Improve regex optimizations around repetitions of the same character (#65273)
authorStephen Toub <stoub@microsoft.com>
Tue, 15 Feb 2022 20:32:58 +0000 (15:32 -0500)
committerGitHub <noreply@github.com>
Tue, 15 Feb 2022 20:32:58 +0000 (15:32 -0500)
commit99160fca9f5ddf3f2731c3de6afe276a378059c1
treee0702b9e7ff5bc31738e8b2a19af272d1eea8ff0
parentc6994a7655a293ea65132945625bcd327258b4de
Improve regex optimizations around repetitions of the same character (#65273)

- For concatenations, we currently do two passes over its nodes: one that coalesces adjacent characters into strings, and one that coalesces adjacent loops.  This swaps the order so that we first coalesce adjacent loops.  We want to coalesce loops first so that we prioritize associating a One with an adjacent loop rather than with an adjacent string.  This is primarily beneficial later on for auto-atomicity.  Consider `a+ab` composed of a loop, a One 'a', and a One 'b'.  We're either going to make that into a loop `a{2,}` followed by `b` or into a loop `a+` followed by the multi `ab`.  We want to do the former, as then when we apply auto-atomicity to the `a{2,}`, we'll see that it's followed by something non-overlapping ('b'), and make the loop atomic.  In constrast, if we joined the `a` and `b`, then auto-atomicity for the `a+` would see it's followed by an `a` and it wouldn't be upgraded.
- Currently, the adjacent loop coalescing logic joins two individual One nodes with the same Ch value into a repeater.  That's actually a deoptimization, so this stops doing so.  We'd rather have `aa` be evaluated as a Multi of two characters rather than as an `a{2}` repeater, as we're able to apply better optimizations with multis, e.g. taking advantage of StartsWith for matching.
- Also in the adjacent loop logic, we're already checking for a loop followed by a one but we're not checking for a loop followed by a multi.  For the same auto-atomicity benefits discussed earlier, we want to shift any adjacent text from a multi following a loop back into the loop, as it makes it more likely we'll then be able to upgrade that loop to atomic. (We could also add logic for a multi followed by a loop, but the benefits there are less obvious.)
- When creating repeaters, we're actually better off creating multis, for the same reasons outlined earlier.  But we don't want to create massive strings in the super rare case where large repeaters for single chars are used, so we only do so up to a limit.
- When emitting generated code for a One repeater, which might be used to implement the required portion of other loops, emit it as a multi match for short enough repetitions.
src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCompiler.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexNode.cs
src/libraries/System.Text.RegularExpressions/tests/RegexReductionTests.cs