GlobalReplace with patterns ending in .*$ scans entire input through BitState unnecessarily
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.2k
- PR merge metrics
- No merged PRs in 30d
Description
When using RE2::GlobalReplace with patterns ending in `.*$` (or `.*`) where the `.*` contributes no capture groups, BitState scans the entire input string to track the .* states, even though it is guaranteed to consume the rest of the string.
This is a pretty common usecase for log processing where a regex like `^https?://(?:www\.)?([^/]+)/.*$` is used to extract hostnames from web logs.
It should be possible to short-circuit the match once everything before the trailing `.*` has been matched, avoiding the cost of scanning the remainder of the input.
I prototyped this by stripping the trailing`.*$` and using `RE2::Extract` instead of `GlobalReplace`, which significantly reduced BitState CPU. However, I had to add a guard to fall back when the replacement references \0 (full match), since the matched portion changes.
Is this approach sound? Are there other edge cases or correctness issues I might be missing? Would this be worth handling natively in RE2?
Contributor guide
Assessment
This issue has not been assessed yet.