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

[Daniel Mendler <daniel@mendler.net>]

[-- Attachment #1: Type: text/plain, Size: 1673 bytes --]

On 4/19/21 11:52 PM, Stefan Monnier wrote:
>> But if this get improved, people may throw more candidates at it and
>> then we will end up again with a threshold.
> 
> That's the main point, indeed: rather than try to handle larger sets, we
> want to avoid larger sets.  

I agree - it is always good to cut off a large amount of the work early on.

> That's why we have
> `icomplete-show-matches-on-no-input` and `company-minimum-prefix-length`
> (tho there can be other approaches like pushing the processing of sets
> to a separate async process).

Yes, these are reasonable settings. However many people like to see 
candidates up front, me included (at least currently, taste changes) - 
like in Ido, Ivy, Selectrum, Vertico etc. Then I am not very fond of 
operations happening after some idle time. Having an input limits feels 
more deterministic.

If Emacs can be made such that it fits for different usage patterns 
that's great. But I would not over do it in optimizing for a million 
candidates - therefore my poor man's "solution" of a threshold in Vertico.

Btw, I attached the updated patch for the boundaries. I am not sure if 
the approach I took there is a good one, this works only in restricted 
set of scenarios (not with partial-completion/initials unfortunately). 
So this should be discussed.

Then you mentioned test cases - to clarify, do you want to see some kind 
of integration test where a mockup minibuffer-completion-table is set-up 
and the results of `completion-all-sorted-completions` are checked, or 
some smaller tests of the helper functions? I looked briefly into 
test/lisp/minibuffer.el - the test should probably go there?

Daniel

[-- Attachment #2: 0002-completion-all-sorted-completions-Add-completion-bou.patch --]
[-- Type: text/x-diff, Size: 3913 bytes --]

From a09ea8f4eb9a341f6c4ab090ec0c49acf070589a Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Tue, 20 Apr 2021 00:01:44 +0200
Subject: [PATCH] completion-all-sorted-completions: Add completion boundary
 support

Remove the completion prefix from the history elements.  This is a
heuristic which does not work for all completion styles.  In
particular when using partial-completion or initials, the candidates
contain directories. Is there a better more general solution?

minibuffer.el (completion-all-sorted-completions): The history is
preprocessed by the function `minibuffer--sort-preprocess-history`.
---
 lisp/minibuffer.el | 49 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 40 insertions(+), 9 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 4ed596430c..d340aec98b 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1381,6 +1381,42 @@ minibuffer--sort-by-length-alpha
                     (and (= (length c1) (length c2))
                          (string< c1 c2))))))
 
+(defun minibuffer--sort-preprocess-history (start string)
+  "Preprocess history, remove completion prefixes.
+STRING is the minibuffer content.
+START is the start position of the completion."
+  (let* ((def (car-safe minibuffer-default))
+         (hist (symbol-value minibuffer-history-variable))
+         (hist (if def (cons def hist) hist))
+         (bounds (completion-boundaries
+                  (substring string 0 (- (point) start))
+                  minibuffer-completion-table
+                  minibuffer-completion-predicate
+                  ""))
+         (pre (substring string 0 (car bounds)))
+         (pre-len (length pre)))
+    ;; Preprocess history if completion boundaries are used
+    (cond
+     ;; Special handling of file name candidates.
+     ;; Drop prefix and everything after the first "/".
+     (minibuffer-completing-file-name
+      (setq hist (delq nil
+                       (mapcar
+                        (lambda (c)
+                          (when (string-prefix-p pre c)
+                            (let ((pos (string-match-p "/" c pre-len)))
+                              (substring c pre-len (and pos (1+ pos))))))
+                        hist))))
+     ;; Drop prefix before the completion boundary
+     ((/= pre-len 0)
+      (setq hist
+            (delq nil (mapcar
+                       (lambda (c)
+                         (when (string-prefix-p pre c)
+                           (substring c pre-len)))
+                       hist))))
+     (t hist))))
+
 (defun completion-all-sorted-completions (&optional start end)
   (or completion-all-sorted-completions
       (let* ((start (or start (minibuffer-prompt-end)))
@@ -1410,21 +1446,16 @@ completion-all-sorted-completions
           (setq all (delete-dups all))
           (setq last (last all))
 
-          (cond
-           (sort-fun
-            (setq all (funcall sort-fun all)))
-           (t
+          (if sort-fun
+              (setq all (funcall sort-fun all))
             ;; Sort first by length and alphabetically.
             (setq all (minibuffer--sort-by-length-alpha all))
-
             ;; Sort by history position, put the default, if it
             ;; exists, on top.
             (when (and (minibufferp) (not (eq minibuffer-history-variable t)))
-              (let ((def (car-safe minibuffer-default))
-                    (hist (symbol-value minibuffer-history-variable)))
               (setq all (minibuffer--sort-by-position
-                         (if def (cons def hist) hist)
-                         all))))))
+                         (minibuffer--sort-preprocess-history start string)
+                         all))))
 
           ;; 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