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

From: Clemens <[email-masked]>
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)))))))))
```