From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Daniel Mendler Newsgroups: gmane.emacs.devel Subject: [PATCH] `completing-read` - allow history=t, sorting improvements Date: Mon, 19 Apr 2021 20:02:44 +0200 Message-ID: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------22668FB1D0FCF59B9C4806F0" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="18806"; mail-complaints-to="usenet@ciao.gmane.io" To: "emacs-devel@gnu.org" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Apr 19 20:04:01 2021 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lYYFc-0004gr-Nk for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 20:04:00 +0200 Original-Received: from localhost ([::1]:39316 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lYYFb-0007GJ-R6 for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 14:03:59 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60708) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYYEY-0006Qz-Pp for emacs-devel@gnu.org; Mon, 19 Apr 2021 14:02:55 -0400 Original-Received: from server.qxqx.de ([2a01:4f8:121:346::180]:52831 helo=mail.qxqx.de) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYYES-00038N-ND for emacs-devel@gnu.org; Mon, 19 Apr 2021 14:02:54 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=qxqx.de; s=mail1392553390; h=Content-Type:MIME-Version:Date:Message-ID:To:Subject:From :Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=aRXJOiqKzM8vW4Y+hNy4DWOeEQLNIoaAhLQ4xGsOPAw=; b=TKjHWiJFNanGQmMr+Vvut/vS1P tK9iZqOh6GgMC8hIT6eii5KnsN66iQ6l7YwO6XnM3xzxzbyq4co6G2jaNgTC0oBgLlvOH/BDse+qo cCOdHbGlCp5UbLMfWJ5amm+7Hly+HuVW5bx7VZYQNpkadGOlySA63cSDdFfhqPvm2r0g=; Content-Language: en-US Received-SPF: pass client-ip=2a01:4f8:121:346::180; envelope-from=mail@daniel-mendler.de; helo=mail.qxqx.de X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:268187 Archived-At: This is a multi-part message in MIME format. --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit I attached patches for minibuffer.el which address these points: 1. Allow history=t to disable the `completing-read` history 2. Sorting improvements Daniel Mendler --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0001-completing-read-If-HIST-is-the-symbol-t-history-is-n.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-completing-read-If-HIST-is-the-symbol-t-history-is-n.pa"; filename*1="tch" >From 6b68a42ef77fcb4c07e5a110e4c77be10985852b Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 08:20:50 +0200 Subject: [PATCH 1/6] completing-read: If HIST is the symbol `t', history is not recorded. * lisp/minibuffer.el (completion-all-sorted-completions): Check if `minibuffer-history-variable` is `t` * src/minibuf.c (completing-read): Update docstring * doc/lispref/minibuf.texi: Update documentation of `read-from-minibuffer` and `completing-read` --- doc/lispref/minibuf.texi | 13 ++++++++----- lisp/minibuffer.el | 2 +- src/minibuf.c | 3 ++- 3 files changed, 11 insertions(+), 7 deletions(-) diff --git a/doc/lispref/minibuf.texi b/doc/lispref/minibuf.texi index d16409d6c8..e922f1836b 100644 --- a/doc/lispref/minibuf.texi +++ b/doc/lispref/minibuf.texi @@ -167,8 +167,10 @@ Text from Minibuffer The argument @var{history} specifies a history list variable to use for saving the input and for history commands used in the minibuffer. -It defaults to @code{minibuffer-history}. You can optionally specify -a starting position in the history list as well. @xref{Minibuffer History}. +It defaults to @code{minibuffer-history}. If @var{history} is the +symbol @code{t}, history is not recorded. You can optionally specify +a starting position in the history list as well. @xref{Minibuffer +History}. If the variable @code{minibuffer-allow-text-properties} is non-@code{nil}, then the string that is returned includes whatever text @@ -1107,9 +1109,10 @@ Minibuffer Completion @code{minibuffer-local-must-match-map} if @var{require-match} is non-@code{nil}. @xref{Completion Commands}. -The argument @var{history} specifies which history list variable to use for -saving the input and for minibuffer history commands. It defaults to -@code{minibuffer-history}. @xref{Minibuffer History}. +The argument @var{history} specifies which history list variable to +use for saving the input and for minibuffer history commands. It +defaults to @code{minibuffer-history}. If @var{history} is the symbol +@code{t}, history is not recorded. @xref{Minibuffer History}. The argument @var{initial} is mostly deprecated; we recommend using a non-@code{nil} value only in conjunction with specifying a cons cell diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index c900b0d7ce..06a5e1e988 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1390,7 +1390,7 @@ completion-all-sorted-completions (t ;; Prefer shorter completions, by default. (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2))))) - (if (minibufferp) + (if (and (minibufferp) (not (eq minibuffer-history-variable t))) ;; Prefer recently used completions and put the default, if ;; it exists, on top. (let ((hist (symbol-value minibuffer-history-variable))) diff --git a/src/minibuf.c b/src/minibuf.c index a3c1b99bf3..f025817276 100644 --- a/src/minibuf.c +++ b/src/minibuf.c @@ -2023,7 +2023,8 @@ DEFUN ("completing-read", Fcompleting_read, Scompleting_read, 2, 8, 0, (This is the only case in which you should use INITIAL-INPUT instead of DEF.) Positions are counted starting from 1 at the beginning of the list. The variable `history-length' controls the maximum length - of a history list. + of a history list. If HIST is the symbol `t', history is not + recorded. DEF, if non-nil, is the default value or the list of default values. -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0002-minibuffer.el-Use-completion-message-instead-of-mini.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0002-minibuffer.el-Use-completion-message-instead-of-mini.pa"; filename*1="tch" >From 42a99f69032b801a402d716280a50b4e27d1238f Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 15:40:00 +0200 Subject: [PATCH 2/6] minibuffer.el: Use completion--message instead of minibuffer-message * minibuffer.el: Use completion--message consistently for the messages "Incomplete", "Sole completion" and "No completions". --- lisp/minibuffer.el | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index 06a5e1e988..e4da79ad2b 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1423,7 +1423,7 @@ minibuffer-force-complete-and-exit ;; test-completion, then we shouldn't exit, but that should be rare. (lambda () (if minibuffer--require-match - (minibuffer-message "Incomplete") + (completion--message "Incomplete") ;; If a match is not required, exit after all. (exit-minibuffer))))) @@ -2008,7 +2008,7 @@ minibuffer-completion-help ;; the sole completion, then hide (previous&stale) completions. (minibuffer-hide-completions) (ding) - (minibuffer-message + (completion--message (if completions "Sole completion" "No completions"))) (let* ((last (last completions)) -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0003-completion-all-sorted-completions-Fix-sorting-perfor.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0003-completion-all-sorted-completions-Fix-sorting-perfor.pa"; filename*1="tch" >From 1a7d149642baafd7785a126cdf2644eff5b51149 Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 08:43:41 +0200 Subject: [PATCH 3/6] completion-all-sorted-completions: Fix sorting performance bug * lisp/minibuffer.el (completion-all-sorted-completions): Use hash table for sorting by history position, O(m+n*log(n)) instead of O(m*n*log(n)) with history length `m` and candidate length `n`. --- lisp/minibuffer.el | 33 +++++++++++++++++++++++++-------- 1 file changed, 25 insertions(+), 8 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index e4da79ad2b..d728c791d3 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1393,14 +1393,31 @@ completion-all-sorted-completions (if (and (minibufferp) (not (eq minibuffer-history-variable t))) ;; Prefer recently used completions and put the default, if ;; it exists, on top. - (let ((hist (symbol-value minibuffer-history-variable))) - (setq all - (sort all - (lambda (c1 c2) - (cond ((equal c1 minibuffer-default) t) - ((equal c2 minibuffer-default) nil) - (t (> (length (member c1 hist)) - (length (member c2 hist)))))))))))) + (let* ((hist (symbol-value minibuffer-history-variable)) + (hash (make-hash-table :test #'equal :size (length hist))) + (index 0) + (def (car-safe minibuffer-default))) + ;; Record history positions in hash + (dolist (c hist) + (unless (gethash c hash) + (puthash c index hash)) + (cl-incf index)) + (when (stringp def) + (puthash def -1 hash)) + ;; Decorate elements with history position + (let ((c all)) + (while c + (setcar c (cons (gethash (car c) hash + most-positive-fixnum) + (car c))) + (pop c))) + (setq all (sort all #'car-less-than-car)) + ;; Drop decoration from the elements + (let ((c all)) + (while c + (setcar c (cdar c)) + (pop c))))))) + ;; Cache the result. This is not just for speed, but also so that ;; repeated calls to minibuffer-force-complete can cycle through ;; all possibilities. -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0004-completion-all-sorted-completions-Respect-completion.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0004-completion-all-sorted-completions-Respect-completion.pa"; filename*1="tch" >From 827c17d1645cce8d37a4a65369bea29e36681f3e Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 13:06:54 +0200 Subject: [PATCH 4/6] completion-all-sorted-completions: Respect completion boundaries * lisp/minibuffer.el (completion-all-sorted-completions): When building the hash of history positions drop the prefix as determined by `completion-boundaries`. For file completions drop everything behind the first "/". --- lisp/minibuffer.el | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index d728c791d3..c7aec9665e 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1396,14 +1396,36 @@ completion-all-sorted-completions (let* ((hist (symbol-value minibuffer-history-variable)) (hash (make-hash-table :test #'equal :size (length hist))) (index 0) - (def (car-safe minibuffer-default))) - ;; Record history positions in hash - (dolist (c hist) - (unless (gethash c hash) - (puthash c index hash)) - (cl-incf index)) + (def (car-safe minibuffer-default)) + (bounds (completion-boundaries + (substring string 0 (- (point) start)) + minibuffer-completion-table + minibuffer-completion-predicate + "")) + (pre (substring string 0 (car bounds))) + (pre-len (length pre))) + ;; Default comes first. (when (stringp def) - (puthash def -1 hash)) + (setq hist (cons def hist))) + ;; Record history positions in hash + (if (equal "" pre) + (progn + (dolist (c hist) + (unless (gethash c hash) + (puthash c index hash)) + (cl-incf index))) + ;; Remove prefix from history strings, in order to + ;; handle completion boundaries. + (dolist (c hist) + (when (string-prefix-p pre c) + ;; Special handling of file name candidates: + ;; Drop everything after the first / after the prefix. + (let ((pos (and minibuffer-completing-file-name + (string-match-p "/" c pre-len)))) + (setq c (substring c pre-len (and pos (1+ pos))))) + (unless (gethash c hash) + (puthash c index hash))) + (cl-incf index))) ;; Decorate elements with history position (let ((c all)) (while c -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0005-completion-all-sorted-completions-Sort-candidates-in.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0005-completion-all-sorted-completions-Sort-candidates-in.pa"; filename*1="tch" >From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 13:17:23 +0200 Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a single pass * lisp/minibuffer.el (completion-all-sorted-completions): Decorate each candidate with history position and length such that the list can be sorted in a single pass. --- lisp/minibuffer.el | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index c7aec9665e..7146604ab4 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1388,11 +1388,9 @@ completion-all-sorted-completions (sort-fun (setq all (funcall sort-fun all))) (t - ;; Prefer shorter completions, by default. - (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2))))) (if (and (minibufferp) (not (eq minibuffer-history-variable t))) - ;; Prefer recently used completions and put the default, if - ;; it exists, on top. + ;; Sort first by history position and then by length. + ;; Put the default, if it exists, on top. (let* ((hist (symbol-value minibuffer-history-variable)) (hash (make-hash-table :test #'equal :size (length hist))) (index 0) @@ -1426,19 +1424,26 @@ completion-all-sorted-completions (unless (gethash c hash) (puthash c index hash))) (cl-incf index))) - ;; Decorate elements with history position + ;; Decorate each candidate with (index<<13) + + ;; length. This way we sort first by index and then + ;; by length. We assume that the candidates are + ;; shorter than 2^13 characters and that the + ;; history is shorter than 2^16 entries. (let ((c all)) (while c - (setcar c (cons (gethash (car c) hash - most-positive-fixnum) - (car c))) + (setcar c (cons + (+ (lsh (gethash (car c) hash #xFFFF) 13) + (length (car c))) + (car c))) (pop c))) (setq all (sort all #'car-less-than-car)) ;; Drop decoration from the elements (let ((c all)) (while c (setcar c (cdar c)) - (pop c))))))) + (pop c)))) + ;; Sort only by length if no history is available. + (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))))) ;; Cache the result. This is not just for speed, but also so that ;; repeated calls to minibuffer-force-complete can cycle through -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0 Content-Type: text/x-diff; charset=UTF-8; name="0006-completion-all-sorted-completions-Sort-alphabeticall.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0006-completion-all-sorted-completions-Sort-alphabeticall.pa"; filename*1="tch" >From 4c657dcd79ee641193ea952cd4c1a01d842aa395 Mon Sep 17 00:00:00 2001 From: Daniel Mendler Date: Mon, 19 Apr 2021 13:25:43 +0200 Subject: [PATCH 6/6] completion-all-sorted-completions: Sort alphabetically * lisp/minibuffer.el (completion-all-sorted-completions): Sort by history position, length and alphabetically. --- lisp/minibuffer.el | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index 7146604ab4..f0277bf4fc 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -1389,8 +1389,9 @@ completion-all-sorted-completions (setq all (funcall sort-fun all))) (t (if (and (minibufferp) (not (eq minibuffer-history-variable t))) - ;; Sort first by history position and then by length. - ;; Put the default, if it exists, on top. + ;; Sort first by history position, then by length, + ;; then alphabetically. Put the default, if it exists, + ;; on top. (let* ((hist (symbol-value minibuffer-history-variable)) (hash (make-hash-table :test #'equal :size (length hist))) (index 0) @@ -1436,14 +1437,21 @@ completion-all-sorted-completions (length (car c))) (car c))) (pop c))) - (setq all (sort all #'car-less-than-car)) + (setq all (sort all (lambda (c1 c2) + (or (< (car c1) (car c2)) + (and (= (car c1) (car c2)) + (string< (cdr c1) (cdr c2))))))) ;; Drop decoration from the elements (let ((c all)) (while c (setcar c (cdar c)) (pop c)))) - ;; Sort only by length if no history is available. - (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))))) + ;; Sort only by length and alphabetically if no history + ;; is available. + (setq all (sort all (lambda (c1 c2) + (or (< (length c1) (length c2)) + (and (= (length c1) (length c2)) + (string< c1 c2))))))))) ;; Cache the result. This is not just for speed, but also so that ;; repeated calls to minibuffer-force-complete can cycle through -- 2.20.1 --------------22668FB1D0FCF59B9C4806F0--