GNU bug report logs - #65137
29.1; completion-substring-try-completion doesn't return the longest common substring

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 65137 in the body.
You can then email your comments to 65137 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Spencer Baugh <sbaugh <at> janestreet.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 29.1; completion-substring-try-completion doesn't return the
 longest common substring
Date: Mon, 07 Aug 2023 19:24:15 -0400

The substring completion style differs from the "basic" style by
performing completion at the start of the input string.  So for example,
both of these are valid completions for "bar":

(completion-substring-all-completions "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
-> ("foobarbaz" "foobar" . 0)

However, the substring completion style's try-completion implementation
does not reflect this.  Since "foobar" is a prefix of all the valid
completions, it should be returned by try-completion.  But it is not,
regardless of the location of point:

(completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
-> ("bar" . 3)

(completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
-> ("bar" . 3)

This breaks completion when one completion candidate is a prefix of
other completion candidates.  The recourse is moving point to the start
of the input, so that the "basic" completion style takes over, which
will correctly insert the common prefix:

(completion-basic-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
-> ("foobar" . 6)

However, even this does not work in the project-file and xref-location
completion categories, for which the "basic" style is not included in
completion-category-defaults.  For such completion categories, there's
simply no way to use completion to insert a common prefix.  This is bad,
because a filename or identifier might easily be a prefix of another
filename or identifier.

The solution is completion-substring-try-completion to be fixed to
insert these common prefixes.  I'll try and fix this, although the code
is a bit intimidating.



In GNU Emacs 29.1 (build 3, x86_64-pc-linux-gnu, X toolkit, cairo
 version 1.15.12, Xaw scroll bars) of 2023-07-29 built on

Repository revision: cf24c7ac7608f41078fd2761c856892d5853b676
Repository branch: my-emacs-29
Windowing system distributor 'The X.Org Foundation', version 11.0.12011000
System Description: Rocky Linux 8.8 (Green Obsidian)

Configured using:
 'configure --config-cache --with-x-toolkit=lucid
 --with-gif=ifavailable'

Configured features:
CAIRO DBUS FREETYPE GLIB GMP GNUTLS GSETTINGS HARFBUZZ JPEG JSON
LIBSELINUX LIBSYSTEMD LIBXML2 MODULES NOTIFY INOTIFY PDUMPER PNG RSVG
SECCOMP SOUND SQLITE3 THREADS TIFF TOOLKIT_SCROLL_BARS X11 XDBE XIM
XINPUT2 XPM LUCID ZLIB

Important settings:
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

Major mode: ELisp/l

Memory information:
((conses 16 1210667 128287)
 (symbols 48 75558 3)
 (strings 32 305623 26170)
 (string-bytes 1 9620792)
 (vectors 16 125723)
 (vector-slots 8 2816397 195041)
 (floats 8 762 279)
 (intervals 56 32710 336)
 (buffers 976 120))

Message #8 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Spencer Baugh <sbaugh <at> janestreet.com>
To: 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Mon, 07 Aug 2023 19:50:00 -0400

I've tracked it down further to:

(completion-pcm--merge-completions
 '("ab1" "ab2")
 '(prefix "b"))
-> (any "b")

which definitely doesn't match the docstring of
completion-pcm--merge-completions...  (note that it returns elements in
reverse order, so this is basically just returning the string "b")

Message #11 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Spencer Baugh <sbaugh <at> janestreet.com>
To: 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Mon, 07 Aug 2023 20:41:12 -0400

[Message part 1 (text/plain, inline)]

Here's a patch fixing this.  It's definitely just a bug in the
implementation of completion-pcm--merge-completions - see my commit
message for details.

[0001-Correctly-handle-common-prefixes-in-substring-comple.patch (text/x-patch, inline)]

From ea63217c1c85f1ca4f1f22b9c4781167de6cf00d Mon Sep 17 00:00:00 2001
From: Spencer Baugh <sbaugh <at> janestreet.com>
Date: Mon, 7 Aug 2023 20:20:34 -0400
Subject: [PATCH] Correctly handle common prefixes in substring completion

substring completion is implemented by passing the `prefix' symbol as
part of the pattern passed to completion-pcm--merge-completions.  This
symbol is supposed to "grow" the completion only as a suffix, not as a
prefix.

The old behavior of completion-pcm--merge-completions when processing
a `prefix' element in the pattern was to find the common prefix of all
the completions in that part of the pattern (using try-completion) and
then completely discard that common prefix.  Then the actual logic for
`prefix' would run with completion--common-suffix.

However, if all the completion candidates had a common prefix while
processing a `prefix' element, then it would both discard the common
prefix *and* skip the completion--common-suffix logic.  If there was
also a common suffix, e.g. with the following invocation:

  (completion-pcm--merge-completions '("axbc" "aybc") '(prefix "c"))

then this would produce the wrong result by ignoring the common suffix
"b".

The new behavior is to simply not bother generating the common prefix
for `prefix' elements, since we don't use it anyway, and just pretend
it's always empty for `prefix' elements.  Then the
completion--common-suffix logic always runs.

* lisp/minibuffer.el (completion-pcm--merge-completions): Don't ignore
a common suffix in a `prefix' pattern element when there's also a
common prefix.
---
 lisp/minibuffer.el | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d2c7e66d2a0..1aa29318bd2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -4029,12 +4029,15 @@ completion-pcm--merge-completions
               ;; different capitalizations in different parts.
               ;; In practice, it doesn't seem to make any difference.
               (setq ccs (nreverse ccs))
-              (let* ((prefix (try-completion fixed comps))
+              (let* ((prefix
+                      ;; We pretend as if there's no common prefix at all for
+                      ;; `prefix', so we go to completion--common-suffix
+                      (if (eq elem 'prefix) "" (try-completion fixed comps)))
                      (unique (or (and (eq prefix t) (setq prefix fixed))
                                  (and (stringp prefix)
+                                      (not (string-empty-p prefix))
                                       (eq t (try-completion prefix comps))))))
-                (unless (or (eq elem 'prefix)
-                            (equal prefix ""))
+                (unless (equal prefix "")
                   (push prefix res))
                 ;; If there's only one completion, `elem' is not useful
                 ;; any more: it can only match the empty string.
-- 
2.39.3

Message #14 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Spencer Baugh <sbaugh <at> janestreet.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1;
 completion-substring-try-completion doesn't return the longest common
 substring
Date: Tue, 08 Aug 2023 14:04:09 +0300

> From: Spencer Baugh <sbaugh <at> janestreet.com>
> Date: Mon, 07 Aug 2023 19:24:15 -0400
> 
> 
> The substring completion style differs from the "basic" style by
> performing completion at the start of the input string.  So for example,
> both of these are valid completions for "bar":
> 
> (completion-substring-all-completions "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
> -> ("foobarbaz" "foobar" . 0)
> 
> However, the substring completion style's try-completion implementation
> does not reflect this.  Since "foobar" is a prefix of all the valid
> completions, it should be returned by try-completion.  But it is not,
> regardless of the location of point:
> 
> (completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
> -> ("bar" . 3)
> 
> (completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
> -> ("bar" . 3)
> 
> This breaks completion when one completion candidate is a prefix of
> other completion candidates.  The recourse is moving point to the start
> of the input, so that the "basic" completion style takes over, which
> will correctly insert the common prefix:
> 
> (completion-basic-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
> -> ("foobar" . 6)
> 
> However, even this does not work in the project-file and xref-location
> completion categories, for which the "basic" style is not included in
> completion-category-defaults.  For such completion categories, there's
> simply no way to use completion to insert a common prefix.  This is bad,
> because a filename or identifier might easily be a prefix of another
> filename or identifier.
> 
> The solution is completion-substring-try-completion to be fixed to
> insert these common prefixes.  I'll try and fix this, although the code
> is a bit intimidating.

Adding Stefan, in case he has some comments or ideas.

Message #17 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: sbaugh <at> catern.com
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Spencer Baugh <sbaugh <at> janestreet.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Tue, 08 Aug 2023 12:40:01 +0000 (UTC)

[Message part 1 (text/plain, inline)]

Eli Zaretskii <eliz <at> gnu.org> writes:
>> From: Spencer Baugh <sbaugh <at> janestreet.com>
>> Date: Mon, 07 Aug 2023 19:24:15 -0400
>> 
>> 
>> The substring completion style differs from the "basic" style by
>> performing completion at the start of the input string.  So for example,
>> both of these are valid completions for "bar":
>> 
>> (completion-substring-all-completions "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
>> -> ("foobarbaz" "foobar" . 0)
>> 
>> However, the substring completion style's try-completion implementation
>> does not reflect this.  Since "foobar" is a prefix of all the valid
>> completions, it should be returned by try-completion.  But it is not,
>> regardless of the location of point:
>> 
>> (completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
>> -> ("bar" . 3)
>> 
>> (completion-substring-try-completion "bar" '("foobar" "foobarbaz") #'identity (length "bar"))
>> -> ("bar" . 3)
>> 
>> This breaks completion when one completion candidate is a prefix of
>> other completion candidates.  The recourse is moving point to the start
>> of the input, so that the "basic" completion style takes over, which
>> will correctly insert the common prefix:
>> 
>> (completion-basic-try-completion "bar" '("foobar" "foobarbaz") #'identity 0)
>> -> ("foobar" . 6)
>> 
>> However, even this does not work in the project-file and xref-location
>> completion categories, for which the "basic" style is not included in
>> completion-category-defaults.  For such completion categories, there's
>> simply no way to use completion to insert a common prefix.  This is bad,
>> because a filename or identifier might easily be a prefix of another
>> filename or identifier.
>> 
>> The solution is completion-substring-try-completion to be fixed to
>> insert these common prefixes.  I'll try and fix this, although the code
>> is a bit intimidating.
>
> Adding Stefan, in case he has some comments or ideas.

See also (v2 of) my patch.  Now a one-line change, much simpler than my
earlier patch:

[0001-Correctly-handle-common-prefixes-in-substring-comple.patch (text/x-patch, inline)]

From 48627fdedf44aa48f235c4c550318d0ad2500c16 Mon Sep 17 00:00:00 2001
From: Spencer Baugh <sbaugh <at> catern.com>
Date: Tue, 8 Aug 2023 08:37:49 -0400
Subject: [PATCH] Correctly handle common prefixes in substring completion

substring completion is implemented by passing the `prefix' symbol as
part of the pattern passed to completion-pcm--merge-completions.  This
symbol is supposed to "grow" the completion only as a suffix, not as a
prefix.

The old behavior of completion-pcm--merge-completions when processing
a `prefix' element in the pattern was to find the common prefix of all
the completions in that part of the pattern (using try-completion) and
then completely discard that common prefix.  Then the actual logic for
`prefix' would run with completion--common-suffix.

However, the completion--common-suffix logic would be skipped when the
prefix covers the entirety of this part of the pattern.  (When
"unique" is non-nil, in the code).  For example, in this call:

  (completion-pcm--merge-completions '("ab" "ab") '(star "b"))
  -> ("b" "a")

there is no need to calculate a common suffix of '("a" "a") after
finding the common prefix "a".  (Note the return value is in reverse
order.)

But for `prefix', we discard the common prefix, so this behavior would
result in us skipping the calculation of both common prefix and common
suffix.  Like in this call:

  (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
  -> ("b")

The correct behavior is to include the common prefix even for `prefix'
elements if it covers the entirety of this part of the pattern,
because then it is then also a common suffix.  Then we get:

  (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
  -> ("b" "a")

which is correct.

* lisp/minibuffer.el (completion-pcm--merge-completions): Don't ignore
a common suffix in a `prefix' pattern element when there's also a
common prefix.
---
 lisp/minibuffer.el | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 186a4753df1..cc50427b5bd 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -4029,7 +4029,9 @@ completion-pcm--merge-completions
                      (unique (or (and (eq prefix t) (setq prefix fixed))
                                  (and (stringp prefix)
                                       (eq t (try-completion prefix comps))))))
-                (unless (or (eq elem 'prefix)
+                ;; if the common prefix is unique, it also is a common
+                ;; suffix, so we should add it for `prefix' elements
+                (unless (or (and (eq elem 'prefix) (not unique))
                             (equal prefix ""))
                   (push prefix res))
                 ;; If there's only one completion, `elem' is not useful
-- 
2.41.0

Message #20 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Gutov <dmitry <at> gutov.dev>
To: Spencer Baugh <sbaugh <at> janestreet.com>, 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Fri, 25 Aug 2023 03:40:43 +0300

Hi Spencer!

On 08/08/2023 02:24, Spencer Baugh wrote:
> However, even this does not work in the project-file and xref-location
> completion categories, for which the "basic" style is not included in
> completion-category-defaults.  For such completion categories, there's
> simply no way to use completion to insert a common prefix.  This is bad,
> because a filename or identifier might easily be a prefix of another
> filename or identifier.

Could you describe the usage scenario a little more?

From my brief testing, the current behavior seems okay most of the 
time: you still get the short input which matches a bunch of strings 
(e.g. filenames), you can type a little more chars and narrow down.

With your change, TAB will insert the most common prefix for all those 
completions, which in case of project-file can be a pretty long string. 
Not a huge problem, but on the face of it that doesn't seem like an 
improvement. So which scenario would that make better?

Message #23 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Dmitry Gutov <dmitry <at> gutov.dev>, Spencer Baugh <sbaugh <at> janestreet.com>,
 "65137 <at> debbugs.gnu.org" <65137 <at> debbugs.gnu.org>
Subject: RE: [External] : bug#65137: 29.1; completion-substring-try-completion
 doesn't return the longest common substring
Date: Fri, 25 Aug 2023 02:30:02 +0000

> With your change, TAB will insert the most
> common prefix for all those completions,
> which in case of project-file can be a
> pretty long string.  Not a huge problem,
> but on the face of it that doesn't seem
> like an improvement. 

Caveat: Not following this thread at all.
So this is likely to be only noise; sorry,
if you find it so.
___

If some of the discussion has to do with
finding and showing the longest common
match across a set of matches for some
pattern, or even _a_ long common match,
then maybe code such as what I wrote for
Icicles, long ago, might be of interest.

For a set of matches of a given pattern,
depending on the pattern-matching approach,
there might not be _any_ common substring
of all the matches.  E.g., different
matches can use the pattern to match
different parts of the completions.

And even if there is a common substring,
there may not be a single such ("the"
common substring).  Or there may not be
a single longest such substring.

For straight prefix completion the matter
is straightforward.  For other kinds of
matching it's less so.  What I was most
interested in was regexp-matching (which
includes substring matching).

The code I came up with doesn't try to
be perfect.  I think it's pretty useful
in practice.  YMMV.  It amounts to this:

  It is the longest match of your input
  pattern that is common to all candidates
  and also contains the first input match
  in the first or second candidate,
  whichever is longer.

The reason this common-match expansion
typically finds the longest common match
is that your input typically matches the
first or the second candidate in only one
place.  And the longer the input you type,
the more likely this is.  In practice it's
only with very short input the expansion
sometimes misses the longest common match.

The algorithm independently tries two
candidates (first & second) as a starting
point, to increase the probability of
finding the longest common match.

I think it's useful, when showing the set
of completions (e.g. in *Completions*),
to highlight, in a candidate completion,
both (1) the part of it matched by the
pattern and (2) the part of it that's
common to all other matching candidates.
Two different faces are used for this.

The expanded common match found isn't just
a common substring of the completions
matched by your input pattern.  It's such
a substring that also matches your input.

It can be interesting to a user, and is
sometimes useful, to see what a given set
of matches have in common with each other
and with your pattern.  One thing they
can have in common is a common substring.

Besides highlighting a common substring,
Icicles can (optionally) expand/replace
your input pattern in the minibuffer as
well.  (You can hit `C-l' to retrieve the
pattern.)

Since I saw that you mentioned that the
common part can be long, and that can
distract users, I'll mention too that if
you use `C-x .' during completion that
toggles an option that hides (elides) the
common part.  E.g., file-finding commands
that expect an absolute file name can
turn on such eliding to start with.

https://www.emacswiki.org/emacs/Icicles_-_Expanded-Common-Match_Completion

Message #26 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Spencer Baugh <sbaugh <at> janestreet.com>
To: Dmitry Gutov <dmitry <at> gutov.dev>
Cc: 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Tue, 29 Aug 2023 11:45:37 -0400

Dmitry Gutov <dmitry <at> gutov.dev> writes:
> Hi Spencer!
>
> On 08/08/2023 02:24, Spencer Baugh wrote:
>> However, even this does not work in the project-file and xref-location
>> completion categories, for which the "basic" style is not included in
>> completion-category-defaults.  For such completion categories, there's
>> simply no way to use completion to insert a common prefix.  This is bad,
>> because a filename or identifier might easily be a prefix of another
>> filename or identifier.
>
> Could you describe the usage scenario a little more?
>
> From my brief testing, the current behavior seems okay most of the
> time: you still get the short input which matches a bunch of strings
> (e.g. filenames), you can type a little more chars and narrow down.
>
> With your change, TAB will insert the most common prefix for all those
> completions, which in case of project-file can be a pretty long
> string. Not a huge problem, but on the face of it that doesn't seem
> like an improvement. So which scenario would that make better?

As a very concrete example that I ran into frequently, for
project-find-file if you have two files:

dir/foo.ml
dir/foo.mli

and you input "foo" and press Tab, you get "foo.ml".  But it is then
impossible to expand that to dir/foo.ml using completion because of this
bug.  So you have to manually select dir/foo.ml if you want to visit
that file, either by switching to *Completions* and selecting it or by
using minibuffer-next-completion.

After this bugfix, inputting "foo" and pressing Tab will expand to
"dir/foo.ml".

In general, this bug makes it impossible to input a file name with
completion (in project-file) if that file name is a prefix of another
file name.  Like dir/foo and dir/foo.tar, or dir/foo.log and
dir/foo.log.bak.

Message #29 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Gutov <dmitry <at> gutov.dev>
To: Spencer Baugh <sbaugh <at> janestreet.com>
Cc: 65137 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> IRO.UMontreal.CA>
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Wed, 30 Aug 2023 02:25:41 +0300

On 29/08/2023 18:45, Spencer Baugh wrote:

>> Could you describe the usage scenario a little more?
>>
>>  From my brief testing, the current behavior seems okay most of the
>> time: you still get the short input which matches a bunch of strings
>> (e.g. filenames), you can type a little more chars and narrow down.
>>
>> With your change, TAB will insert the most common prefix for all those
>> completions, which in case of project-file can be a pretty long
>> string. Not a huge problem, but on the face of it that doesn't seem
>> like an improvement. So which scenario would that make better?
> 
> As a very concrete example that I ran into frequently, for
> project-find-file if you have two files:
> 
> dir/foo.ml
> dir/foo.mli
> 
> and you input "foo" and press Tab, you get "foo.ml".  But it is then
> impossible to expand that to dir/foo.ml using completion because of this
> bug.  So you have to manually select dir/foo.ml if you want to visit
> that file, either by switching to *Completions* and selecting it or by
> using minibuffer-next-completion.

Now I understand, thank you. I guess this is something that certain 
environments (such as OCaml) are more prone to than others.

Also this problem seems somewhat unique to the default completion 
mechanism. If I use Ivy, or Helm, or Vertico, or even the "bare" 
icomplete-mode, they all have the notion of the currently selected 
completion, with a short key sequence to choose it.

E.g. with icomplete-mode on I would type until the needed completion is 
highlighted in the minibuffer and then press C-j (maybe press C-, or C-. 
to select it).

The default completion, as you say, has the means to do a similar thing 
with M-<up> and M-<down>, but it's less obvious and requires more 
keypresses.

> After this bugfix, inputting "foo" and pressing Tab will expand to
> "dir/foo.ml".
> 
> In general, this bug makes it impossible to input a file name with
> completion (in project-file) if that file name is a prefix of another
> file name.  Like dir/foo and dir/foo.tar, or dir/foo.log and
> dir/foo.log.bak.

Your patch fixes that by expanding inputs into longer lines after TAB 
(meaning, the user will see their input text shift, sometimes 
considerably, to the right, and perhaps feel a little disoriented). It 
might be a minor thing, but a downside nevertheless.

I do wonder what Stefan thinks what would be the right behavior here.

Message #32 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: sbaugh <at> catern.com
Cc: Spencer Baugh <sbaugh <at> janestreet.com>, Eli Zaretskii <eliz <at> gnu.org>,
 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Tue, 29 Aug 2023 21:31:51 -0400

>   (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
>   -> ("b")

Right this is a bug.

    (completion-pcm--merge-completions '("ab" "sab") '(prefix "b"))

returns (correctly)

    ("b" "a" prefix)

so

    (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))

should return either ("b" "a") or ("b" "a" prefix).

Could you accompany your patch of a regression test using
`completion-pcm--merge-completions` as above?

Similarly, I see that

    (completion-pcm--merge-completions '("abr" "absabr") '(prefix "br"))

returns

    ("br" prefix)

whereas it should arguably return

    ("br" "a" prefix)

[ Tho this may have the side effect that after this completion, `absabr`
  won't be considered any more, if the `basic` completion comes before
  `substring` :-(  ]


        Stefan

Message #35 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Spencer Baugh <sbaugh <at> janestreet.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: sbaugh <at> catern.com, Eli Zaretskii <eliz <at> gnu.org>, 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Tue, 05 Sep 2023 15:51:14 -0400

[Message part 1 (text/plain, inline)]

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
>>   (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
>>   -> ("b")
>
> Right this is a bug.
>
>     (completion-pcm--merge-completions '("ab" "sab") '(prefix "b"))
>
> returns (correctly)
>
>     ("b" "a" prefix)
>
> so
>
>     (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
>
> should return either ("b" "a") or ("b" "a" prefix).
>
> Could you accompany your patch of a regression test using
> `completion-pcm--merge-completions` as above?

Patch with test:

[0001-Correctly-handle-common-prefixes-in-substring-comple.patch (text/x-patch, inline)]

From 364a10aa54acd8de71a10d1ab98d059a27f26460 Mon Sep 17 00:00:00 2001
From: Spencer Baugh <sbaugh <at> janestreet.com>
Date: Tue, 5 Sep 2023 15:40:06 -0400
Subject: [PATCH] Correctly handle common prefixes in substring completion

Substring completion would previously not complete the longest common
substring if that substring was a prefix of all the completion
alternatives.  Now it does.  An explanation of this bug

Substring completion is implemented by passing the `prefix' symbol as
part of the pattern passed to completion-pcm--merge-completions.  This
symbol is supposed to cause completion-pcm--merge-completions to
"grow" a completion of a common substring only from the "right" of the
symbol (a common suffix), not from the "left" of the symbol (a common
prefix).  Yes, this is the opposite of what the name `prefix' would
imply.

When processing a symbolic element of the pattern,
completion-pcm--merge-completions first finds the common prefix of all
the completions in that part of the pattern (using try-completion).
Then for `prefix' and other elements which want to complete a common
suffix, the common prefix is removed from each element and then the
common suffix is calculated with completion--common-suffix.

If the common prefix covers the entirety of all the alternatives
(i.e. when "unique" is true in the code), it's also a common suffix.
In that case, the common suffix calculation (if it runs) is basically
a no-op which will produce an empty string, since we removed the
common prefix before running it.

Before this change, `prefix' elements would unconditionally discard
the common prefix, which produced the wrong result in the case that
common prefix == common suffix.  For example:

  (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
  -> ("b")

Now we detect this situation and include the common prefix in this
case for `prefix' elements.  Then we get:

  (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
  -> ("b" "a")

which is correct.

* lisp/minibuffer.el (completion-pcm--merge-completions): Don't ignore
a common suffix in a `prefix' pattern element when it's also a common
prefix.
* test/lisp/minibuffer-tests.el (completion-substring-test-5): Add a
test.
---
 lisp/minibuffer.el            |  4 +++-
 test/lisp/minibuffer-tests.el | 13 +++++++++++++
 2 files changed, 16 insertions(+), 1 deletion(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 35b359a75e2..ac054da61d2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -4038,7 +4038,9 @@ completion-pcm--merge-completions
                      (unique (or (and (eq prefix t) (setq prefix fixed))
                                  (and (stringp prefix)
                                       (eq t (try-completion prefix comps))))))
-                (unless (or (eq elem 'prefix)
+                ;; if the common prefix is unique, it also is a common
+                ;; suffix, so we should add it for `prefix' elements
+                (unless (or (and (eq elem 'prefix) (not unique))
                             (equal prefix ""))
                   (push prefix res))
                 ;; If there's only one completion, `elem' is not useful
diff --git a/test/lisp/minibuffer-tests.el b/test/lisp/minibuffer-tests.el
index ff58d35eb3e..4f92d7f841c 100644
--- a/test/lisp/minibuffer-tests.el
+++ b/test/lisp/minibuffer-tests.el
@@ -298,6 +298,19 @@ completion-substring-test-4
                   "jab" '("dabjabstabby" "many") nil 3)))
            6)))
 
+(ert-deftest completion-substring-test-5 ()
+  ;; merge-completions needs to work correctly when
+  (should (equal
+           (completion-pcm--merge-completions '("ab" "sab") '(prefix "b"))
+           '("b" "a" prefix)))
+  (should (equal
+           (completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
+           '("b" "a")))
+  ;; substring completion should successfully complete the entire string
+  (should (equal
+           (completion-substring-try-completion "b" '("ab" "ab") nil 0)
+           '("ab" . 2))))
+
 (ert-deftest completion-flex-test-1 ()
   ;; Fuzzy match
   (should (equal
-- 
2.39.3

[Message part 3 (text/plain, inline)]

> Similarly, I see that
>
>     (completion-pcm--merge-completions '("abr" "absabr") '(prefix "br"))
>
> returns
>
>     ("br" prefix)
>
> whereas it should arguably return
>
>     ("br" "a" prefix)
>
> [ Tho this may have the side effect that after this completion, `absabr`
>   won't be considered any more, if the `basic` completion comes before
>   `substring` :-(  ]

I did notice this too.  I could try fixing/changing this too, but it
does seem annoying when basic comes before substring - as it does by
default in a number of completion categories.

I wonder if we should move basic to after substring in those categories
in completion-category-defaults?  Or just remove basic from them.  It
doesn't seem like having both basic and substring in those lists has
much point.  Plus it would be a nice improvement to defaults - buffer
completion in particular confused me for a long time before I understood
how basic and substring interacted, so having only substring would ease
understanding for new users.

Message #38 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Spencer Baugh <sbaugh <at> janestreet.com>
Cc: sbaugh <at> catern.com, Eli Zaretskii <eliz <at> gnu.org>, 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Tue, 05 Sep 2023 17:26:00 -0400

> Patch with test:

Thanks, pushed.

>> Similarly, I see that
>>
>>     (completion-pcm--merge-completions '("abr" "absabr") '(prefix "br"))
>>
>> returns
>>
>>     ("br" prefix)
>>
>> whereas it should arguably return
>>
>>     ("br" "a" prefix)
>>
>> [ Tho this may have the side effect that after this completion, `absabr`
>>   won't be considered any more, if the `basic` completion comes before
>>   `substring` :-(  ]

> I did notice this too.  I could try fixing/changing this too, but it
> does seem annoying when basic comes before substring - as it does by
> default in a number of completion categories.

Yup :-(

I have often wished for there to be a way to remember the style that was
used so as to try and avoid such "style capture".

> I wonder if we should move basic to after substring in those
> categories in completion-category-defaults?

It's a tradeoff: the default is designed to reduce the factor of
surprise for people used to the default (i.e. to mostly prefix completion).

> Or just remove basic from them.

Same difference :-)

> It doesn't seem like having both basic and substring in those lists
> has much point.

If you're used to relying on `substring` indeed it's not helpful.
But if you're used to using mostly prefix-based completion (which may
have the effect that you choose your names such that prefix completion
works well), it can be helpful to have `substring` as a fallback when
you can't remember what prefix to use for the thing you're looking for.


        Stefan

Message #41 received at 65137 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Spencer Baugh <sbaugh <at> janestreet.com>
Cc: sbaugh <at> catern.com, monnier <at> iro.umontreal.ca, 65137 <at> debbugs.gnu.org
Subject: Re: bug#65137: 29.1; completion-substring-try-completion doesn't
 return the longest common substring
Date: Wed, 06 Sep 2023 14:00:24 +0300

> From: Spencer Baugh <sbaugh <at> janestreet.com>
> Cc: sbaugh <at> catern.com,  Eli Zaretskii <eliz <at> gnu.org>,  65137 <at> debbugs.gnu.org
> Date: Tue, 05 Sep 2023 15:51:14 -0400
> 
> 
> * lisp/minibuffer.el (completion-pcm--merge-completions): Don't ignore
> a common suffix in a `prefix' pattern element when it's also a common
> prefix.
> * test/lisp/minibuffer-tests.el (completion-substring-test-5): Add a
> test.

Please mention the bug number in the commit log message.

> +                ;; if the common prefix is unique, it also is a common
> +                ;; suffix, so we should add it for `prefix' elements

Comments should begin with a capital letter and end with a period.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.