Re: [PATCH] `completing-read` - allow history=t, sorting improvements

[Stefan Monnier <monnier@iro.umontreal.ca>]

Hi Daniel,

> 1. Allow history=t to disable the `completing-read` history

Thanks, pushed.
I see that this was really just a bug fix: t already prevented adding
the result to "the history", there was just one place where the code
burped when encountering this special "history var".

> 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

I don't have a strong opinion on this patch, but I have the impression
that there might have been a good reason for the difference (i.e. the
above two cases could be considered "more serious" than those using
`completion--message`).

I would personally gladly get rid of `completion-show-inline-help`, so
I'm not the right person to judge if the above patch is doing the right
thing or not.

I pushed your "use a hash-table" patch to fix the N² complexity.

> 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 @@
>                  (let* ((hist (symbol-value minibuffer-history-variable))
>                         (hash (make-hash-table :test #'equal :size (length hist)))
>                         (index 0)
> -                       (def (car-safe minibuffer-default)))
> +                       (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)
> +                    (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))
> -                  (when (stringp def)
> -                    (puthash def -1 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

I think I'm fine with this patch, but at that point, this sorting code
*really* needs to be moved out into a separate function (already the
previous patch, which I just pushed, was borderline in this respect).
Also, I think this should come with a test case.

> 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.

Does this result in a measurable difference?
The assumptions about maximum size and length aren't ideal, so unless
there's a clear performance argument, I think we're better off sticking
to the multiple passes.

> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
> history position, length and alphabetically.

I'd expect this will not make a big difference in most cases, but the
fact that it results in a more deterministic outcome is very welcome.
If you rebase this patch on top of the current minibuffer.el, I'll be
happy to push it.

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

Here also: have you compared the performance of multiple calls to `sort`
vs a single call to sort with a more costly comparison function?
I'd expect the difference to be negligible (and having a separate
alphabetical sort at the beginning would save us from having to handle
it twice (i.e. in the two different branches)).


        Stefan