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

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

[Clemens]

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)))))))))
```

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

[Dmitry Gutov]

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.

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

[Lars Ingebrigtsen]

Clemens <clemera@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

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

[Daniel Mendler]

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

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

[Lars Ingebrigtsen]

Daniel Mendler <mail@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