Add support for multiple char classes in FindFirstChars (#2254)
authorStephen Toub <stoub@microsoft.com>
Wed, 29 Jan 2020 02:17:53 +0000 (21:17 -0500)
committerGitHub <noreply@github.com>
Wed, 29 Jan 2020 02:17:53 +0000 (21:17 -0500)
commitaaaf84a6d6853aea0ab66044a465086a0c9331eb
tree732eb9385625de1429f6293be95d039c0699ec42
parent7365ddbbe91da8a0f08edac1c11f0be2b1d58983
Add support for multiple char classes in FindFirstChars (#2254)

* Add a "multi first" check for FindFirstChars

FindFirstChars already has multiple things it checks for:
- If the expression is anchored, it checks the current position for that anchor.
- If we were able to compute a min required length, it checks for that much space remaining.
- If we were able to analyze the expression and come up with a string of text of multiple characters that must be at the beginning of any expression, we use Boyer-Moore to find it.
- If we were able to analyze the expression to come up with a character class that must match the first character in the input, we iterate through looking for that (and if possible, use IndexOf{Any} to speed that along).

This PR extends that last check to try to create a character class not just for the first character in the input, but for the first N characters in the input.  The check isn't as robust, mainly focused on expressions beginning with an alternation (often when it's global), so it's a separate check we try first, and only fall back to the more robust single-class analysis if we were unsuccessful.

By checking multiple characters, we're able to stay in a tighter loop inside of FindFirstChars.  In the future, we could look at replacing this with something potentially even better, such as a vectorized search for multiple starting strings.

* Address PR feedback
12 files changed:
src/libraries/System.Text.RegularExpressions/src/System.Text.RegularExpressions.csproj
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexAssemblyCompiler.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexBoyerMoore.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/RegexInterpreter.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexLWCGCompiler.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexNode.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexPrefix.cs [deleted file]
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexPrefixAnalyzer.cs [moved from src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFCD.cs with 63% similarity]
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexWriter.cs
src/libraries/System.Text.RegularExpressions/tests/Regex.MultipleMatches.Tests.cs