Fix pathological slowness in flex completion

The 'completion-regexp-list' optimization in
completion--flex-all-completions-1, a cheap pre-filter via a trivial
regexp, performs very poorly for longer patterns and strings, so drop
it.  That alone recovers fairly decent performance for the flex
completion when compared to the 'hotfuzz' point of reference.

We then recover the cheap rejection with an O(N+M) pre-check in the
Fcompletion__flex_cost_gotoh C scorer.  This kicks in the common case
(completion-ignore-case is nil) and pays off especially when the table
is already a list and 'all-completions' needn't cons.

See:
  https://lists.gnu.org/archive/html/emacs-devel/2026-04/msg01081.html
  https://lists.gnu.org/archive/html/emacs-devel/2026-05/msg00519.html

* lisp/minibuffer.el (completion--flex-all-completions-1): Remove
regexp pre-filter.

* src/minibuf.c (Fcompletion__flex_cost_gotoh): Add subsequence
pre-check.

1 files changed, 16 insertions, 0 deletions

diff --git a/src/minibuf.c b/src/minibuf.c
index c716ac0d811..745a71a63fc 100644
--- a/src/minibuf.c
+++ b/src/minibuf.c
@@ -2364,6 +2364,22 @@ STR the i-th character of PAT matched.  */)
     if (patlen == 0 || strlen == 0 || size > FLEX_MAX_MATRIX_SIZE)
       return Qnil;
 
+    /* Also bail if PAT is not a subsequence of STR so bail "cheaply"
+       before the O(N*M) DP algorithm.  Walking both strings
+       byte-by-byte for this purpose (and only for case-sensitive common
+       case) should be valid even for multibyte strings. */
+    if (!completion_ignore_case)
+      {
+	const unsigned char *p = SDATA (pat);
+	const unsigned char *s = SDATA (str);
+	int pi = 0;
+	for (int si = 0; si < strlen && pi < patlen; si++)
+	  if (s[si] == p[pi])
+	    pi++;
+	if (pi < patlen)
+	  return Qnil;
+      }
+
     /* Initialize M and D with positive infinity...  */
     for (int j = 0; j < size; j++)
       M[j] = D[j] = pos_inf;