bug#42149: Substring and flex completion ignore implicit trailing ‘any’

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi,

I have found out that substring and flex completion ignore the implicit
trailing ‘any’ introduced by ‘completion-pcm--optimize-pattern’.  This
is evident from the examples shown next.

My Emacs version is 28.0.50, built on 2020-07-01 from commit e98ddd6fc1.

Example 1
=========

  (completion-substring-all-completions "f" (list "f") nil 1)

and

  (completion-flex-all-completions "f" (list "f") nil 1)

both result in

  (#("f" 0 1 (face completions-common-part completion-score 0.0)) . 0)

whereas I would expect a completion score of 1.

Example 2
=========

  (completion-substring-all-completions "fo" (list "fo") nil 1)

results in

  (#("fo" 0 1 (face completions-common-part completion-score 0.5) 1 2
    (face (completions-first-difference completions-common-part))) . 0)

whereas I would again expect a completion score of 1.

Proposed Solution
=================

I propose that we make the implicit trailing ‘any’ explicit in
‘completion-substring--all-completions’.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Make implicit trailing `any' explicit in `completion-substring--all-completions' --]
[-- Type: text/x-diff, Size: 951 bytes --]

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d2c3f9045e..a598b1d1fd 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3585,10 +3585,12 @@ that is non-nil."
          (pattern (if (not (stringp (car basic-pattern)))
                       basic-pattern
                     (cons 'prefix basic-pattern)))
-         (pattern (completion-pcm--optimize-pattern
-                   (if transform-pattern-fn
-                       (funcall transform-pattern-fn pattern)
-                     pattern)))
+         (pattern (append
+                   (completion-pcm--optimize-pattern
+                    (if transform-pattern-fn
+                        (funcall transform-pattern-fn pattern)
+                      pattern))
+                   '(any)))             ; make implicit `any' explicit
          (all (completion-pcm--all-completions prefix pattern table pred)))
     (list all pattern prefix suffix (car bounds))))
 

[-- Attachment #3: Type: text/plain, Size: 318 bytes --]


This fixes the problem and seems to perform well from my testing.
However, I have no idea if I am overlooking something, so please let me
know.

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

> Hi,
>
> I have found out that substring and flex completion ignore the implicit
> trailing ‘any’ introduced by ‘completion-pcm--optimize-pattern’.  This
> is evident from the examples shown next.
>
> My Emacs version is 28.0.50, built on 2020-07-01 from commit e98ddd6fc1.
>
> Example 1
> =========
>
>   (completion-substring-all-completions "f" (list "f") nil 1)
>
> and
>
>   (completion-flex-all-completions "f" (list "f") nil 1)
>
> both result in
>
>   (#("f" 0 1 (face completions-common-part completion-score 0.0)) . 0)
>
> whereas I would expect a completion score of 1.

Is it the fact that the completion-score is 0 that causes the earlier
problems you experienced?

> Example 2
> =========
>
>   (completion-substring-all-completions "fo" (list "fo") nil 1)
>
> results in
>
>   (#("fo" 0 1 (face completions-common-part completion-score 0.5) 1 2
>     (face (completions-first-difference completions-common-part))) . 0)
>
> whereas I would again expect a completion score of 1.
>
> Proposed Solution
> =================
>
> I propose that we make the implicit trailing ‘any’ explicit in
> ‘completion-substring--all-completions’.
>
> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index d2c3f9045e..a598b1d1fd 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -3585,10 +3585,12 @@ that is non-nil."
>           (pattern (if (not (stringp (car basic-pattern)))
>                        basic-pattern
>                      (cons 'prefix basic-pattern)))
> -         (pattern (completion-pcm--optimize-pattern
> -                   (if transform-pattern-fn
> -                       (funcall transform-pattern-fn pattern)
> -                     pattern)))
> +         (pattern (append
> +                   (completion-pcm--optimize-pattern
> +                    (if transform-pattern-fn
> +                        (funcall transform-pattern-fn pattern)
> +                      pattern))
> +                   '(any)))             ; make implicit `any' explicit
>           (all (completion-pcm--all-completions prefix pattern table pred)))
>      (list all pattern prefix suffix (car bounds))))
>  
>
>
> This fixes the problem and seems to perform well from my testing.
> However, I have no idea if I am overlooking something, so please let me
> know.

You analysis is good and it does reveal a quirk somewhere.  However, for
now, completion scores are relative things, i.e. they an absolute value
has no meaning by its own.

I can therefore understand that "t" disappears from your completion list
(goes to the very end) given that something else has non-zero score,
like "footrix".

But does the problem also manifest itself with two-character
completions?  I.e. is the 0.5 perfect match for "fo" (in the example you
gave) ever surpassed by another, presumably less good, match?

So I'd have to look better.  Either

- The bug is where you say it is, and the fix should go where you say it
  does.

- Some numeric adjust should be made to the algorithm
  completion-pcm--hilit-commonality.

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

> > Hi,
> >
> > I have found out that substring and flex completion ignore the implicit
> > trailing ‘any’ introduced by ‘completion-pcm--optimize-pattern’.  This
> > is evident from the examples shown next.
> >
> > My Emacs version is 28.0.50, built on 2020-07-01 from commit e98ddd6fc1.
> >
> > Example 1
> > =========
> >
> >   (completion-substring-all-completions "f" (list "f") nil 1)
> >
> > and
> >
> >   (completion-flex-all-completions "f" (list "f") nil 1)
> >
> > both result in
> >
> >   (#("f" 0 1 (face completions-common-part completion-score 0.0)) . 0)
> >
> > whereas I would expect a completion score of 1.
> >
> > Example 2
> > =========
> >
> >   (completion-substring-all-completions "fo" (list "fo") nil 1)
> >
> > results in
> >
> >   (#("fo" 0 1 (face completions-common-part completion-score 0.5) 1 2
> >     (face (completions-first-difference completions-common-part))) . 0)
> >
> But does the problem also manifest itself with two-character
> completions?  I.e. is the 0.5 perfect match for "fo" (in the example you
> gave) ever surpassed by another, presumably less good, match?

Answering my own question, the answer seems to be "no".

   (completion-substring-all-completions "fo" (list "f" "fo" "foot") nil 1)
   (#("fo" 0 1
      (face completions-common-part completion-score 0.5)
      1 2
      (face
       (completions-first-difference completions-common-part)))
    #("foot" 0 1
      (face completions-common-part completion-score 0.25)
      1 2
      (face
       (completions-first-difference completions-common-part)))
    . 0)


But indeed there is the problem of the 1-long.  And the problem is that
_every_ completion gets 0.

   (completion-substring-all-completions "f" (list "f" "fo" "foot") nil 1)
   (#("f" 0 1
      (face completions-common-part completion-score 0.0))
    #("fo" 0 1
      (face completions-common-part completion-score 0.0)
      1 2
      (face completions-first-difference))
    #("foot" 0 1
      (face completions-common-part completion-score 0.0)
      1 2
      (face completions-first-difference))
    . 0)

I still don't know what the proper fix this, just adding some
information I think is relevant.

Thanks,
João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi João,

> I still don't know what the proper fix this, just adding some
> information I think is relevant.

Indeed the problem is that they all get a completion score of 0, and I
would expect the exact match to get a score of 1.

You’re right that we can also modify the algorithm of
‘completion-pcm--hilit-commonality’.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Modify the algorithm of ‘completion-pcm--hilit-commonality’ --]
[-- Type: text/x-diff, Size: 1413 bytes --]

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d2c3f9045e..e1f1ffed1c 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3251,6 +3251,9 @@ one-letter-long matches).")
                 (update-score
                  (lambda (a b)
                    "Update score variables given match range (A B)."
+		   (add-face-text-property a b
+					   'completions-common-part
+					   nil str)
                    (setq
                     score-numerator   (+ score-numerator (- b a)))
                    (unless (or (= a last-b)
@@ -3264,19 +3267,10 @@ one-letter-long matches).")
                                                     flex-score-match-tightness)))))
                    (setq
                     last-b              b))))
-           (funcall update-score start start)
            (while md
-             (funcall update-score start (car md))
-             (add-face-text-property
-              start (pop md)
-              'completions-common-part
-              nil str)
+             (funcall update-score start (pop md))
              (setq start (pop md)))
-           (funcall update-score len len)
-           (add-face-text-property
-            start end
-            'completions-common-part
-            nil str)
+           (funcall update-score start end)
            (if (> (length str) pos)
                (add-face-text-property
                 pos (1+ pos)

[-- Attachment #3: Type: text/plain, Size: 308 bytes --]

This modification also solves the issue (and simplifies the code a
little bit), but I’m not sure of unwanted side effects.

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi João, hi everyone,

Is there any progress on this?

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

On Tue, Sep 8, 2020 at 10:05 AM Dario Gjorgjevski <
dario.gjorgjevski@gmail.com> wrote:

> Hi João, hi everyone,
>
> Is there any progress on this?


I don't think so. Could you (re)state the use case where this matters?
That helps prioritize it.

João

[-- Attachment #2: Type: text/html, Size: 612 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

> I don't think so. Could you (re)state the use case where this matters?
> That helps prioritize it.

Hi João,

My use case is very simple: I have a directory which, among others,
contains files named 1, 2, etc.  It’s really annoying that C-x C-f 2 RET
does not find 2 but instead finds some other file containing 2 in its
name.

Also, I can’t start an R process by doing M-x R RET.  (You need to have
R and ESS installed for this, of course.)

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

On Tue, Sep 8, 2020 at 10:44 AM Dario Gjorgjevski <
dario.gjorgjevski@gmail.com> wrote:

> > I don't think so. Could you (re)state the use case where this matters?
> > That helps prioritize it.
>
> Hi João,
>
> My use case is very simple: I have a directory which, among others,
> contains files named 1, 2, etc.  It’s really annoying that C-x C-f 2 RET
> does not find 2 but instead finds some other file containing 2 in its
> name.
>

Is this is vanilla emacs, or are you using some icomplete-mode or
fido-mode?
I.e. can you post the entire Emacs -Q recipe?


> Also, I can’t start an R process by doing M-x R RET.  (You need to have
> R and ESS installed for this, of course.)


Same question. If you're using, say, fido-mode, you can probably fix this
by typing
M-j instead of RET in these one-letter completion cases. Or even C-u M-j,
if that
doesn't work.

João

[-- Attachment #2: Type: text/html, Size: 1481 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

> Is this is vanilla emacs, or are you using some icomplete-mode or
> fido-mode?
> I.e. can you post the entire Emacs -Q recipe?

It is really simple to reproduce.

0. Run ‘emacs -Q’ in a directory with two files: “1” and “foo1”.
1. Enable fido-mode.
2. C-x C-f 1 RET.

Emacs will open “foo1” even though I would expect it to open “1” as that
is an exact match.  But, I really think this is a pointless discussion.

The issue *is not caused by fido-mode* but by the mechanism of substring
(and therefore, flex) completion.  You can also trigger it without
fido-mode by invoking minibuffer-force-complete-and-exit.

    (completion-flex-all-completions "1" '("1" "11" "1122") nil 1)
    (completion-substring-all-completions "1" '("1" "11" "1122") nil 1)

Both return completely the nonsensical result of

    (#("1"
       0 1 (face completions-common-part completion-score 0.0))
     #("11"
       0 1 (face completions-common-part completion-score 0.0)
       1 2 (face completions-first-difference))
     #("1122"
       0 1 (face completions-common-part completion-score 0.0)
       1 2 (face completions-first-difference))
     . 0)

(Why are all the completion-score values 0?)  Applying the attached
patch changes the result to

    (#("1"
       0 1 (face completions-common-part completion-score 1.0))
     #("11"
       0 1 (face completions-common-part completion-score 0.5)
       1 2 (face completions-first-difference))
     #("1122"
       0 1 (face completions-common-part completion-score 0.25)
       1 2 (face completions-first-difference))
     . 0)

which I hope you would agree makes a lot more sense.

> M-j instead of RET in these one-letter completion cases. Or even C-u
> M-j, if that doesn't work.

Sure, but my muscle memory opposes that.

Best regards,
Dario


[-- Attachment #2: Add explicit trailing ‘any’ to substring completion --]
[-- Type: text/x-diff, Size: 531 bytes --]

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 6deb1eb077..cfcf0fdccb 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3581,6 +3581,7 @@ that is non-nil."
                    (if transform-pattern-fn
                        (funcall transform-pattern-fn pattern)
                      pattern)))
+	 (pattern (append pattern '(any))) ; explicit trailing ‘any’
          (all (completion-pcm--all-completions prefix pattern table pred)))
     (list all pattern prefix suffix (car bounds))))
 

[-- Attachment #3: Type: text/plain, Size: 152 bytes --]


-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

>> Is this is vanilla emacs, or are you using some icomplete-mode or
>> fido-mode?
>> I.e. can you post the entire Emacs -Q recipe?
>
> It is really simple to reproduce.
>
> 0. Run ‘emacs -Q’ in a directory with two files: “1” and “foo1”.
> 1. Enable fido-mode.
> 2. C-x C-f 1 RET.
>
> Emacs will open “foo1” even though I would expect it to open “1” as that
> is an exact match.  But, I really think this is a pointless
> discussion.

It's not.  Before, you hadn't mentioned fido-mode.  As I told you, I
need to assess the priority of this bug, in terms of whom it affects and
to what intensity.

> The issue *is not caused by fido-mode* but by the mechanism of substring
> (and therefore, flex) completion.

Obviously, I'm not disputing that in any way.

>> M-j instead of RET in these one-letter completion cases. Or even C-u
>> M-j, if that doesn't work.
>
> Sure, but my muscle memory opposes that.

I'm sorry, but that's the only workaround I can think of.  Bear in mind
that, when using fido-mode, you need to be aware of that shortcut anyway
in some situations where the text you want to input is not among the
completions.  C-c C-w to write a new file would likely be the most
prominent example.

To summarize, I believe this isn't a very common case, and it is easily
circumvented with the workaround I gave you.  I of course acknowledge
this bug report as a bug.  Maybe you can try making a patch for Emacs
that fixes it and test it.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

> To summarize, I believe this isn't a very common case, and it is easily
> circumvented with the workaround I gave you.  I of course acknowledge
> this bug report as a bug.  Maybe you can try making a patch for Emacs
> that fixes it and test it.

Thanks, I’ll look into it some more and submit a patch.

To be honest, it seems that the issue is also exhibited by
completion-pcm-all-completions, so the best place to fix it would be
completion-pcm--hilit-commonality.

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

On Tue, Sep 8, 2020 at 12:30 PM Dario Gjorgjevski <
dario.gjorgjevski@gmail.com> wrote:

> > To summarize, I believe this isn't a very common case, and it is easily
> > circumvented with the workaround I gave you.  I of course acknowledge
> > this bug report as a bug.  Maybe you can try making a patch for Emacs
> > that fixes it and test it.
>
> Thanks, I’ll look into it some more and submit a patch.
>
> To be honest, it seems that the issue is also exhibited by
> completion-pcm-all-completions, so the best place to fix it would be
> completion-pcm--hilit-commonality.
>

Sounds good. I'm adding Stefan Monnier to this conversation
as he is expert in these matters.

João

[-- Attachment #2: Type: text/html, Size: 1083 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi João, hi Stefan,

Please find attached a patch that fixes this issue and optimizes the
scoring in PCM completion a bit.  As far as I can tell, this works fine
and can be merged, but please have a look and do some testing yourself.


[-- Attachment #2: Fix (and optimize) scoring in PCM completion --]
[-- Type: text/x-diff, Size: 5686 bytes --]

From 8699e72f92524da8041f63949cf29858caded4a5 Mon Sep 17 00:00:00 2001
From: Dario Gjorgjevski <dario.gjorgjevski@gmail.com>
Date: Wed, 9 Sep 2020 12:10:52 +0200
Subject: [PATCH] Fix (and optimize) scoring in PCM completion
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* lisp/minibuffer.el (completion-pcm--hilit-commonality): Fix scoring
to also include the last part of the query string.  This was
especially evident for single-character query strings, e.g.,
‘(completion-flex-all-completions "1" '("1" "foo1") nil 1)’ would
match both "1" and "foo1" with a completion-score of 0.  This
adjustment makes the completion-score of "1" be 1 and of "foo1" by
0.25.  See also bug#42149.  Furthermore, some optimizations are done.
---
 lisp/minibuffer.el | 78 ++++++++++++++++++++++------------------------
 1 file changed, 37 insertions(+), 41 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 62a33f3e2d..7fa132f3c5 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3191,17 +3191,20 @@ one-letter-long matches).")
   (when completions
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
-           (case-fold-search completion-ignore-case))
+           (case-fold-search completion-ignore-case)
+           (score-numerator (float (apply #'+ (mapcar (lambda (part)
+                                                        (if (stringp part)
+                                                            (length part)
+                                                          0))
+                                                      pattern)))))
       (mapcar
        (lambda (str)
-	 ;; Don't modify the string itself.
+         ;; Don't modify the string itself.
          (setq str (copy-sequence str))
          (unless (string-match re str)
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
                 (md (match-data))
-                (start (pop md))
-                (end (pop md))
                 (len (length str))
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
@@ -3237,47 +3240,40 @@ one-letter-long matches).")
                 ;;    (SUM_across_i(hole_i_contrib) + 1) * len
                 ;;
                 ;; , where "len" is the string's length.
-                (score-numerator 0)
-                (score-denominator 0)
-                (last-b 0)
-                (update-score
-                 (lambda (a b)
-                   "Update score variables given match range (A B)."
-                   (setq
-                    score-numerator   (+ score-numerator (- b a)))
-                   (unless (or (= a last-b)
-                               (zerop last-b)
-                               (= a (length str)))
-                     (setq
-                      score-denominator (+ score-denominator
-                                           1
-                                           (expt (- a last-b 1)
-                                                 (/ 1.0
-                                                    flex-score-match-tightness)))))
-                   (setq
-                    last-b              b))))
-           (funcall update-score start start)
+                (full-match-start (pop md))
+                (full-match-end (pop md))
+                (leading-hole-start (pop md))
+                (leading-hole-end (pop md))
+                (match-start leading-hole-end)
+                (score-denominator 0))
            (while md
-             (funcall update-score start (car md))
-             (add-face-text-property
-              start (pop md)
-              'completions-common-part
-              nil str)
-             (setq start (pop md)))
-           (funcall update-score len len)
+             (let ((hole-start (pop md))
+                   (hole-end (pop md)))
+               (add-face-text-property
+                match-start hole-start
+                'completions-common-part
+                nil str)
+               (unless (= hole-start hole-end)
+                 (setq
+                  score-denominator (+ score-denominator
+                                       1
+                                       (expt
+                                        (- hole-end hole-start 1)
+                                        (/ 1.0 flex-score-match-tightness)))))
+               (setq match-start hole-end)))
            (add-face-text-property
-            start end
+            match-start full-match-end
             'completions-common-part
             nil str)
-           (if (> (length str) pos)
-               (add-face-text-property
-                pos (1+ pos)
-                'completions-first-difference
-                nil str))
-           (unless (zerop (length str))
-             (put-text-property
-              0 1 'completion-score
-              (/ score-numerator (* len (1+ score-denominator)) 1.0) str)))
+           (when (> len pos)
+             (add-face-text-property
+              pos (1+ pos)
+              'completions-first-difference
+              nil str))
+           (put-text-property
+            0 1
+            'completion-score
+            (/ score-numerator (* len (1+ score-denominator))) str))
          str)
        completions))))
 
-- 
2.17.1


[-- Attachment #3: Type: text/plain, Size: 173 bytes --]


Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi João, hi Stefan,

Unfortunately, I found some bugs in the patch I shared above.  While it
works well for substring and flex completion (with the minor caveat of
ignoring the point’s position which I will take care of), it breaks
under vanilla PCM completion.  I will try to fix it.

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> Unfortunately, I found some bugs in the patch I shared above.  While it
> works well for substring and flex completion (with the minor caveat of
> ignoring the point’s position which I will take care of), it breaks
> under vanilla PCM completion.  I will try to fix it.

BTW, this code sorely needs tests, so when you find a bug (either in
the original code or in changes you introduced temporarily), if you
could add corresponding tests, that would be a great help.


        Stefan "yes, the very one to blame for the lack of those tests"

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

> BTW, this code sorely needs tests, so when you find a bug (either in
> the original code or in changes you introduced temporarily), if you
> could add corresponding tests, that would be a great help.

Hi Stefan, hi João,

Thanks a lot.  I managed to iron out the bugs in a way that I’m happy
with.  It seems to work well with everything I tested so far, and I went
ahead and added some tests.

Please have a look.


[-- Attachment #2: Fix (and optimize) scoring in PCM completion --]
[-- Type: text/x-diff, Size: 13910 bytes --]

From 21ca47a2208ed7e154d1110f74f12c63bdd28262 Mon Sep 17 00:00:00 2001
From: Dario Gjorgjevski <dario.gjorgjevski@gmail.com>
Date: Wed, 9 Sep 2020 12:10:52 +0200
Subject: [PATCH] Fix (and optimize) scoring in PCM completion
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* lisp/minibuffer.el (completion-pcm--hilit-commonality): Fix scoring
to also include the last part of the query string.  This was
especially evident for single-character query strings, e.g.,
‘(completion-flex-all-completions "1" '("1" "foo1") nil 1)’ would
match both "1" and "foo1" with a completion-score of 0.  This
adjustment makes the completion-score of "1" be 1 and of "foo1" by
0.25.  Furthermore, fix ‘completions-first-difference’ and
‘completions-common-part’ sometimes overlapping.  See also bug#42149.
Furthermore, some optimizations are done.

(completion-pcm--optimize-pattern): Turn all terminating symbols,
instead of only ‘point’, into an implicit ‘any’.  This removes
trailing holes which affect the scoring adversely when someone is,
e.g., completing “li-pac*” with PCM completion.

(completion-pcm--count-leading-holes): New function.

(completion-pcm--match-size): New function.

* test/lisp/minibuffer-tests.el (completion-pcm-all-completions-test,
completion-substring-all-completions-test,
completion-flex-all-completions-test): Regression tests.
---
 lisp/minibuffer.el            | 112 +++++++++++++++++-------------
 test/lisp/minibuffer-tests.el | 127 ++++++++++++++++++++++++++++++++++
 2 files changed, 191 insertions(+), 48 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 62a33f3e2d..33e0bc67a2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3104,13 +3104,15 @@ or a symbol, see `completion-pcm--merge-completions'."
     (while p
       (pcase p
         (`(,(or 'any 'any-delim) point . ,rest) (setq p `(point . ,rest)))
-        ;; This is not just a performance improvement: it also turns
-        ;; a terminating `point' into an implicit `any', which
-        ;; affects the final position of point (because `point' gets
-        ;; turned into a non-greedy ".*?" regexp whereas we need
-        ;; it the be greedy when it's at the end, see bug#38458).
-        (`(,(pred symbolp)) (setq p nil)) ;Implicit terminating `any'.
         (_ (push (pop p) n))))
+    ;; Remove terminating symbols at the end and turn them into an
+    ;; implicit `any'.  This is not just a performance improvement: it
+    ;; also turns a terminating `point' into an implicit `any', which
+    ;; affects the final position of point (because `point' gets
+    ;; turned into a non-greedy ".*?" regexp whereas we need it the be
+    ;; greedy when it's at the end, see bug#38458).
+    (while (and n (symbolp (car n)))
+      (pop n))
     (nreverse n)))
 
 (defun completion-pcm--pattern->regex (pattern &optional group)
@@ -3187,21 +3189,32 @@ one large \"hole\" and a clumped-together \"oo\" match) higher
 than the latter (which has two \"holes\" and three
 one-letter-long matches).")
 
+(defun completion-pcm--count-leading-holes (pattern)
+  "Count the number of leading holes in PATTERN."
+  (length (seq-take-while #'symbolp pattern)))
+
+(defun completion-pcm--match-size (pattern)
+  "Return the match size of PATTERN."
+  (apply #'+
+         (mapcar
+          (lambda (part) (if (stringp part) (length part) 0))
+          pattern)))
+
 (defun completion-pcm--hilit-commonality (pattern completions)
   (when completions
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
-           (case-fold-search completion-ignore-case))
+           (case-fold-search completion-ignore-case)
+           (num-leading-holes (completion-pcm--count-leading-holes pattern))
+           (score-numerator (float (completion-pcm--match-size pattern))))
       (mapcar
        (lambda (str)
-	 ;; Don't modify the string itself.
+         ;; Don't modify the string itself.
          (setq str (copy-sequence str))
          (unless (string-match re str)
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
                 (md (match-data))
-                (start (pop md))
-                (end (pop md))
                 (len (length str))
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
@@ -3237,47 +3250,50 @@ one-letter-long matches).")
                 ;;    (SUM_across_i(hole_i_contrib) + 1) * len
                 ;;
                 ;; , where "len" is the string's length.
-                (score-numerator 0)
+                (full-match-start (pop md))
+                (full-match-end (pop md))
+                (match-start)
                 (score-denominator 0)
-                (last-b 0)
-                (update-score
-                 (lambda (a b)
-                   "Update score variables given match range (A B)."
-                   (setq
-                    score-numerator   (+ score-numerator (- b a)))
-                   (unless (or (= a last-b)
-                               (zerop last-b)
-                               (= a (length str)))
-                     (setq
-                      score-denominator (+ score-denominator
-                                           1
-                                           (expt (- a last-b 1)
-                                                 (/ 1.0
-                                                    flex-score-match-tightness)))))
-                   (setq
-                    last-b              b))))
-           (funcall update-score start start)
+                (hilit (lambda (match-start match-end)
+                         (add-face-text-property
+                          match-start match-end
+                          'completions-common-part
+                          nil str)
+                         ;; Maybe move `pos' away so we don not end up
+                         ;; putting `completions-first-difference' over
+                         ;; text that actually matches.
+                         (when (and (>= pos match-start) (< pos match-end))
+                           (setq pos match-end)))))
+           ;; Make sure that leading holes are explicitly discarded.
+           ;; Trailing holes are taken care of by
+           ;; `completion-pcm--optimize-pattern'.
+           (if (zerop num-leading-holes)
+               (setq match-start full-match-start)
+             (dotimes (_ (1- (* 2 num-leading-holes)))
+               (pop md))
+             (setq match-start (pop md)))
            (while md
-             (funcall update-score start (car md))
+             (let ((hole-start (pop md))
+                   (hole-end (pop md)))
+               (funcall hilit match-start hole-start)
+               (unless (= hole-start hole-end)
+                 (setq
+                  score-denominator (+ score-denominator
+                                       1
+                                       (expt
+                                        (- hole-end hole-start 1)
+                                        (/ 1.0 flex-score-match-tightness)))))
+               (setq match-start hole-end)))
+           (funcall hilit match-start full-match-end)
+           (when (> len pos)
              (add-face-text-property
-              start (pop md)
-              'completions-common-part
-              nil str)
-             (setq start (pop md)))
-           (funcall update-score len len)
-           (add-face-text-property
-            start end
-            'completions-common-part
-            nil str)
-           (if (> (length str) pos)
-               (add-face-text-property
-                pos (1+ pos)
-                'completions-first-difference
-                nil str))
-           (unless (zerop (length str))
-             (put-text-property
-              0 1 'completion-score
-              (/ score-numerator (* len (1+ score-denominator)) 1.0) str)))
+              pos (1+ pos)
+              'completions-first-difference
+              nil str))
+           (put-text-property
+            0 1
+            'completion-score
+            (/ score-numerator (* len (1+ score-denominator))) str))
          str)
        completions))))
 
diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index 5da86f3614..a473fec441 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -104,5 +104,132 @@
                                                 nil (length input))
                      (cons output (length output)))))))
 
+(ert-deftest completion-pcm-all-completions-test ()
+  ;; Point is at end, this does not match anything
+  (should (equal
+           (completion-pcm-all-completions
+            "foo" '("hello" "world" "barfoobar") nil 3)
+           nil))
+  ;; Point is at beginning, this matches "barfoobar"
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 0))
+           "barfoobar"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; One fourth of a match and no match due to point being at the end
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "RO" '("RaOb") nil 1)))
+           (/ 1.0 4.0)))
+  (should (equal
+           (completion-pcm-all-completions
+            "RO" '("RaOb") nil 2)
+           nil))
+  ;; Point is at beginning, but `completions-first-difference' is
+  ;; moved after it
+  (should (equal
+           (get-text-property
+            1 'face
+            (car (completion-pcm-all-completions
+                  "f" '("few" "many") nil 0)))
+           'completions-first-difference))
+  ;; Wildcards and delimiters work
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("list-packages") nil 7))
+           "list-packages"))
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("do-not-list-packages") nil 7))
+           nil)))
+
+(ert-deftest completion-substring-all-completions-test ()
+  ;; One third of a match!
+  (should (equal
+           (car (completion-substring-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 3))
+           "barfoobar"))
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "foo" '("hello" "world" "barfoobar") nil 3)))
+           (/ 1.0 3.0)))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Substring match
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 4))
+           "customize-group"))
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 5))
+           nil))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjobstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 3)))
+           'completions-first-difference)))
+
+(ert-deftest completion-flex-all-completions-test ()
+  ;; Fuzzy match
+  (should (equal
+           (car (completion-flex-all-completions
+                 "foo" '("hello" "world" "fabrobazo") nil 3))
+           "fabrobazo"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-flex-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Another fuzzy match, but more of a "substring" one
+  (should (equal
+           (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4))
+           "customize-group-other-window"))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            15 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 9)))
+           'completions-first-difference)))
+
 (provide 'completion-tests)
 ;;; completion-tests.el ends here
-- 
2.17.1


[-- Attachment #3: Type: text/plain, Size: 173 bytes --]


Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi Stefan, hi João,

I rebased my patch on top of the fix introduced for bug#41705 and
confirmed that it does not cause a regression.  Have you been able to
look into it?  Please let me know if you think there’s something missing
or if I should add additional tests.

I am attaching the patch below.


[-- Attachment #2: Fix (and optimize) scoring in PCM completion --]
[-- Type: text/x-diff, Size: 13013 bytes --]

From e1d07804aeb155a5ff3b6a1c410ec757269a43d3 Mon Sep 17 00:00:00 2001
From: Dario Gjorgjevski <dario.gjorgjevski@gmail.com>
Date: Wed, 14 Oct 2020 10:06:40 +0200
Subject: [PATCH] Fix (and optimize) scoring in PCM completion
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* lisp/minibuffer.el (completion-pcm--hilit-commonality): Fix scoring
to also include the last part of the query string.  This was
especially evident for single-character query strings, e.g.,
‘(completion-flex-all-completions "1" '("1" "foo1") nil 1)’ would
match both "1" and "foo1" with a completion-score of 0.  This
adjustment makes the completion-score of "1" be 1 and of "foo1" by
0.25.  Furthermore, fix ‘completions-first-difference’ and
‘completions-common-part’ sometimes overlapping.  See also bug#42149.
Furthermore, some optimizations are done.

(completion-pcm--optimize-pattern): Turn multiple consecutive
occurrences of ‘any’ into just a single one.

(completion-pcm--count-leading-holes): New function.

(completion-pcm--match-size): New function.

* test/lisp/minibuffer-tests.el (completion-pcm-all-completions-test,
completion-substring-all-completions-test,
completion-flex-all-completions-test): Regression tests.
---
 lisp/minibuffer.el            |  99 +++++++++++++++-----------
 test/lisp/minibuffer-tests.el | 127 ++++++++++++++++++++++++++++++++++
 2 files changed, 184 insertions(+), 42 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 427636e866..38bb4d0785 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3110,6 +3110,7 @@ or a symbol, see `completion-pcm--merge-completions'."
     (while p
       (pcase p
         (`(,(or 'any 'any-delim) point . ,rest) (setq p `(point . ,rest)))
+	(`(any any . ,rest) (setq p `(any . ,rest)))
         ;; This is not just a performance improvement: it turns a
         ;; terminating `point' into an implicit `any', which affects
         ;; the final position of point (because `point' gets turned
@@ -3193,21 +3194,32 @@ one large \"hole\" and a clumped-together \"oo\" match) higher
 than the latter (which has two \"holes\" and three
 one-letter-long matches).")
 
+(defun completion-pcm--count-leading-holes (pattern)
+  "Count the number of leading holes in PATTERN."
+  (length (seq-take-while #'symbolp pattern)))
+
+(defun completion-pcm--match-size (pattern)
+  "Return the match size of PATTERN."
+  (apply #'+
+         (mapcar
+          (lambda (part) (if (stringp part) (length part) 0))
+          pattern)))
+
 (defun completion-pcm--hilit-commonality (pattern completions)
   (when completions
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
-           (case-fold-search completion-ignore-case))
+           (case-fold-search completion-ignore-case)
+           (num-leading-holes (completion-pcm--count-leading-holes pattern))
+           (score-numerator (float (completion-pcm--match-size pattern))))
       (mapcar
        (lambda (str)
-	 ;; Don't modify the string itself.
+         ;; Don't modify the string itself.
          (setq str (copy-sequence str))
          (unless (string-match re str)
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
                 (md (match-data))
-                (start (pop md))
-                (end (pop md))
                 (len (length str))
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
@@ -3243,47 +3255,50 @@ one-letter-long matches).")
                 ;;    (SUM_across_i(hole_i_contrib) + 1) * len
                 ;;
                 ;; , where "len" is the string's length.
-                (score-numerator 0)
+                (full-match-start (pop md))
+                (full-match-end (pop md))
+                (match-start)
                 (score-denominator 0)
-                (last-b 0)
-                (update-score
-                 (lambda (a b)
-                   "Update score variables given match range (A B)."
-                   (setq
-                    score-numerator   (+ score-numerator (- b a)))
-                   (unless (or (= a last-b)
-                               (zerop last-b)
-                               (= a (length str)))
-                     (setq
-                      score-denominator (+ score-denominator
-                                           1
-                                           (expt (- a last-b 1)
-                                                 (/ 1.0
-                                                    flex-score-match-tightness)))))
-                   (setq
-                    last-b              b))))
-           (funcall update-score start start)
+                (hilit (lambda (match-start match-end)
+                         (add-face-text-property
+                          match-start match-end
+                          'completions-common-part
+                          nil str)
+                         ;; Maybe move `pos' away so we don not end up
+                         ;; putting `completions-first-difference' over
+                         ;; text that actually matches.
+                         (when (and (>= pos match-start) (< pos match-end))
+                           (setq pos match-end)))))
+           ;; Make sure that leading holes are explicitly discarded.
+           ;; Trailing holes are taken care of by
+           ;; `completion-pcm--optimize-pattern'.
+           (if (zerop num-leading-holes)
+               (setq match-start full-match-start)
+             (dotimes (_ (1- (* 2 num-leading-holes)))
+               (pop md))
+             (setq match-start (pop md)))
            (while md
-             (funcall update-score start (car md))
+             (let ((hole-start (pop md))
+                   (hole-end (pop md)))
+               (funcall hilit match-start hole-start)
+               (unless (= hole-start hole-end)
+                 (setq
+                  score-denominator (+ score-denominator
+                                       1
+                                       (expt
+                                        (- hole-end hole-start 1)
+                                        (/ 1.0 flex-score-match-tightness)))))
+               (setq match-start hole-end)))
+           (funcall hilit match-start full-match-end)
+           (when (> len pos)
              (add-face-text-property
-              start (pop md)
-              'completions-common-part
-              nil str)
-             (setq start (pop md)))
-           (funcall update-score len len)
-           (add-face-text-property
-            start end
-            'completions-common-part
-            nil str)
-           (if (> (length str) pos)
-               (add-face-text-property
-                pos (1+ pos)
-                'completions-first-difference
-                nil str))
-           (unless (zerop (length str))
-             (put-text-property
-              0 1 'completion-score
-              (/ score-numerator (* len (1+ score-denominator)) 1.0) str)))
+              pos (1+ pos)
+              'completions-first-difference
+              nil str))
+           (put-text-property
+            0 1
+            'completion-score
+            (/ score-numerator (* len (1+ score-denominator))) str))
          str)
        completions))))
 
diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index 5da86f3614..a473fec441 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -104,5 +104,132 @@
                                                 nil (length input))
                      (cons output (length output)))))))
 
+(ert-deftest completion-pcm-all-completions-test ()
+  ;; Point is at end, this does not match anything
+  (should (equal
+           (completion-pcm-all-completions
+            "foo" '("hello" "world" "barfoobar") nil 3)
+           nil))
+  ;; Point is at beginning, this matches "barfoobar"
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 0))
+           "barfoobar"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; One fourth of a match and no match due to point being at the end
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "RO" '("RaOb") nil 1)))
+           (/ 1.0 4.0)))
+  (should (equal
+           (completion-pcm-all-completions
+            "RO" '("RaOb") nil 2)
+           nil))
+  ;; Point is at beginning, but `completions-first-difference' is
+  ;; moved after it
+  (should (equal
+           (get-text-property
+            1 'face
+            (car (completion-pcm-all-completions
+                  "f" '("few" "many") nil 0)))
+           'completions-first-difference))
+  ;; Wildcards and delimiters work
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("list-packages") nil 7))
+           "list-packages"))
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("do-not-list-packages") nil 7))
+           nil)))
+
+(ert-deftest completion-substring-all-completions-test ()
+  ;; One third of a match!
+  (should (equal
+           (car (completion-substring-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 3))
+           "barfoobar"))
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "foo" '("hello" "world" "barfoobar") nil 3)))
+           (/ 1.0 3.0)))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Substring match
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 4))
+           "customize-group"))
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 5))
+           nil))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjobstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 3)))
+           'completions-first-difference)))
+
+(ert-deftest completion-flex-all-completions-test ()
+  ;; Fuzzy match
+  (should (equal
+           (car (completion-flex-all-completions
+                 "foo" '("hello" "world" "fabrobazo") nil 3))
+           "fabrobazo"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-flex-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Another fuzzy match, but more of a "substring" one
+  (should (equal
+           (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4))
+           "customize-group-other-window"))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            15 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 9)))
+           'completions-first-difference)))
+
 (provide 'completion-tests)
 ;;; completion-tests.el ends here
-- 
2.17.1


[-- Attachment #3: Type: text/plain, Size: 173 bytes --]


Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

Hi Dario,

Sorry for the delay in handling this.

I haven't had time to look into it in detail, which I must do since
it is reasonably complex.  However it looks good on the surface
and from what I remember your original bug report holds water.

I have two questions and a nitpick:

1. Question: if I compile and/or evaluate the changes to the
test/lisp/minibuffer-tests.el file but _don't_ compile the changes
to the lisp/minibuffer.el file, will they expose this bug and this
bug only?  In other words, will I get exactly the same failures
that you describe originally in this issue and will that fact be
apparent in the failure message(s)?

2. Question: are the changes to completion-pcm--optimize-pattern
an optimization or does the fix above depend on them?  If the
former, could you make it a separate commit?

3. Nitpick: the commit message is broadly according to the
format, but I find it hard to parse its intentions. Though
conventions vary, I usually like to format the commit message
like in this example which separates the what, the why and
the how.

"Fix the thing imperatively because racecar (bug#12345)

Before, when the user did foo the system stupidly behaved
bar. Now it's much better, it does baz.

I fixed this by doing quux and quzz

* file (function): use more intense quuxing."

João

[-- Attachment #2: Type: text/html, Size: 1874 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi João,

> Sorry for the delay in handling this.

No problem; it’s not a very critical bug after all, just an annoying
one.

> 1. Question: if I compile and/or evaluate the changes to the
> test/lisp/minibuffer-tests.el file but _don't_ compile the changes
> to the lisp/minibuffer.el file, will they expose this bug and this
> bug only?  In other words, will I get exactly the same failures
> that you describe originally in this issue and will that fact be
> apparent in the failure message(s)?

Yes.  As for how apparent they’ll be, well, I guess that’s up to ERT.
You will get something along the lines of

    (ert-test-failed
     ((should
       (eql
	(get-text-property 0 'completion-score
			   (car ...))
	1.0))
      :form
      (eql 0.0 1.0)
      :value nil))

Which says that the ‘completion-score’ was 0 but should have been 1, as
indicated in the bug report.  Of course, some of the tests are more
general tests for the sake of catching regressions.

> 2. Question: are the changes to completion-pcm--optimize-pattern
> an optimization or does the fix above depend on them?  If the
> former, could you make it a separate commit?

Unfortunately, the fix loosely depends on them.  Without them, having
multiple consecutive “*” would mess up the PCM scoring.

> 3. Nitpick: the commit message is broadly according to the
> format, but I find it hard to parse its intentions. Though
> conventions vary, I usually like to format the commit message
> like in this example which separates the what, the why and
> the how.

Thanks for both the remark and the useful example.  I will fix it and
come back with a new patch.

Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi João, hi Stefan,

Please find attached a patch with an edited commit message.  It should
be better.


[-- Attachment #2: Fix PCM scoring ignoring last part of query string --]
[-- Type: text/x-diff, Size: 13455 bytes --]

From 59c4b64e830bef4258dba06e77e674f33b603918 Mon Sep 17 00:00:00 2001
From: Dario Gjorgjevski <dario.gjorgjevski@gmail.com>
Date: Wed, 14 Oct 2020 10:06:40 +0200
Subject: [PATCH] Fix PCM scoring ignoring last part of query string
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This issue is especially evident for single-character query strings,
e.g.,

  (completion-flex-all-completions "1" '("1" "foo1") nil 1)

would match both "1" and "foo1" with a completion score of 0, whereas
they should have completion scores of 1 and 0.25 respectively.  See
also bug#42149.

Furthermore, ‘completions-first-difference’ and
‘completions-common-part’ would sometimes overlap depending on the
position of point within the query string.

The former is fixed by correcting the part of
‘completion-pcm--hilit-commonality’ responsible for looping over the
holes in the query string.  The latter is fixed by explicitly moving
the position of ‘completions-first-difference’ in case an overlap with
‘completions-common-part’ is detected.

* lisp/minibuffer.el (completion-pcm--hilit-commonality): Correctly
loop over the holes in the query string; detect overlaps of
‘completions-first-difference’ with ‘completions-common-part’;
pre-compute the numerator.

(completion-pcm--optimize-pattern): Turn multiple consecutive
occurrences of ‘any’ into just a single one.

(completion-pcm--count-leading-holes): New function.

(completion-pcm--match-size): New function.

* test/lisp/minibuffer-tests.el (completion-pcm-all-completions-test,
completion-substring-all-completions-test,
completion-flex-all-completions-test): Regression tests.
---
 lisp/minibuffer.el            |  99 +++++++++++++++-----------
 test/lisp/minibuffer-tests.el | 127 ++++++++++++++++++++++++++++++++++
 2 files changed, 184 insertions(+), 42 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 427636e866..38bb4d0785 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3110,6 +3110,7 @@ or a symbol, see `completion-pcm--merge-completions'."
     (while p
       (pcase p
         (`(,(or 'any 'any-delim) point . ,rest) (setq p `(point . ,rest)))
+	(`(any any . ,rest) (setq p `(any . ,rest)))
         ;; This is not just a performance improvement: it turns a
         ;; terminating `point' into an implicit `any', which affects
         ;; the final position of point (because `point' gets turned
@@ -3193,21 +3194,32 @@ one large \"hole\" and a clumped-together \"oo\" match) higher
 than the latter (which has two \"holes\" and three
 one-letter-long matches).")
 
+(defun completion-pcm--count-leading-holes (pattern)
+  "Count the number of leading holes in PATTERN."
+  (length (seq-take-while #'symbolp pattern)))
+
+(defun completion-pcm--match-size (pattern)
+  "Return the match size of PATTERN."
+  (apply #'+
+         (mapcar
+          (lambda (part) (if (stringp part) (length part) 0))
+          pattern)))
+
 (defun completion-pcm--hilit-commonality (pattern completions)
   (when completions
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
-           (case-fold-search completion-ignore-case))
+           (case-fold-search completion-ignore-case)
+           (num-leading-holes (completion-pcm--count-leading-holes pattern))
+           (score-numerator (float (completion-pcm--match-size pattern))))
       (mapcar
        (lambda (str)
-	 ;; Don't modify the string itself.
+         ;; Don't modify the string itself.
          (setq str (copy-sequence str))
          (unless (string-match re str)
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
                 (md (match-data))
-                (start (pop md))
-                (end (pop md))
                 (len (length str))
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
@@ -3243,47 +3255,50 @@ one-letter-long matches).")
                 ;;    (SUM_across_i(hole_i_contrib) + 1) * len
                 ;;
                 ;; , where "len" is the string's length.
-                (score-numerator 0)
+                (full-match-start (pop md))
+                (full-match-end (pop md))
+                (match-start)
                 (score-denominator 0)
-                (last-b 0)
-                (update-score
-                 (lambda (a b)
-                   "Update score variables given match range (A B)."
-                   (setq
-                    score-numerator   (+ score-numerator (- b a)))
-                   (unless (or (= a last-b)
-                               (zerop last-b)
-                               (= a (length str)))
-                     (setq
-                      score-denominator (+ score-denominator
-                                           1
-                                           (expt (- a last-b 1)
-                                                 (/ 1.0
-                                                    flex-score-match-tightness)))))
-                   (setq
-                    last-b              b))))
-           (funcall update-score start start)
+                (hilit (lambda (match-start match-end)
+                         (add-face-text-property
+                          match-start match-end
+                          'completions-common-part
+                          nil str)
+                         ;; Maybe move `pos' away so we don not end up
+                         ;; putting `completions-first-difference' over
+                         ;; text that actually matches.
+                         (when (and (>= pos match-start) (< pos match-end))
+                           (setq pos match-end)))))
+           ;; Make sure that leading holes are explicitly discarded.
+           ;; Trailing holes are taken care of by
+           ;; `completion-pcm--optimize-pattern'.
+           (if (zerop num-leading-holes)
+               (setq match-start full-match-start)
+             (dotimes (_ (1- (* 2 num-leading-holes)))
+               (pop md))
+             (setq match-start (pop md)))
            (while md
-             (funcall update-score start (car md))
+             (let ((hole-start (pop md))
+                   (hole-end (pop md)))
+               (funcall hilit match-start hole-start)
+               (unless (= hole-start hole-end)
+                 (setq
+                  score-denominator (+ score-denominator
+                                       1
+                                       (expt
+                                        (- hole-end hole-start 1)
+                                        (/ 1.0 flex-score-match-tightness)))))
+               (setq match-start hole-end)))
+           (funcall hilit match-start full-match-end)
+           (when (> len pos)
              (add-face-text-property
-              start (pop md)
-              'completions-common-part
-              nil str)
-             (setq start (pop md)))
-           (funcall update-score len len)
-           (add-face-text-property
-            start end
-            'completions-common-part
-            nil str)
-           (if (> (length str) pos)
-               (add-face-text-property
-                pos (1+ pos)
-                'completions-first-difference
-                nil str))
-           (unless (zerop (length str))
-             (put-text-property
-              0 1 'completion-score
-              (/ score-numerator (* len (1+ score-denominator)) 1.0) str)))
+              pos (1+ pos)
+              'completions-first-difference
+              nil str))
+           (put-text-property
+            0 1
+            'completion-score
+            (/ score-numerator (* len (1+ score-denominator))) str))
          str)
        completions))))
 
diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index 5da86f3614..a473fec441 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -104,5 +104,132 @@
                                                 nil (length input))
                      (cons output (length output)))))))
 
+(ert-deftest completion-pcm-all-completions-test ()
+  ;; Point is at end, this does not match anything
+  (should (equal
+           (completion-pcm-all-completions
+            "foo" '("hello" "world" "barfoobar") nil 3)
+           nil))
+  ;; Point is at beginning, this matches "barfoobar"
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 0))
+           "barfoobar"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; One fourth of a match and no match due to point being at the end
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "RO" '("RaOb") nil 1)))
+           (/ 1.0 4.0)))
+  (should (equal
+           (completion-pcm-all-completions
+            "RO" '("RaOb") nil 2)
+           nil))
+  ;; Point is at beginning, but `completions-first-difference' is
+  ;; moved after it
+  (should (equal
+           (get-text-property
+            1 'face
+            (car (completion-pcm-all-completions
+                  "f" '("few" "many") nil 0)))
+           'completions-first-difference))
+  ;; Wildcards and delimiters work
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("list-packages") nil 7))
+           "list-packages"))
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("do-not-list-packages") nil 7))
+           nil)))
+
+(ert-deftest completion-substring-all-completions-test ()
+  ;; One third of a match!
+  (should (equal
+           (car (completion-substring-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 3))
+           "barfoobar"))
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "foo" '("hello" "world" "barfoobar") nil 3)))
+           (/ 1.0 3.0)))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Substring match
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 4))
+           "customize-group"))
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 5))
+           nil))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjobstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 3)))
+           'completions-first-difference)))
+
+(ert-deftest completion-flex-all-completions-test ()
+  ;; Fuzzy match
+  (should (equal
+           (car (completion-flex-all-completions
+                 "foo" '("hello" "world" "fabrobazo") nil 3))
+           "fabrobazo"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-flex-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Another fuzzy match, but more of a "substring" one
+  (should (equal
+           (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4))
+           "customize-group-other-window"))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            15 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 9)))
+           'completions-first-difference)))
+
 (provide 'completion-tests)
 ;;; completion-tests.el ends here
-- 
2.17.1


[-- Attachment #3: Type: text/plain, Size: 173 bytes --]


Best regards,
Dario

-- 
dario.gjorgjevski@gmail.com :: +49 1525 8666837
%   gpg --keyserver 'hkps://hkps.pool.sks-keyservers.net' \
\`>     --recv-keys '744A4F0B4F1C9371'

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Just a friendly bump.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

Indeed, sometimes a bump is needed.  I'll have a good look
as soon as possible.

João

On Fri, Nov 20, 2020 at 8:39 PM Dario Gjorgjevski <
dario.gjorgjevski@gmail.com> wrote:

> Just a friendly bump.
>
> Best regards,
> Dario
>
> --
> $ keyserver=hkps://hkps.pool.sks-keyservers.net
> $ keyid=744A4F0B4F1C9371
> $ gpg --keyserver $keyserver --search-keys $keyid
>


-- 
João Távora

[-- Attachment #2: Type: text/html, Size: 906 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

Hi Dario,

I took a better look at your patch finally, but I still
don't understand it fully.

Don't worry, I will soon.  First thing I looked at
was the tests you provided, which are very welcome.
I restructured them, creating instead 13 small tests
instead of just 3 tests that currently fail.

Like this I can see exactly what's failing and what's
not.  6 of the new tests fail, 7 pass.

Tomorrow I'll look at your patch and why it (probably)
fixes the 6 failures.

The branch I'm doing this work in is called:

scratch/bug-42149-funny-pcm-completion-scores

I'm the author of one of the commits there and credit
you as "Co-author".  If you'd rather reverse that, let
me know.

João

On Fri, Nov 20, 2020 at 9:27 PM João Távora <joaotavora@gmail.com> wrote:

> Indeed, sometimes a bump is needed.  I'll have a good look
> as soon as possible.
>
> João
>
> On Fri, Nov 20, 2020 at 8:39 PM Dario Gjorgjevski <
> dario.gjorgjevski@gmail.com> wrote:
>
>> Just a friendly bump.
>>
>> Best regards,
>> Dario
>>
>> --
>> $ keyserver=hkps://hkps.pool.sks-keyservers.net
>> $ keyid=744A4F0B4F1C9371
>> $ gpg --keyserver $keyserver --search-keys $keyid
>>
>
>
> --
> João Távora
>


-- 
João Távora

[-- Attachment #2: Type: text/html, Size: 2388 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi João,

> I took a better look at your patch finally, but I still
> don't understand it fully.

Thanks a lot.  I think the best way to see what’s going on is to take
the ‘completion-pcm--hilit-commonality’ function and, ironically, do
some printf() debugging.  In the current implementation, if you insert

  (message "String: %s" str)            in the initial lambda and
  (message "Found match [%d, %d]" a b)  in ‘update-score’

and then you try the example from the comments

  (completion-flex-all-completions
   "foo" '("fabrobazo" "fbarbazoo" "barfoobaz") nil 3)

you will see it prints

  String: fabrobazo
  Found match [0, 0] [2 times]
  Found match [0, 1]
  Found match [4, 5]
  Found match [9, 9]
  String: fbarbazoo
  Found match [0, 0] [2 times]
  Found match [0, 1]
  Found match [7, 8]
  Found match [9, 9]
  String: barfoobaz
  Found match [0, 0] [2 times]
  Found match [3, 4]
  Found match [4, 5]
  Found match [9, 9]

Notice how the last matching character is *not processed* -- this is the
essence of the bug.  It’s easiest to see from ‘barfoobaz’ where only [3,
4] (the ‘f’) and [4, 5] (the second ‘o’) are processed, [5, 6] is
nowhere to be seen.

With my patch, the output becomes

String: foobarbaz
Found match [0, 1]
Found match [1, 2]
Found match [2, 3]
String: fbarbazoo
Found match [0, 1]
Found match [7, 8]
Found match [8, 9]
String: barfoobaz
Found match [3, 4]
Found match [4, 5]
Found match [5, 6]

Which is all good.

> Don't worry, I will soon.  First thing I looked at
> was the tests you provided, which are very welcome.
> I restructured them, creating instead 13 small tests
> instead of just 3 tests that currently fail.

Thanks a lot once again, this is very appreciated.  Admittedly, the
tests weren’t very good and I wasn’t sure how to make them better.

> I'm the author of one of the commits there and credit
> you as "Co-author".  If you'd rather reverse that, let
> me know.

This is fine by me.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

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

On Wed, Nov 25, 2020 at 8:22 AM Dario Gjorgjevski <
dario.gjorgjevski@gmail.com> wrote:

> > Don't worry, I will soon.  First thing I looked at
> > was the tests you provided, which are very welcome.
> > I restructured them, creating instead 13 small tests
> > instead of just 3 tests that currently fail.
> Thanks a lot once again, this is very appreciated.  Admittedly, the
> tests weren’t very good and I wasn’t sure how to make them better.

Maybe you misunderstood me. I didn't write any new tests, I used
your code and split it up into multiple ert-deftests so that I could get
a better idea of which assertions are failing.  The tests you wrote
seem decent (but if you have even better ones, I'm OK with that
too :-) )

João

[-- Attachment #2: Type: text/html, Size: 969 bytes --]

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

> Maybe you misunderstood me. I didn't write any new tests, I used
> your code and split it up into multiple ert-deftests so that I could get
> a better idea of which assertions are failing.  The tests you wrote
> seem decent (but if you have even better ones, I'm OK with that
> too :-) )

What I meant was bad about the tests I had written is precisely what you
fixed -- the way they were structured.  So, all is good.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi,

Has anyone had the time to look into this?

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

> Hi,
>
> Has anyone had the time to look into this?
>
> Best regards,
> Dario

Hi Dario,

After a long long delay, I've now looked at this in earnest.

I can report that I think the problem lies somewhere completely
different than what I think you patch addresses.  Instead of reworking

    completion-pcm--hilit-commonality   [1]

I think we should take a better look at
completion-pcm--optimize-pattern.  In its current form, it will thus
"optimize" the pcm patterns like so:

1 -> (completion-pcm--optimize-pattern (prefix "f" any point))
1 <- completion-pcm--optimize-pattern: (prefix "f")

whereas I think it shouldn't be optimizing away the "any".  When I make
it keep the any with this simple patch, _most_ of your tests start
passing becasue completion-pcm--hilit-commonality starts doing the right
thing, i.e. it starts working the way it was intented to work,
considering a (potentially empty) hole in the back of the pattern form.

This is that simple patch:

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 7d05f7704e..637a29eaa0 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3165,7 +3165,7 @@ completion-pcm--optimize-pattern
         ;; the final position of point (because `point' gets turned
         ;; into a non-greedy ".*?" regexp whereas we need it to be
         ;; greedy when it's at the end, see bug#38458).
-        (`(point) (setq p nil)) ;Implicit terminating `any'.
+        (`(point) (setq p '(any)))  ;Implicit terminating `any'.
         (_ (push (pop p) n))))
     (nreverse n)))

However, I'm pretty sure Stefan will tell us to hold our horses with any
changes to this, since it's used in many more mysterious ways that I
can't fathom.

So, maybe this is a smaller, safer change:

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 7d05f7704e..cc2573db19 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3245,6 +3245,8 @@ flex-score-match-tightness
 
 (defun completion-pcm--hilit-commonality (pattern completions)
   (when completions
+    (unless (eq (car (last pattern)) 'any)
+      (setq pattern (append pattern '(any))))
     (let* ((re (completion-pcm--pattern->regex pattern 'group))
            (point-idx (completion-pcm--pattern-point-idx pattern))
            (case-fold-search completion-ignore-case))

[1]: completion-pcm--hilit-commonality, which does seem to have a couple
of superflous calls to the update-score local function)

[2]: please Stefan: remind me for the 1000th time what "pcm" stands for

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

I'm sorry, I seem to have sent the previous reply prematurely.

However, there was not much more to add except my signature
and some more reporting on test results.

Thanks,
João

On Sun, Dec 27, 2020 at 8:08 PM João Távora <joaotavora@gmail.com> wrote:
>
> Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:
>
> > Hi,
> >
> > Has anyone had the time to look into this?
> >
> > Best regards,
> > Dario
>
> Hi Dario,
>
> After a long long delay, I've now looked at this in earnest.
>
> I can report that I think the problem lies somewhere completely
> different than what I think you patch addresses.  Instead of reworking
>
>     completion-pcm--hilit-commonality   [1]
>
> I think we should take a better look at
> completion-pcm--optimize-pattern.  In its current form, it will thus
> "optimize" the pcm patterns like so:
>
> 1 -> (completion-pcm--optimize-pattern (prefix "f" any point))
> 1 <- completion-pcm--optimize-pattern: (prefix "f")
>
> whereas I think it shouldn't be optimizing away the "any".  When I make
> it keep the any with this simple patch, _most_ of your tests start
> passing becasue completion-pcm--hilit-commonality starts doing the right
> thing, i.e. it starts working the way it was intented to work,
> considering a (potentially empty) hole in the back of the pattern form.
>
> This is that simple patch:
>
> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index 7d05f7704e..637a29eaa0 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -3165,7 +3165,7 @@ completion-pcm--optimize-pattern
>          ;; the final position of point (because `point' gets turned
>          ;; into a non-greedy ".*?" regexp whereas we need it to be
>          ;; greedy when it's at the end, see bug#38458).
> -        (`(point) (setq p nil)) ;Implicit terminating `any'.
> +        (`(point) (setq p '(any)))  ;Implicit terminating `any'.
>          (_ (push (pop p) n))))
>      (nreverse n)))
>
> However, I'm pretty sure Stefan will tell us to hold our horses with any
> changes to this, since it's used in many more mysterious ways that I
> can't fathom.
>
> So, maybe this is a smaller, safer change:
>
> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index 7d05f7704e..cc2573db19 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -3245,6 +3245,8 @@ flex-score-match-tightness
>
>  (defun completion-pcm--hilit-commonality (pattern completions)
>    (when completions
> +    (unless (eq (car (last pattern)) 'any)
> +      (setq pattern (append pattern '(any))))
>      (let* ((re (completion-pcm--pattern->regex pattern 'group))
>             (point-idx (completion-pcm--pattern-point-idx pattern))
>             (case-fold-search completion-ignore-case))
>
> [1]: completion-pcm--hilit-commonality, which does seem to have a couple
> of superflous calls to the update-score local function)
>
> [2]: please Stefan: remind me for the 1000th time what "pcm" stands for



-- 
João Távora

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> @@ -3165,7 +3165,7 @@ completion-pcm--optimize-pattern
>          ;; the final position of point (because `point' gets turned
>          ;; into a non-greedy ".*?" regexp whereas we need it to be
>          ;; greedy when it's at the end, see bug#38458).
> -        (`(point) (setq p nil)) ;Implicit terminating `any'.
> +        (`(point) (setq p '(any)))  ;Implicit terminating `any'.

There is always an implicit terminating `any`, and I'd really prefer to
keep it implicit.


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> Please find attached a patch with an edited commit message.  It should
> be better.

[ Boy, we are really unacceptably slow at reviewing this.  ]

Thanks very much for your patch.
It looks good to me, but I think it's important we find a fix with which
João agrees.

> Furthermore, ‘completions-first-difference’ and
> ‘completions-common-part’ would sometimes overlap depending on the
> position of point within the query string.

Could you point us at the corresponding test?
[ And thanks so much for the tests, this is great!  ]

> The former is fixed by correcting the part of
> ‘completion-pcm--hilit-commonality’ responsible for looping over the
> holes in the query string.

Is that done by treating the "leftover" from the string as if there was
an additional match?  That would correspond to the "implicit any"
that terminates every pattern.

> The latter is fixed by explicitly moving
> the position of ‘completions-first-difference’ in case an overlap with
> ‘completions-common-part’ is detected.

Did you (by any chance) figure out how/why the two end up overlapping?
The fix you're using looks pretty "hackish" and introduces a non-trivial
data flow for `pos`.  Before using such an ad-hoc solution it'd be best
to understand where the problem comes from (it might still be the
better answer in the end, but it's hard to judge).

> (completion-pcm--optimize-pattern): Turn multiple consecutive
> occurrences of ‘any’ into just a single one.

This is good (consecutive `any` can introduce serious performance bugs
because of our backtracing regexp matcher).
Other than improving performance, have you found other effects?

> +(defun completion-pcm--count-leading-holes (pattern)
> +  "Count the number of leading holes in PATTERN."
> +  (length (seq-take-while #'symbolp pattern)))

`seq-take-while` is not defined at this stage.
Either:
- (require 'seq), but that means `seq` will have to be preloaded,
  which will require negotiating with Eli.
- Mark `seq-take-while` with a `;;;###autoload` cookie so it'll be
  loaded on demand.
- Avoid using `seq-take-while` here.
I vote for the the 2nd option.

I think João knows the scoring algorithm much more than I do, so I'll
let him judge if the change is sound.


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> @@ -3165,7 +3165,7 @@ completion-pcm--optimize-pattern
>>          ;; the final position of point (because `point' gets turned
>>          ;; into a non-greedy ".*?" regexp whereas we need it to be
>>          ;; greedy when it's at the end, see bug#38458).
>> -        (`(point) (setq p nil)) ;Implicit terminating `any'.
>> +        (`(point) (setq p '(any)))  ;Implicit terminating `any'.
>
> There is always an implicit terminating `any`, and I'd really prefer to
> keep it implicit.

OK, but can you elaborate on why that is?

Regardless, if you don't want to touch that funciton, I understand, it
is used in more places than just completion-pcm--hilit-commonality,
which really should be called

   completion--given-that-we-know-this-matches-tell-me-where-and-how-well

(or maybe it should have a docstring, which I've done just now).

I propose something around this simpler patch.

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 7d05f7704e..df4ec67e35 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3255,10 +3255,10 @@ completion-pcm--hilit-commonality
          (unless (string-match re str)
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
-                (md (match-data))
-                (start (pop md))
-                (end (pop md))
+                (md (cddr (match-data)))
+                (start 0)
                 (len (length str))
+                (end len)
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
                 ;; flex-matches "fabrobazo", "fbarbazoo" and

It seems to be passing your original report, but still failing some of
your test assertions.  However, i don't know if I agree with those test
assertions.

This is one of them.

    (ert-deftest completion-pcm-test-3 ()
      ;; Full match!
      (should (eql
               (completion--pcm-score
                (car (completion-pcm-all-completions
                      "R" '("R" "hello") nil 1)))
               1.0)))

I still don't know why this misses, but I do know that the scoring part
of completion-pcm--hilit-commonality is not meant for the "bare" pcm
completion style or substring completion style.  It could, though.

I'll take a better look at those cases.

Anyway, I've pushed this simple fix (and some another fix to the test
cases) to the working branch:

     scratch/bug-42149-funny-pcm-completion-scores

which I've also rebased on top of origin/master by deleting/recreating.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Please find attached a patch with an edited commit message.  It should
>> be better.
>
> [ Boy, we are really unacceptably slow at reviewing this.  ]
>
> Thanks very much for your patch.
> It looks good to me, but I think it's important we find a fix with which
> João agrees.

Indeed, I'm very sorry to be a kill-joy here, the patch doesn't look
very good to me.  Last time I looked it was too complex for me to
follow, touches many lines, and created unnecessary consing.  I'm
convinced the current algorithm in completion-pcm--hilit-commonality is
fine for these 1-char edge cases, given that the assumptions hold.

>> Furthermore, ‘completions-first-difference’ and
>> ‘completions-common-part’ would sometimes overlap depending on the
>> position of point within the query string.
>
> Could you point us at the corresponding test?
> [ And thanks so much for the tests, this is great!  ]

Yes, please use the latest tests that I've pushed to the

   scratch/bug-42149-funny-pcm-completion-scores

branch.  They are still your test, only discriminated into various
ert-deftest.  If you want, you can split and discriminate further.

> I think João knows the scoring algorithm much more than I do, so I'll
> let him judge if the change is sound.

I'm not aware that it's not sound, but I do believe it's too complex and
not well understood.  In constrast, I can understand the three-line fix
I did earlier and which covers all of Darios's test cases for the flex
completion style.  Previously it was failing 7 cases, now it is only
failing these 3.

F completion-pcm-test-3
F completion-pcm-test-5
F completion-substring-test-4

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi Stefan,

> Thanks very much for your patch.
> It looks good to me, but I think it's important we find a fix with which
> João agrees.

Thanks likewise!

>> Furthermore, ‘completions-first-difference’ and
>> ‘completions-common-part’ would sometimes overlap depending on the
>> position of point within the query string.
>
> Could you point us at the corresponding test?

That would be the test

    ;; Point is at beginning, but `completions-first-difference' is
    ;; moved after it
    (should (equal
             (get-text-property
              1 'face
              (car (completion-pcm-all-completions
                    "f" '("few" "many") nil 0)))
             'completions-first-difference))

You can replace pcm with flex or substring, it doesn’t matter.

>> The former is fixed by correcting the part of
>> ‘completion-pcm--hilit-commonality’ responsible for looping over the
>> holes in the query string.
>
> Is that done by treating the "leftover" from the string as if there was
> an additional match?  That would correspond to the "implicit any"
> that terminates every pattern.

I believe the simplest way to summarize the issue with the current
implementation is that it assumes the regex match is of the form

    <hole><match><hole><match>...<hole>

(Where the <hole>s might be of length 0.)  However, the trailing <hole>
is not there and therefore the score is not updated correctly.
Furthermore, it does nothing to actually ensure these assumptions in the
presence of wildcards in the query string.

>> The latter is fixed by explicitly moving
>> the position of ‘completions-first-difference’ in case an overlap with
>> ‘completions-common-part’ is detected.
>
> Did you (by any chance) figure out how/why the two end up overlapping?
> The fix you're using looks pretty "hackish" and introduces a non-trivial
> data flow for `pos`.  Before using such an ad-hoc solution it'd be best
> to understand where the problem comes from (it might still be the
> better answer in the end, but it's hard to judge).

`completions-first-difference' is put at the first position after point
in the query string.  However, the part of the query string *after*
point might actually match there.  I don’t see an easier solution.

>> (completion-pcm--optimize-pattern): Turn multiple consecutive
>> occurrences of ‘any’ into just a single one.
>
> This is good (consecutive `any` can introduce serious performance bugs
> because of our backtracing regexp matcher).
> Other than improving performance, have you found other effects?

Yes, the presence of multiple consecutive wildcards invalidates the
aforementioned assumption of completion-pcm--hilit-commonality that the
match is of the form

    <hole><match><hole><match>...<hole>

>> +(defun completion-pcm--count-leading-holes (pattern)
>> +  "Count the number of leading holes in PATTERN."
>> +  (length (seq-take-while #'symbolp pattern)))
>
> `seq-take-while` is not defined at this stage.
> [...]
> - Mark `seq-take-while` with a `;;;###autoload` cookie so it'll be
>   loaded on demand.
> [...]

Good catch, this should indeed be done.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

Hi João,

> Indeed, I'm very sorry to be a kill-joy here, the patch doesn't look
> very good to me.

It’s all fine, however...

> Last time I looked it was too complex for me to follow, touches many
> lines, and created unnecessary consing.  I'm convinced the current
> algorithm in completion-pcm--hilit-commonality is fine for these
> 1-char edge cases, given that the assumptions hold.

I very much disagree with this due to 1. the test cases and 2. the
previous reply to Stefan where I tried to explain the shortcomings of
the current implementation of completion-pcm--hilit-commonality.  Also,
could you point to the unnecessary consing?  If anything, I believe my
patch is faster than the current implementation.

> I'm not aware that it's not sound, but I do believe it's too complex and
> not well understood.  In constrast, I can understand the three-line fix
> I did earlier and which covers all of Darios's test cases for the flex
> completion style.  Previously it was failing 7 cases, now it is only
> failing these 3.

Making the `any' explicit was also the very first thing I suggested, but
further testing pointed to problems it doesn’t solve, which are indeed
parts of the tests that are failing.  I can add more tests if you think
that would help.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

>> Last time I looked it was too complex for me to follow, touches many
>> lines, and created unnecessary consing.  I'm convinced the current
>> algorithm in completion-pcm--hilit-commonality is fine for these
>> 1-char edge cases, given that the assumptions hold.
>
> I very much disagree with this

My assertion that your solution is complex is comparative, of course,
not absolute.  It is _more_ complex that some other existing solution --
in this case my three-line solution -- and I say that because of the
factual observation that it changes much more than three lines,
introduces new code paths, etc.  

For now, I believe the original problem that started this bug report,
which dealt with flex and substring completion, is fixed by my patch.
Your failed user experience of typing "R" to perform "M-x R" should now
be correct, as far as I can tell.

Of course, you say your current patch fixes _more_ things, but I've yet
to understand what those presumably broken things are.  Perhaps once all
of this is understood we will come to the conclusion that your solution
is indeed the simplest possible.  Or perhaps we won't.

> due to 1. the test cases

The test cases should be independent of the implementation, so adding
more tests doesn't make the implemented solution any simpler.  It does
make solutions _simpler to simplify_, which is why I welcome tests.

However, tests themselves should map to real-world problems (you know,
the ones that you describe in terms of Emacs -Q reproduction recipes).
And I'm still having trouble understanding exactly what these are for
some tests.  But I'm spending time to work on that.

> 2. the  previous reply to Stefan where I tried to explain the shortcomings of
> the current implementation of completion-pcm--hilit-commonality.

I don't understand these shortcomings, yet.  I think they should be
evidenced more clearly, in terms of actual user-experienceable problems.

> Also, could you point to the unnecessary consing?

completion-pcm--count-leading-holes and completion-pcm--match-size both
add consing.  That is clear to see from their respective
implementations.  I don't know if they can be made non-consing, though I
suspect they can.  Anyway, using them as they are adds a small amount
consing.

> I believe my patch is faster than the current implementation.

Why do you believe that?  Do you have any benchmarks to demonstrate it?

>> I'm not aware that it's not sound, but I do believe it's too complex and
>> not well understood.  In constrast, I can understand the three-line fix
>> I did earlier and which covers all of Darios's test cases for the flex
>> completion style.  Previously it was failing 7 cases, now it is only
>> failing these 3.
>
> Making the `any' explicit was also the very first thing I suggested, but
> further testing pointed to problems it doesn’t solve, which are indeed
> parts of the tests that are failing.

My latest proposal doesn't make the any explicit.  I'll try to
understand what the intention is behind the tests that are failing.

> I can add more tests if you think that would help.

Yes, it would.  But any test that you add should bring about evidence of
a real-world problem.  I.e., to state the obvious but make my point clear,
the assertion:

    (should (eq 'foo 'bar))
    
fails spectacularly but doesn't bring about such evidence.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

> For now, I believe the original problem that started this bug report,
> which dealt with flex and substring completion, is fixed by my patch.
> Your failed user experience of typing "R" to perform "M-x R" should now
> be correct, as far as I can tell.

Sorry, but the branch bug-42149-funny-pcm-completion-scores doesn’t fix
any of that problem.

  (completion-flex-all-completions "R" '("R" "something-else-with-an-R")
                                   nil 1)

Will make both "R" and "something-else-with-an-R" get a completion-score
of 0, which is definitely not helping anything.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

>> For now, I believe the original problem that started this bug report,
>> which dealt with flex and substring completion, is fixed by my patch.
>> Your failed user experience of typing "R" to perform "M-x R" should now
>> be correct, as far as I can tell.
>
> Sorry, but the branch bug-42149-funny-pcm-completion-scores doesn’t fix
> any of that problem.
>
>   (completion-flex-all-completions "R" '("R" "something-else-with-an-R")
>                                    nil 1)
>
> Will make both "R" and "something-else-with-an-R" get a completion-score
> of 0, which is definitely not helping anything.

You're right.  I was a little too eager, and reported results on a
version that had another fix built it (a fix that is also simple and
reasonable, but which I haven't shown since it conses a little bit).

Anyway, the patch after my sig should fix it.  I'll push it later with
better comments, but it correctly identifies the presence or absence of
a trailing 'any in terms of the match-data, and corrects accordingly, in
terms of scoring.

It also fixes another one (I don't know which) of your tests.  Now only
two tests fail:

F completion-pcm-test-5
F completion-substring-test-4

I think we should focus on the meaning of these tests from here on.

Thanks,
João

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 4c912b5a34..eec0b3e09e 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3263,9 +3263,9 @@ completion-pcm--hilit-commonality
            (error "Internal error: %s does not match %s" re str))
          (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
                 (md (cddr (match-data)))
+                (match-end (cadr (match-data)))
                 (start 0)
-                (len (length str))
-                (end len)
+                (end (length str))
                 ;; To understand how this works, consider these bad
                 ;; ascii(tm) diagrams showing how the pattern "foo"
                 ;; flex-matches "fabrobazo", "fbarbazoo" and
@@ -3326,6 +3326,8 @@ completion-pcm--hilit-commonality
               'completions-common-part
               nil str)
              (setq start (pop md)))
+           (unless (= start match-end) ; ... which is t if we have trailing 'any
+             (funcall update-score start match-end))
            (add-face-text-property
             start end
             'completions-common-part
@@ -3338,7 +3340,7 @@ completion-pcm--hilit-commonality
            (unless (zerop (length str))
              (put-text-property
               0 1 'completion-score
-              (/ score-numerator (* len (1+ score-denominator)) 1.0) str)))
+              (/ score-numerator (* end (1+ score-denominator)) 1.0) str)))
          str)
        completions))))

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> This is one of them.
>
>     (ert-deftest completion-pcm-test-3 ()
>       ;; Full match!
>       (should (eql
>                (completion--pcm-score
>                 (car (completion-pcm-all-completions
>                       "R" '("R" "hello") nil 1)))
>                1.0)))

BTW, a good improvement to the tests would be to replace the score
equality tests with score ordering comparisons (like "score of foo >
score of bar") since it'd be perfectly OK to use a different scoring
system which gives different values as long as the relative ordering is
still obeyed.


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> Regardless, if you don't want to touch that funciton, I understand, it
> is used in more places than just completion-pcm--hilit-commonality,
> which really should be called
>
>    completion--given-that-we-know-this-matches-tell-me-where-and-how-well

Hmm... until someone™ added scoring to it, this function did nothing
more than add faces to highlight the common parts and the "first
difference".  So I'd suggest you take it up with that someone ;-)


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

>>> The latter is fixed by explicitly moving
>>> the position of ‘completions-first-difference’ in case an overlap with
>>> ‘completions-common-part’ is detected.
>>
>> Did you (by any chance) figure out how/why the two end up overlapping?
>> The fix you're using looks pretty "hackish" and introduces a non-trivial
>> data flow for `pos`.  Before using such an ad-hoc solution it'd be best
>> to understand where the problem comes from (it might still be the
>> better answer in the end, but it's hard to judge).
>
> `completions-first-difference' is put at the first position after point
> in the query string.

Oh, yes, I remember the problem is in the name: it is not really used to
highlight the first difference, but rather something like the "next
character to type" (which happens to be the first difference in the
simplest case of prefix completion).

In the example you show, I think overlapping *is* as good a behavior as
any other (and the code is careful to to replace one face with the other
but to actually put both faces there, so you get a bold-blue instead of
either bold or blue).  Moving the highlighting to the next character
like you've done seems actually worse in this case (e.g. if you're
completing ("f" . 0) against ("foo" "barfoo"), it's rather odd to
highlight the "b" of "barfoo" and the first "o" of "foo").

[ BTW, I notice that we have a bug currently in the highlighting:
  M-x for-s C-a ?
  correctly puts "for" and "s" in blue in the completion list, whereas
  M-x for C-a ?
  somehow fails to put "for" in blue :-(

>> This is good (consecutive `any` can introduce serious performance bugs
>> because of our backtracing regexp matcher).
>> Other than improving performance, have you found other effects?
>
> Yes, the presence of multiple consecutive wildcards invalidates the
> aforementioned assumption of completion-pcm--hilit-commonality that the
> match is of the form
>
>     <hole><match><hole><match>...<hole>

Makes sense, thank you.


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> This is one of them.
>>
>>     (ert-deftest completion-pcm-test-3 ()
>>       ;; Full match!
>>       (should (eql
>>                (completion--pcm-score
>>                 (car (completion-pcm-all-completions
>>                       "R" '("R" "hello") nil 1)))
>>                1.0)))
>
> BTW, a good improvement to the tests would be to replace the score
> equality tests with score ordering comparisons (like "score of foo >
> score of bar") since it'd be perfectly OK to use a different scoring
> system which gives different values as long as the relative ordering is
> still obeyed.

I'm not so sure I agree.  I mean, I agree with the general principle,
but I also think in our particular algorithm we can make some simple
guarantees about the absolute value of the computed score in such
trivial situations.  In this case, Dario's test asserts that a full and
perfect match has a score of 1 (hundred percent).  So the test is only
brittle if we break down this pillar, and I don't think we should.  At
least I don't think we have good reason to.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Regardless, if you don't want to touch that funciton, I understand, it
>> is used in more places than just completion-pcm--hilit-commonality,
>> which really should be called
>>
>>    completion--given-that-we-know-this-matches-tell-me-where-and-how-well
>
> Hmm... until someone™ added scoring to it, this function did nothing
> more than add faces to highlight the common parts and the "first
> difference".  So I'd suggest you take it up with that someone ;-)

:-)

Grumblebgrumpbl.  I kinda did, and so I added a docstring to it (have a
read).  Anyway, what's suprising about this function is that this
re-matches PATTERN to each of COMPLETIONS which is very odd to the
reader, becasue it also asserts that PATTERN already matches
COMPLETIONS.  Why are we regexp-matching twice?! -- asks the poor soul
reading this.

This comes down to completion-regexp-list being used by
Fall_completions() directly.  If that C function recorded the match data
in all the lisp strings it was passed, then completion--given-that...
would be easier follow.  And likely faster.  Though I haven't measured
the impact, sparing a regexp match against each completion might be
worth it in terms of responsiveness, especially in flex and similar
methods.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> `completions-first-difference' is put at the first position after point
>> in the query string.
>
> Oh, yes, I remember the problem is in the name: it is not really used to
> highlight the first difference, but rather something like the "next
> character to type" (which happens to be the first difference in the
> simplest case of prefix completion).
>
> In the example you show, I think overlapping *is* as good a behavior as
> any other (and the code is careful to to replace one face with the
> other

I agree with this general idea.  I think we have to be careful to write
tests in terms of user experience as much as possible.  For example, in
the very latest version of the code I pushed, I still have one of
Dario's original tests failing (down to only two now).

   completion-substring-test-4

Actually, only 1 of 3 of its assertions is failing (and this is an
argument for splitting it up further).  This is that assertion:

 (should (equal
           (completion--pcm-first-difference-pos
            (car (completion-substring-all-completions
                  "jab" '("dabjabstabby" "many") nil 1)))
           6))

The number returned by the current code is 4, and not 6.  Maybe this is
wrong, but I don't know if it makes a difference.  If I evaluate

  (let ((completion-styles '(substring)))
     (completing-read "hey? " '("dabjabstabby" "dabjabfooey" "many")))

... and then type "jab", backtrack two characters, and type TAB.  I see
the 's' of stabby and the 'f' of fooey being highlighted as the "next
character to type".  I also see "jab" correctly highlighted.  Exactly as
expected.  Likewise if I evaluate this:

  (let ((completion-styles '(partial-completion)))
     (completing-read "hey? " '("few" "many" "foo")))

which is similar to the other failing test.

Anyway, what I mean is that we need to see tests that tell us when
things are failing at this level.  It's not always easy to write such
tests: we should pick "public" interfaces carefully (regardless of these
problems Dario did a great job with the new tests, which are certainly
better than the pure nothing we had there.)

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

>> In the example you show, I think overlapping *is* as good a behavior as
>> any other (and the code is careful to to replace one face with the
>> other
>
> I agree with this general idea.  I think we have to be careful to write
> tests in terms of user experience as much as possible.  For example, in
> the very latest version of the code I pushed, I still have one of
> Dario's original tests failing (down to only two now).

Makes sense.  I had misunderstood the purpose of the face.  Overlapping
is indeed fine -- for all I care, we can also avoid putting it
altogether in cases where there is no _first character to type_ (without
moving point).  But again, the current behavior is OK.

In that case, the tests should be changed.

>>> This is good (consecutive `any` can introduce serious performance
>>> bugs because of our backtracing regexp matcher).  Other than
>>> improving performance, have you found other effects?
>>
>> Yes, the presence of multiple consecutive wildcards invalidates the
>> aforementioned assumption of completion-pcm--hilit-commonality that
>> the match is of the form
>>
>>     <hole><match><hole><match>...<hole>
>
> Makes sense, thank you.

I think this elimination of consecutive `any' should also be included in
João’s branch.

Best regards,
Dario

-- 
$ keyserver=hkps://hkps.pool.sks-keyservers.net
$ keyid=744A4F0B4F1C9371
$ gpg --keyserver $keyserver --search-keys $keyid

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Stefan Monnier]

> I think this elimination of consecutive `any' should also be included in
> João’s branch.

I just pushed (a rewrite of) that change to `master`.


        Stefan

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I think this elimination of consecutive `any' should also be included in
>> João’s branch.
>
> I just pushed (a rewrite of) that change to `master`.

And I just pushed my cleaned up fix to to master as well, thus hopefully
fixing the brunt of this bug.  Dario and others, please test this.  I
haven't yet pushed the tests, since we're not entirely sure of those,
but I think we should break them up further and push them too, once we
come to an aggreement on what and how they should test exactly.

Thanks,
João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

João Távora <joaotavora@gmail.com> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> I think this elimination of consecutive `any' should also be included in
>>> João’s branch.
>>
>> I just pushed (a rewrite of) that change to `master`.
>
> And I just pushed my cleaned up fix to to master as well, thus hopefully
> fixing the brunt of this bug.  Dario and others, please test this.  I
> haven't yet pushed the tests, since we're not entirely sure of those,
> but I think we should break them up further and push them too, once we
> come to an aggreement on what and how they should test exactly.

Meanwhile, I found that the patch after my sig fixes the remaining two
Dario tests, concerning the presumed misplacement of
'completions-first-difference.

I hadn't touched this part explicitly, and it doesn't seem to make a
world of difference, so I'll leave it up to you two if we should isntall
something like this or not.  (I do think some form of tests should go
in).

I'll put this bit of patch in the side branch
scratch/bug-42149-funny-pcm-completion-scores, too

João

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index dc37c5f447..074d436b35 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3332,11 +3332,12 @@ completion-pcm--hilit-commonality
            ;; for that extra bit of match (bug#42149).
            (unless (= from match-end)
              (funcall update-score-and-face from match-end))
-           (if (> (length str) pos)
-               (add-face-text-property
-                pos (1+ pos)
-                'completions-first-difference
-                nil str))
+           (cl-loop for p from pos below (length str)
+                    unless (eq (get-text-property p 'face str)
+                               'completions-common-part)
+                    return (add-face-text-property p (1+ p)
+                                                   'completions-first-difference
+                                                   nil str))
            (unless (zerop (length str))
              (put-text-property
               0 1 'completion-score

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Lars Ingebrigtsen]

João Távora <joaotavora@gmail.com> writes:

> And I just pushed my cleaned up fix to to master as well, thus hopefully
> fixing the brunt of this bug.  Dario and others, please test this.  I
> haven't yet pushed the tests, since we're not entirely sure of those,
> but I think we should break them up further and push them too, once we
> come to an aggreement on what and how they should test exactly.

I've only skimmed this long thread, but my understanding of it is that
the reported bug was fixed...  but there was some discussion about
including (or not) Dario's tests?

Which (if I'm grepping correctly) would be the patch below?  I tried
applying it, and:

2 unexpected results:
   FAILED  completion-pcm-all-completions-test
   FAILED  completion-substring-all-completions-test

I have not looked into this further -- João, what's the state here?

diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index 5da86f3614..a473fec441 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -104,5 +104,132 @@
                                                 nil (length input))
                      (cons output (length output)))))))
 
+(ert-deftest completion-pcm-all-completions-test ()
+  ;; Point is at end, this does not match anything
+  (should (equal
+           (completion-pcm-all-completions
+            "foo" '("hello" "world" "barfoobar") nil 3)
+           nil))
+  ;; Point is at beginning, this matches "barfoobar"
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 0))
+           "barfoobar"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; One fourth of a match and no match due to point being at the end
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-pcm-all-completions
+                  "RO" '("RaOb") nil 1)))
+           (/ 1.0 4.0)))
+  (should (equal
+           (completion-pcm-all-completions
+            "RO" '("RaOb") nil 2)
+           nil))
+  ;; Point is at beginning, but `completions-first-difference' is
+  ;; moved after it
+  (should (equal
+           (get-text-property
+            1 'face
+            (car (completion-pcm-all-completions
+                  "f" '("few" "many") nil 0)))
+           'completions-first-difference))
+  ;; Wildcards and delimiters work
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("list-packages") nil 7))
+           "list-packages"))
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("do-not-list-packages") nil 7))
+           nil)))
+
+(ert-deftest completion-substring-all-completions-test ()
+  ;; One third of a match!
+  (should (equal
+           (car (completion-substring-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 3))
+           "barfoobar"))
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "foo" '("hello" "world" "barfoobar") nil 3)))
+           (/ 1.0 3.0)))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-substring-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Substring match
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 4))
+           "customize-group"))
+  (should (equal
+           (car (completion-substring-all-completions
+                  "custgroup" '("customize-group") nil 5))
+           nil))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjobstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 1)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            6 'face
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 3)))
+           'completions-first-difference)))
+
+(ert-deftest completion-flex-all-completions-test ()
+  ;; Fuzzy match
+  (should (equal
+           (car (completion-flex-all-completions
+                 "foo" '("hello" "world" "fabrobazo") nil 3))
+           "fabrobazo"))
+  ;; Full match!
+  (should (eql
+           (get-text-property
+            0 'completion-score
+            (car (completion-flex-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0))
+  ;; Another fuzzy match, but more of a "substring" one
+  (should (equal
+           (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4))
+           "customize-group-other-window"))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (get-text-property
+            4 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4)))
+           'completions-first-difference))
+  (should (equal
+           (get-text-property
+            15 'face
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 9)))
+           'completions-first-difference)))
+


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

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> João Távora <joaotavora@gmail.com> writes:
>
>> And I just pushed my cleaned up fix to to master as well, thus hopefully
>> fixing the brunt of this bug.  Dario and others, please test this.  I
>> haven't yet pushed the tests, since we're not entirely sure of those,
>> but I think we should break them up further and push them too, once we
>> come to an aggreement on what and how they should test exactly.
>
> I've only skimmed this long thread, but my understanding of it is that
> the reported bug was fixed...  but there was some discussion about
> including (or not) Dario's tests?
>
> Which (if I'm grepping correctly) would be the patch below?  I tried
> applying it, and:
>
> 2 unexpected results:
>    FAILED  completion-pcm-all-completions-test
>    FAILED  completion-substring-all-completions-test
>
> I have not looked into this further -- João, what's the state here?

I think you applied the original patch of two failing tests, the tests
that demonstrate a particular bug.  So it makes sense that hey fail.

I think we want to merge what's in the
scratch/bug-42149-funny-pcm-completion-scores.  I attach a summary of
the four commtis there.  Then we want to close this issue.

Not sure if it's merged yet, but I don't think so.  I was waiting for
Dario's comments on it, they never arrived, but I'm veryq confident that
this fixes the issues reported here.

There are 4 commits there.  And if you merge this branch, _don't_ also
try to merge the patch you tried earlier: the branch already contains a
rewrite of those tests.

João

commit 03c160fb1573107586355e851c111326debfe95a
Author: João Távora <joaotavora@gmail.com>
Date:   Tue Dec 29 13:31:46 2020 +0000

    Fix "first-differente" face in completion-pcm--hilit-commonality
    
    Fixes: bug#42149
    
    Depending on the position of point in the completion and the
    completion style being used, it may or may not make sense for this
    face to appear immediately after point.  This patch assumes that it
    should appear in the first non-matched character after point, which
    may likely be the next one to type to disambiguate between two or more
    completions.
    
    Suggested by Dario Gjorgjevski <dario.gjorgjevski@gmail.com>.
    
    * lisp/minibuffer.el (completion-pcm--hilit-commonality): Fix
    occasional misplacement of completions-first-differente.

commit d8c596f7309bd6fd6e127b8027dfb4c508afd2ea
Author: João Távora <joaotavora@gmail.com>
Date:   Mon Dec 28 09:10:19 2020 +0000

    Robustify a helper function for test/lisp/minibuffer-tests.el
    
    completion--pcm-first-difference-pos wasn't taking into account the
    fact that faces may come in lists.  bug#42149
    
    * test/lisp/minibuffer-tests.el
    (completion--pcm-first-difference-pos): Robustify.

commit d333ec4cabd21244e5ee468b3a7475fa2dcbe614
Author: João Távora <joaotavora@gmail.com>
Date:   Tue Nov 24 23:15:40 2020 +0000

    Make a completion test robust to custom completion styles
    
    * test/lisp/minibuffer-tests.el (completion-test1): Make test
    resilient to more completion styles.

commit 0265a99ed6b035930fdb21d5bcfdab0707b303aa
Author: João Távora <joaotavora@gmail.com>
Date:   Tue Nov 24 22:34:22 2020 +0000

    Add tests for bug#42149
    
    * test/lisp/minibuffer-tests.el (completion--pcm-score)
    (completion--pcm-first-difference-pos): New helpers.
    (completion-pcm-test-1, completion-pcm-test-2)
    (completion-pcm-test-3, completion-pcm-test-4)
    (completion-pcm-test-5, completion-pcm-test-6)
    (completion-substring-test-1, completion-substring-test-2)
    (completion-substring-test-3, completion-substring-test-4)
    (completion-flex-test-1, completion-flex-test-2)
    (completion-flex-test-3): New tests.
    
    Co-authored-by: Dario Gjorgjevski <dario.gjorgjevski@gmail.com>


João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Dario Gjorgjevski]

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

Hi,

> Not sure if it's merged yet, but I don't think so.  I was waiting for
> Dario's comments on it, they never arrived, but I'm veryq confident that
> this fixes the issues reported here.

Sorry, I kind of forgot about this.  The bug itself was fixed by commit
d199a46, it is only the test that have not been merged yet.

The tests that fail are the ones related to
completions-first-difference, which, we agreed should be left as it is.
Therefore, those tests need to be changed.  (This also applies to the
scratch/bug-42149-funny-pcm-completion-scores branch.)

Here is a patch with the fixed tests: 

[-- Attachment #2: Add tests for bug#42149 --]
[-- Type: text/x-diff, Size: 6719 bytes --]

From 215ac5b9c55670435b69fa92d6124d0c7bf9b5a3 Mon Sep 17 00:00:00 2001
From: Dario Gjorgjevski <dario.gjorgjevski+git@gmail.com>
Date: Thu, 13 May 2021 17:29:13 +0200
Subject: [PATCH] Add tests for bug#42149
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* test/lisp/minibuffer-tests.el (completion--pcm-score)
(completion--pcm-first-difference-pos): New helpers.
(completion-pcm-test-1, completion-pcm-test-2)
(completion-pcm-test-3, completion-pcm-test-4)
(completion-pcm-test-5, completion-pcm-test-6)
(completion-substring-test-1, completion-substring-test-2)
(completion-substring-test-3, completion-substring-test-4)
(completion-flex-test-1, completion-flex-test-2)
(completion-flex-test-3): New tests.

Co-authored-by: João Távora <joaotavora@gmail.com>
---
 test/lisp/minibuffer-tests.el | 143 ++++++++++++++++++++++++++++++++++
 1 file changed, 143 insertions(+)

diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index 6ab5f57eff..c3ba8f9a92 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -188,5 +188,148 @@
                   '("some/alpha" "base/epsilon" "base/delta"))
                  `("epsilon" "delta" "beta" "alpha" "gamma"  . 5))))
 
+(defun completion--pcm-score (comp)
+  "Get `completion-score' from COMP."
+  (get-text-property 0 'completion-score comp))
+
+(defun completion--pcm-first-difference-pos (comp)
+  "Get `completions-first-difference' from COMP."
+  (cl-loop for pos = (next-single-property-change 0 'face comp)
+           then (next-single-property-change pos 'face comp)
+           while pos
+           when (eq (get-text-property pos 'face comp)
+                    'completions-first-difference)
+           return pos))
+
+(ert-deftest completion-pcm-test-1 ()
+  ;; Point is at end, this does not match anything
+  (should (null
+           (completion-pcm-all-completions
+            "foo" '("hello" "world" "barfoobar") nil 3))))
+
+(ert-deftest completion-pcm-test-2 ()
+  ;; Point is at beginning, this matches "barfoobar"
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 0))
+           "barfoobar")))
+
+(ert-deftest completion-pcm-test-3 ()
+  ;; Full match!
+  (should (eql
+           (completion--pcm-score
+            (car (completion-pcm-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0)))
+
+(ert-deftest completion-pcm-test-4 ()
+  ;; One fourth of a match and no match due to point being at the end
+  (should (eql
+           (completion--pcm-score
+            (car (completion-pcm-all-completions
+                  "RO" '("RaOb") nil 1)))
+           (/ 1.0 4.0)))
+  (should (null
+           (completion-pcm-all-completions
+            "RO" '("RaOb") nil 2))))
+
+(ert-deftest completion-pcm-test-5 ()
+  ;; Since point is at the beginning, there is nothing that can really
+  ;; be typed anymore
+  (should (null
+           (completion--pcm-first-difference-pos
+            (car (completion-pcm-all-completions
+                  "f" '("few" "many") nil 0))))))
+
+(ert-deftest completion-pcm-test-6 ()
+  ;; Wildcards and delimiters work
+  (should (equal
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("list-packages") nil 7))
+           "list-packages"))
+  (should (null
+           (car (completion-pcm-all-completions
+                 "li-pac*" '("do-not-list-packages") nil 7)))))
+
+(ert-deftest completion-substring-test-1 ()
+  ;; One third of a match!
+  (should (equal
+           (car (completion-substring-all-completions
+                 "foo" '("hello" "world" "barfoobar") nil 3))
+           "barfoobar"))
+  (should (eql
+           (completion--pcm-score
+            (car (completion-substring-all-completions
+                  "foo" '("hello" "world" "barfoobar") nil 3)))
+           (/ 1.0 3.0))))
+
+(ert-deftest completion-substring-test-2 ()
+  ;; Full match!
+  (should (eql
+           (completion--pcm-score
+            (car (completion-substring-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0)))
+
+(ert-deftest completion-substring-test-3 ()
+  ;; Substring match
+  (should (equal
+           (car (completion-substring-all-completions
+                 "custgroup" '("customize-group") nil 4))
+           "customize-group"))
+  (should (null
+           (car (completion-substring-all-completions
+                 "custgroup" '("customize-group") nil 5)))))
+
+(ert-deftest completion-substring-test-4 ()
+  ;; `completions-first-difference' should be at the right place
+  (should (eql
+           (completion--pcm-first-difference-pos
+            (car (completion-substring-all-completions
+                  "jab" '("dabjobstabby" "many") nil 1)))
+           4))
+  (should (null
+           (completion--pcm-first-difference-pos
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 1)))))
+  (should (equal
+           (completion--pcm-first-difference-pos
+            (car (completion-substring-all-completions
+                  "jab" '("dabjabstabby" "many") nil 3)))
+           6)))
+
+(ert-deftest completion-flex-test-1 ()
+  ;; Fuzzy match
+  (should (equal
+           (car (completion-flex-all-completions
+                 "foo" '("hello" "world" "fabrobazo") nil 3))
+           "fabrobazo")))
+
+(ert-deftest completion-flex-test-2 ()
+  ;; Full match!
+  (should (eql
+           (completion--pcm-score
+            (car (completion-flex-all-completions
+                  "R" '("R" "hello") nil 1)))
+           1.0)))
+
+(ert-deftest completion-flex-test-3 ()
+  ;; Another fuzzy match, but more of a "substring" one
+  (should (equal
+           (car (completion-flex-all-completions
+                 "custgroup" '("customize-group-other-window") nil 4))
+           "customize-group-other-window"))
+  ;; `completions-first-difference' should be at the right place
+  (should (equal
+           (completion--pcm-first-difference-pos
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 4)))
+           4))
+  (should (equal
+           (completion--pcm-first-difference-pos
+            (car (completion-flex-all-completions
+                  "custgroup" '("customize-group-other-window") nil 9)))
+           15)))
+
 (provide 'minibuffer-tests)
 ;;; minibuffer-tests.el ends here
-- 
2.31.GIT


[-- Attachment #3: Type: text/plain, Size: 350 bytes --]


Once the tests are merged, I suppose the
scratch/bug-42149-funny-pcm-completion-scores branch can safely be
deleted.

Best regards,

-- 
Dario Gjorgjevski <dario.gjorgjevski@gmail.com>
Key fingerprint = F7C3 734D 2381 DAEB 4C6D  9CF7 744A 4F0B 4F1C 9371
$ gpg --keyserver   hkps://hkps.pool.sks-keyservers.net \
      --search-keys 744A4F0B4F1C9371

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[João Távora]

Dario Gjorgjevski <dario.gjorgjevski@gmail.com> writes:

> Hi,
>
>> Not sure if it's merged yet, but I don't think so.  I was waiting for
>> Dario's comments on it, they never arrived, but I'm veryq confident that
>> this fixes the issues reported here.
>
> Sorry, I kind of forgot about this.  The bug itself was fixed by commit
> d199a46, it is only the test that have not been merged yet.

Oh, so it is merged (or rather rebased).  Thanks for checking, Dario.

Then I guess this can be closed after merging this patch, which I suppose
is a variation on one of the test commits I presented before.

João

bug#42149: Substring and flex completion ignore implicit trailing ‘any’

[Lars Ingebrigtsen]

João Távora <joaotavora@gmail.com> writes:

> Then I guess this can be closed after merging this patch, which I suppose
> is a variation on one of the test commits I presented before.

OK; I've now pushed Dario's latest patch (i.e., the additional tests),
and I'm closing this bug report.

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