GNU bug report logs - #47294
27.1; completing-read: History handling and sorting

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 47294 in the body.
You can then email your comments to 47294 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Clemens <clemera <at> posteo.net>
To: bug-gnu-emacs <at> gnu.org
Subject: 27.1; completing-read: History handling and sorting
Date: Sun, 21 Mar 2021 15:29:49 +0100

One can pass `t` to ignore history to `read-from-minibuffer`. I
assumed this is also true for `completing-read` and discovered this
would throw an error (for example when using icomplete
`completion-all-sorted-completions` is called which doesn't handle the
`t` value). Can we change things to allow this API also for
`completing-read`?

Another observation is that the implementation of
`completion-all-sorted-completions` could be made faster by using a
hash table as Daniel Mendler implemented it for Selectrum:

```elisp
(let* ((list (and (not (eq minibuffer-history-variable t))
                  (symbol-value minibuffer-history-variable)))
       (hist (make-hash-table :test #'equal
                              :size (length list))))
  ;; Store the history position first in a hashtable in order to
  ;; keep the sorting fast and the complexity at O(n*log(n)).
  (seq-do-indexed (lambda (elem idx)
                    (unless (gethash elem hist)
                      (puthash elem idx hist)))
                  list)
  (sort candidates
        (lambda (c1 c2)
          (let ((h1 (gethash c1 hist most-positive-fixnum))
                (h2 (gethash c2 hist most-positive-fixnum))
                (l1 (length c1))
                (l2 (length c2)))
            (or (< h1 h2)
                (and (= h1 h2)
                     (or (< l1 l2)
                         (and (= l1 l2) (string< c1 c2)))))))))
```

Message #8 received at 47294 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Gutov <dgutov <at> yandex.ru>
To: Clemens <clemera <at> posteo.net>, 47294 <at> debbugs.gnu.org
Subject: Re: bug#47294: 27.1; completing-read: History handling and sorting
Date: Mon, 22 Mar 2021 21:50:02 +0200

On 21.03.2021 16:29, Clemens wrote:
> Another observation is that the implementation of
> `completion-all-sorted-completions` could be made faster by using a
> hash table as Daniel Mendler implemented it for Selectrum:

This sounds sensible, but some supporting numbers couldn't hurt.

And a patch in the form of a diff against master.

Message #11 received at 47294 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Clemens <clemera <at> posteo.net>
Cc: 47294 <at> debbugs.gnu.org
Subject: Re: bug#47294: 27.1; completing-read: History handling and sorting
Date: Sat, 25 Jun 2022 17:12:46 +0200

Clemens <clemera <at> posteo.net> writes:

> One can pass `t` to ignore history to `read-from-minibuffer`. I
> assumed this is also true for `completing-read` and discovered this
> would throw an error (for example when using icomplete
> `completion-all-sorted-completions` is called which doesn't handle the
> `t` value). Can we change things to allow this API also for
> `completing-read`?

(I'm going through old bug reports that unfortunately weren't resolved
at the time.)

I'm unable to reproduce this in Emacs 27.1 and the current trunk.

(completing-read "foo" nil nil nil nil t)

doesn't throw an error for me.  Do you have a complete recipe to
reproduce the problem?

> Another observation is that the implementation of
> `completion-all-sorted-completions` could be made faster by using a
> hash table as Daniel Mendler implemented it for Selectrum:
>
> ```elisp
> (let* ((list (and (not (eq minibuffer-history-variable t))
>                    (symbol-value minibuffer-history-variable)))
>         (hist (make-hash-table :test #'equal
>                                :size (length list))))
>    ;; Store the history position first in a hashtable in order to
>    ;; keep the sorting fast and the complexity at O(n*log(n)).
>    (seq-do-indexed (lambda (elem idx)
>                      (unless (gethash elem hist)
>                        (puthash elem idx hist)))
>                    list)
>    (sort candidates
>          (lambda (c1 c2)
>            (let ((h1 (gethash c1 hist most-positive-fixnum))
>                  (h2 (gethash c2 hist most-positive-fixnum))
>                  (l1 (length c1))
>                  (l2 (length c2)))
>              (or (< h1 h2)
>                  (and (= h1 h2)
>                       (or (< l1 l2)
>                           (and (= l1 l2) (string< c1 c2)))))))))

It's not immediately obvious to me what this code is supposed to
replace.  Do you have a patch for this instead?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Message #16 received at 47294 <at> debbugs.gnu.org (full text, mbox):

From: Daniel Mendler <mail <at> daniel-mendler.de>
To: 47294 <at> debbugs.gnu.org
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#47294: 27.1; completing-read: History handling and sorting
Date: Sat, 25 Jun 2022 18:32:23 +0200

As far as I know, both issues have already been fixed in Emacs 28.
completing-read accepts t now to disable the history. I contributed the
patch for sorting by history using a hashtable (see
minibuffer--sort-by-position).

Daniel

Message #19 received at 47294 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Daniel Mendler <mail <at> daniel-mendler.de>
Cc: 47294 <at> debbugs.gnu.org
Subject: Re: bug#47294: 27.1; completing-read: History handling and sorting
Date: Sun, 26 Jun 2022 14:40:41 +0200

Daniel Mendler <mail <at> daniel-mendler.de> writes:

> As far as I know, both issues have already been fixed in Emacs 28.
> completing-read accepts t now to disable the history. I contributed the
> patch for sorting by history using a hashtable (see
> minibuffer--sort-by-position).

Ah, thanks.  I'm closing this bug report, then.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.