Improve handling of more common Regex sets (#67365)
authorStephen Toub <stoub@microsoft.com>
Wed, 6 Apr 2022 10:24:22 +0000 (06:24 -0400)
committerGitHub <noreply@github.com>
Wed, 6 Apr 2022 10:24:22 +0000 (06:24 -0400)
commit3dbc67e1b844b022fd759361af4b3cd248afa05e
treea8c8ce91cccc25cdf7d7bf8d242ee868aa19b620
parentc537cc6a45c4c75524ec98f6a8d4c9637438958e
Improve handling of more common Regex sets (#67365)

- Today for a set like [\r\n], we'll emit a comparison that compares the char to each of '\r' and '\n', but for a set like [^\r\n], we end up falling back to emitting a lookup table.  With this PR, we simply use the existing support for the non-negating case, just negating the result.
- Today for a set like [\p{IsGreek}\p{IsGreekExtended}] that ends up being two ranges, we'll fall back to our lookup table.  With this PR, we'll emit it as two range checks.
- Today for a set like [A-Za-z], we'll fall back to our lookup table.  As a special case of two-range support, with this PR we'll now recognize that these ranges are just one bit flip away from each other, and we'll employ the normal ASCII casing to do a single range comparison against the input or'd with a mask.
- Today as a fallback, we employ a lookup table stored in a string; this requires a bounds check, dereferencing the string object, doing the math to find the right index, doing the math to find the right bit, etc.  With this PR, for sets composed only of ranges where the exclusiveMax - inclusiveMin <= 64, with this PR we'll now emit it as a lookup into a ulong that's done in a branchless fashion and is much faster.
- It appears to be relatively common for folks to use [\d\D], [\w\W], or [\s\S] as a simple way of saying "match anything"; RegexOptions.Singleline changes '.' to mean this as well.  We already have special handling for '.' with Singleline as "AnyClass"... this just normalizes those other common representations into the same shape so that everyhing else recognizes them accordingly.
- Today when we see an AnyClass, we emit a nonsense comparison that always results in true (or false for negations); that's because, for a while, the expression given to the matching routine may have had side effects.  There are no longer side effects, though, so it's ok to just emit "true" or "false" directly and make the operation cheaper.
- For every optimization we have in MatchCharacterClass, we should always be able to handle negation trivially.
- Handle character classes composed of multiple UnicodeCategories. This helps with composed categories, like \p{N}.
- Fix hard-coded char class strings for \W and \S. There are multiple ways to invert a RegexCharClass string: you can invert the whole string by just setting the invert flag, or you can invert all the individual components, e.g. if the string is composed of only categories, invert each category.  The hardcoded string the parser uses when you write \W simply sets the negated bit, but this causes problems if \W is used as [\W], because then the individual components are added into a larger set that doesn't have negation set.  And that means \W and [\W] result in different strings, which means any place we special-case the string for \W, we don't recognize [\W].  The same applies to \S. This commit changes the hardcoded string for \W and \S to use the more canonical form. Also, the implementation generally uses "set" and "class" interchangeably, but when specifying the ECMA-related strings, it uses "set" to actually mean "ranges", which is very confusing.  I've changed them.
src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCharClass.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/FunctionalTests/RegexCharacterSetTests.cs