Adding positive lookahead prevents some optimizations

[Fefer-Ivan]

Consider the following regular expression .*abcd.
And a large string that doesn't match it.
Despite having no match, pcre2grep returns instantly:

> wc -c large_string.txt
   98305 large_string.txt
> time pcre2grep -i '.*abcd' large_string.txt
pcre2grep -i '.*abcd' large_string.txt  0.00s user 0.01s system 45% cpu 0.023 total

Now let's wrap the regex into a positive lookahead (?=.*abcd).
With the same file it takes more than 3 seconds to figure out that there is no match:

> time pcre2grep -i '(?=.*abcd)' large_string.txt
pcre2grep -i '(?=.*abcd)' large_string.txt  3.06s user 0.01s system 99% cpu 3.084 total

And the time complexity increases non-linearly.
If I increase the size of input in 2, time grows 4 times, indicating quadratic match complexity:

> wc -c large_string.txt
  196609 large_string.txt
> time pcre2grep -i '(?=.*abcd)' large_string.txt
pcre2grep -i '(?=.*abcd)' large_string.txt  12.86s user 0.03s system 99% cpu 12.906 total

It looks like wrapping regex into a positive lookahead prevents an optimization of first looking for a fixed abcd substring before matching.

pcre2grep version:

> pcre2grep --version
pcre2grep version 10.47 2025-10-21

[NWilson]

Thank you for reporting this. In general, the coverage for these optimisations is lower as the regex becomes more complicated. It's a nice bonus that you get an optimisation at all with the leading .*.

It's also unfortunate that you get the quadratic complexity when it scans the entire string starting at each position. It would be possible, in this case, to implement an optimisation that avoids that, but I don't know how much it would be generally-useful. There are already a lot of special-case optimisations which add up to a lot of code.

I'll keep this open, so I can think about it in future.

[PhilipHazel]

This pcre2test output shows why. Notice the lack of optimization data for the lookahead. Sorry about the appearance of this comment. I can't figure out how to make Markdown just display fixed format text and I don't know why it is showing some of it in a large font.

PCRE2 version 10.47 2025-10-21 (8-bit)
/.*abcd/
------------------------------------------------------------------
  0  13 Bra
  3     Any*
  5     abcd
 13  13 Ket
 16     End
------------------------------------------------------------------
Capture group count = 0
First code unit at start or follows newline
Last code unit = 'd'
Subject length lower bound = 4

/(?=.*abcd)/
------------------------------------------------------------------
  0  19 Bra
  3  13 Assert
  6     Any*
  8     abcd
 16  13 Ket
 19  19 Ket
 22     End
------------------------------------------------------------------
Capture group count = 0
May match empty string
Subject length lower bound = 0

[ltrzesniewski]

@PhilipHazel you need to write code blocks between two lines with 3 backticks, with an optional language name after the backticks on the first line for highlighting (you can ignore this detail for regex patterns):

```c
int main() {
    return 0;
}
```

results in the following:

int main() {
    return 0;
}

To write code inline, use a single backtick for escaping, which results in this in the middle of a sentence.

[PhilipHazel]

Thank you for the information and for cleaning up my post.

[edwinguillermoarroyogarcia-tech]

Considere la siguiente expresión regular .*abcd. Y una cadena larga que no coincide con ella. A pesar de no tener ninguna coincidencia, pcre2grep devuelve instantáneamente:

> wc -c large_string.txt
   98305 large_string.txt
> time pcre2grep -i '.*abcd' large_string.txt
pcre2grep -i '.*abcd' large_string.txt  0.00s user 0.01s system 45% cpu 0.023 total

Ahora, transformemos la expresión regular en una búsqueda anticipada positiva (?=.*abcd). Con el mismo archivo, se tarda más de 3 segundos en determinar que no hay coincidencia:

> time pcre2grep -i '(?=.*abcd)' large_string.txt
pcre2grep -i '(?=.*abcd)' large_string.txt  3.06s user 0.01s system 99% cpu 3.084 total

Y la complejidad temporal aumenta de forma no lineal. Si aumento el tamaño de la entrada en 2, el tiempo se cuadruplica, lo que indica una complejidad de coincidencia cuadrática:

> wc -c large_string.txt
  196609 large_string.txt
> time pcre2grep -i '(?=.*abcd)' large_string.txt
pcre2grep -i '(?=.*abcd)' large_string.txt  12.86s user 0.03s system 99% cpu 12.906 total

Parece que envolver una expresión regular en una búsqueda positiva hacia adelante impide una optimización de la primera búsqueda de una abcdsubcadena fija antes de la coincidencia.

Versión de pcre2grep:

> pcre2grep --version
pcre2grep version 10.47 2025-10-21

rg [-.|--hidden] --no-ignore patternrg -n -H -S -e "525539377724" -e "+525539377724" -e "5539377724" -e "553 937 7724" --oculto