Automatically upgrade some loops to be greedy
authorStephen Toub <stoub@microsoft.com>
Thu, 26 Dec 2019 20:25:18 +0000 (15:25 -0500)
committerStephen Toub <stoub@microsoft.com>
Thu, 9 Jan 2020 03:50:09 +0000 (22:50 -0500)
commit8536878ab2f04b64f914285fa1502a5e8d437710
tree5373fc379a11ea2d00ba0ade6515c05e9f588985
parentb2c639e3330b8fa96861a38c77cb9ee65bd9d0fa
Automatically upgrade some loops to be greedy

In an expression like A*B, backtracing may be involved even if it's impossible that it'll do any good, namely if there's no overlap between the A and B sets.  This backtracking can be avoided by using a greedy subexpression, e.g. (?>A*)B, but a) few developers think to do that, and b) even when they do the implementation has more overhead than is desirable.

This change does three things:
1. It introduces primitives for "oneloopgreedy" and "setloopgreedy" that correspond to the existing "oneloop" (a single character in a loop) and "setloop" (a char class in a loop) primitives.
2. It reduces a Greedy node that contains a one/setloop to instead just be a one/setloopgreedy node.
3. It finds cases of one/setloop concatenated with other things, and automatically updates those to be one/setloopgreedy when it can provie that the backtracking would have no benefit.

(2) removes a small amount of overhead, in particular in compiled, because it avoids needing to spit additional tracking state for backtracking.

(3) can likely be expanded in the future to catch more cases, but it handles the common cases now.  This has a very measurable impact on non-matches that would otherwise trigger backtracking into the subexpression.
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCharClass.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCode.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCompiler.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFCD.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexInterpreter.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexNode.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexWriter.cs