From: Daniel Mendler <mail@daniel-mendler.de>
To: "emacs-devel@gnu.org" <emacs-devel@gnu.org>
Subject: [PATCH] `completing-read` - allow history=t, sorting improvements
Date: Mon, 19 Apr 2021 20:02:44 +0200 [thread overview]
Message-ID: <d07ce97d-55ee-96c7-02bb-b5f64de73f33@daniel-mendler.de> (raw)
[-- Attachment #1: Type: text/plain, Size: 166 bytes --]
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
[-- Attachment #2: 0001-completing-read-If-HIST-is-the-symbol-t-history-is-n.patch --]
[-- Type: text/x-diff, Size: 3556 bytes --]
From 6b68a42ef77fcb4c07e5a110e4c77be10985852b Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
[-- Attachment #3: 0002-minibuffer.el-Use-completion-message-instead-of-mini.patch --]
[-- Type: text/x-diff, Size: 1318 bytes --]
From 42a99f69032b801a402d716280a50b4e27d1238f Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
[-- Attachment #4: 0003-completion-all-sorted-completions-Fix-sorting-perfor.patch --]
[-- Type: text/x-diff, Size: 2785 bytes --]
From 1a7d149642baafd7785a126cdf2644eff5b51149 Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
[-- Attachment #5: 0004-completion-all-sorted-completions-Respect-completion.patch --]
[-- Type: text/x-diff, Size: 3079 bytes --]
From 827c17d1645cce8d37a4a65369bea29e36681f3e Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
[-- Attachment #6: 0005-completion-all-sorted-completions-Sort-candidates-in.patch --]
[-- Type: text/x-diff, Size: 3144 bytes --]
From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
[-- Attachment #7: 0006-completion-all-sorted-completions-Sort-alphabeticall.patch --]
[-- Type: text/x-diff, Size: 2679 bytes --]
From 4c657dcd79ee641193ea952cd4c1a01d842aa395 Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
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
next reply other threads:[~2021-04-19 18:02 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-04-19 18:02 Daniel Mendler [this message]
2021-04-19 19:14 ` [PATCH] `completing-read` - allow history=t, sorting improvements Stefan Monnier
2021-04-19 19:36 ` Daniel Mendler
2021-04-19 20:15 ` Stefan Monnier
2021-04-19 20:44 ` Daniel Mendler
2021-04-19 21:52 ` Stefan Monnier
2021-04-19 22:29 ` Daniel Mendler
2021-04-19 22:55 ` Stefan Monnier
2021-04-19 23:47 ` Daniel Mendler
2021-04-20 1:55 ` Stefan Monnier
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d07ce97d-55ee-96c7-02bb-b5f64de73f33@daniel-mendler.de \
--to=mail@daniel-mendler.de \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).