Feature Request: Early Bail Out for Time-Consuming Regex Matches in pcre2 about ripgrep HOT 4 CLOSED

FWIW, here's a faster way to match two words in the same line: ^(?=.*?export)(?=.*?function)

from ripgrep.

I don't mean to be pedantic, but I'll add a few comments since it's an interestic topic 🙂

The .NET regex engine supports timeouts (there's a constructor overload which takes a timeout parameter). This feature is mainly provided for searching with untrusted patterns in order to avoid DoS attacks. I haven't looked at how it's implemented but I believe a check is inserted when backtracking (and maybe in some other cases such as lookarounds). The check is simple enough but it still needs to retrieve the clock when enabled. In any case this article states:

Regex supports timeouts, and guarantees that it will only do at most O(n) work (where n is the length of the input) between timeout checks

As for PCRE2, it has a PCRE2_AUTO_CALLOUT flag which causes the engine to call a user-provided function before each pattern "item", and you can cancel execution from there, so in theory you could implement timeouts, but that would surely wreck the matching performance.

from ripgrep.

^(?=.?export)(?=.?function)

It serves me well, thank you.

from ripgrep.

Or also, rg export | rg function.

Anyway, PCRE2 doesn't support a way to say, "if the search is taking longer than X time, stop." I don't know of any regex engine that supports that. If you think for a moment about how something like that would be implemented, it's pretty clear why: imagine trying to check a timeout value when you're in the middle of some vectorized SIMD loop. It would trash performance. And this sort of timeout check would need to be in virtually every loop everywhere. Ain't going to happen.

PCRE2, like most regex engines, does expose other types of resource limits. But none of them really approximate "time."

Your best bet is to filter out longer lines yourself (rg -v '.{100}' or something), or use a technique that doesn't require using a backtracking engine. Hopefully some day #875 will happen and that will probably be the "right" way to solve your particular problem.

from ripgrep.