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

[Stefan Monnier <monnier@iro.umontreal.ca>]

> 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