completion inserts a character from neither match; possible fix patch in join_sub()

[Luca Berneking <luca@xxxxxxxxxxxxx>]

Hi,

I am facing an annoying autocomplete bug with the default ohmyzsh config in some of my directories.
At first I thought that this is related to the ohmyzsh configuration but finally had the time to
take a closer look at the bug with the help of an LLM. My original ohmyzsh github issue:
https://github.com/ohmyzsh/ohmyzsh/issues/12723

Reproducers tested with zsh 5.9.2:

  autoload -Uz compinit; compinit -u
  zstyle ':completion:*' matcher-list 'm:{a-zA-Z}={A-Za-z}' 'r:|=*' 'l:|=* r:|=*'

Now

  mkdir -p /tmp/x && cd /tmp/x && touch ab-xyFOO ac-xyBAR
  cat -xy<TAB>

autocompletes to `aB-xy`, and

  mkdir -p /tmp/t && cd /tmp/t && touch 1abc 2abc
  cat a<TAB>

autocompletes to `Aabc`.

I found similar bug reports from 2014 (X-seq: zsh-users 18877).
The bug got semi-fixed in zsh 5.9
https://www.zsh.org/mla/workers/2021/msg01887.html
https://www.zsh.org/mla/workers/2016/msg00671.html
but got reverted due to a regression with
https://www.zsh.org/mla/workers/2022/msg00652.html
https://www.zsh.org/mla/workers/2022/msg00655.html

I dont have any prior experience with the zsh source code but might have found the bug using an LLM:


> join_sub() (Src/Zle/compmatch.c) compares two chunks of text and asks
> whether one string could stand for both.  The old chunk arrives from the
> caller as str/len; the new one is tracked by the cursor struct as
> md->str/md->len.
> 
> A chunk can be identified by where it starts or where it ends, and which
> is wanted depends on direction: when sfx is set, pattern_match() scans
> backwards and needs pointers to the end.  That is what the "if (sfx)"
> block is for.  But the two chunks do not arrive in the same form -- str
> from the caller is a start pointer, while md->str is already an end
> pointer, because check_cmdata() did "md->str += md->len" when it loaded
> the chunk.
> 
> There are two mistakes, and both have to be fixed; correcting either one
> alone leaves the function broken.
> 
> 1. The "if (sfx)" block treats the two sides symmetrically:
> 
>        ow += ol; nw += nl;
> 
>    That is right for ow, which really is a start, and wrong for nw, which
>    was already an end.  Advancing it again pushes it a whole region-length
>    too far, past the chunk being compared and into whatever follows.  For
>    1abc/2abc that is the character after the anchor.  In other cases it
>    runs off the end of the allocation: for two directories ppaazz and
>    ppbbzz it lands at offset 8 of a 6-byte string, so some of the
>    currently "correct" answers in this area are only correct because the
>    out-of-bounds bytes happened not to match.
> 
> 2. Those same pointers are then handed to bld_line(), which walks its
>    "word" argument forwards for wlen characters to build a character
>    array, and so needs the start of the region.  It was being given the
>    end.  This is independent of (1): even with nw correct as an end
>    pointer, it is still the wrong thing to pass here.
> 
> Instrumented trace of the 1abc/2abc case, before the fix:
> 
>   join_sub ENTER: sfx=4 ow=<1> ol=1 | md.pcl.word=<2>(wlen=1) str_off=1
>   join_sub: after sfx adj: nw points past <a>
>   pattern_match1: EQUIV chr='1' -> NO MATCH, returning 0
>   pattern_match1: EQUIV chr='2' -> NO MATCH, returning 0
>   join_sub: matched t=0 -> mw=<a> other=<1>
>   bld_line ENTER: mword=<a> word=<a> wlen=1 sfx=4
>   pme: wind=27 -> PATMATCHINDEX index=26 -> exact lchr='A'
>   bld_line EXIT: rl=1 built-line=<A>
> 
> '1' and '2' are correctly rejected as having no equivalent, which is
> where it should have stopped.  The 'A' comes from then comparing 'a' --
> the character after the anchor in 2abc -- against '1'.  bld_line() and
> pattern_match_equivalence() are behaving correctly on the input they are
> given; they are simply given the wrong characters.



diff --git a/Src/Zle/compmatch.c b/Src/Zle/compmatch.c
index 7e0411294..5bafa18a9 100644
--- a/Src/Zle/compmatch.c
+++ b/Src/Zle/compmatch.c
@@ -2212,12 +2212,23 @@ join_sub(Cmdata md, char *str, int len, int *mlen, int sfx, int join)
     if (!check_cmdata(md, sfx)) {
 	char *ow = str, *nw = md->str;
 	int ol = len, nl = md->len;
+	/*
+	 * ow and nw are used below as the *end* of each unmatched region,
+	 * since pattern_match() scans backwards from there when sfx is
+	 * set.  bld_line() instead reads its "word" argument forwards and
+	 * needs the *start*, derived here the same way undo_cmdata() does.
+	 */
+	char *owb = str, *nwb = md->str - (sfx ? md->len : 0);
 	Cmlist ms;
 	Cmatcher mp;
 	int t;

 	if (sfx) {
-	    ow += ol; nw += nl;
+	    /*
+	     * check_cmdata() has already positioned md->str at the end of
+	     * the unconsumed portion, so nw must not be advanced again.
+	     */
+	    ow += ol;
 	}
 	for (t = 0, ms = bmatchers; ms && !t; ms = ms->next) {
 	    mp = ms->matcher;
@@ -2262,7 +2273,7 @@ join_sub(Cmdata md, char *str, int len, int *mlen, int sfx, int join)
 		    else
 			mw = nw - (sfx ? mp->wlen : 0);

-		    if ((bl = bld_line(mp, line, mw, (t ? nw : ow),
+		    if ((bl = bld_line(mp, line, mw, (t ? nwb : owb),
 				       (t ? nl : ol), sfx)))  {
 			/* Yep, one of the lines matched the other
 			 * string. */