google / google/re2

GlobalReplace with patterns ending in .*$ scans entire input through BitState unnecessarily

Open
#605 2 comments 1 reaction 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.