libstdc++: Inline simple regex repeating matches in DFS
Optimized regex matching for repeated character classes in libstdc++'s regex engine.
This change optimizes the Direct Finite State Machine (DFS) NFA shape for repeating regex patterns, such as [\w]+ or #+. It avoids creating unnecessary stack frames for greedy repeats, directly consuming match states when the repeated body returns to the repeat state. This optimization improves performance for various regex patterns, including email and URI matching.
In Details
The DFS regex executor's state machine for handling repeating subexpressions has been optimized. Specifically, when a repeated subexpression immediately returns to the repeat state (e.g., in a+ where a is a single character match), the executor now consumes that match state directly without pushing/popping bookkeeping frames. This optimization targets common greedy repeats and maintains backtracking behavior.
- DFS NFA
- Direct Finite State Machine (DFS) NFA refers to an optimized implementation of a Nondeterministic Finite Automaton used for regular expression matching. It directly models the state transitions without explicit stack manipulation for certain operations.
- greedy repeats
- In regular expressions, a greedy repeat (like
*,+,?) attempts to match as many characters as possible. This optimization focuses on efficiently handling cases where a greedy repeat is followed by a simple match. - stack frame
- A region of memory on the call stack used to store function call information, including local variables and return addresses. In this context, it refers to bookkeeping information pushed onto the stack during regex execution.