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

[Dario Gjorgjevski <dario.gjorgjevski@gmail.com>]

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