Earlier fail fast for fixed-length regex patterns with anchors

[jnyrup]

Description

When having a regex pattern which contains both leading+trailing anchors and the pattern is of fixed length, it seems to me that we might be missing an opportunity to fail fast earlier.

Take e.g. the regex pattern ^1234$.
Currently the emitted TryFindNextPossibleStartingPosition checks that the input has at least 4 characters to continue.

if (pos <= inputSpan.Length - 4 && pos == 0)

When invoking IsMatch("12345") on the generated regex, the flow will be:

• pass TryFindNextPossibleStartingPosition as the input is longer than 4 characters,
• enter TryMatchAtCurrentPosition and call .StartsWith("1234"),
• and first then fail on 5 < slice.Length because the input was too long.

If we tightened the check in TryFindNextPossibleStartingPosition to "exactly 4 characters", we wouldn't have to enter TryMatchAtCurrentPosition.

If I understand the code correctly, we can detect this situation in EmitTryFindNextPossibleStartingPosition when:

• rm.Tree.FindOptimizations.LeadingAnchor is RegexNodeKind.Beginning and
• rm.Tree.FindOptimizations.FindMode is FindNextStartingPositionMode.TrailingAnchor_FixedLength_LeftToRight_End or FindNextStartingPositionMode.TrailingAnchor_FixedLength_LeftToRight_EndZ

Am I missing something?

[stephentoub]

Thanks. There are certainly more special-cases we could optimize for; it's primarily a question of how common they are and whether it's worth the extra code to maintain. Looking through https://github.com/dotnet/runtime-assets/blob/main/src/System.Text.RegularExpressions.TestData/Regex_RealWorldPatterns.json, there are several hundred occurrences of this pattern, so I'd be ok with a PR to try to optimize it further.

That said, keep in mind that $ does not mean "exactly at the end". It actually means "at the end or just before an ending \n", so a length check of exactly 4 would be wrong.

For this specific construction, I think the right answer would be to not emit TryFindNextPossibleStartingPosition at all. You can see in the source generator code there's already special-cases when Scan is emitted to control whether or not we emit TryFindNextPossibleStartingPosition or TryMatchAtCurrentPosition. In this case, I think the right answer would simply be to just emit TryMatchAtCurrentPosition and have Scan just call it.

[stephentoub]

Looking at this again, I take back what I said about not emitting TryFindNextPossibleStartingPosition; it has the length check, which we still want, as it quickly rules out any candidates that aren't of the right length. The only difference I think we might want would be for that length check to be an exact length check rather than a minimum, i.e. instead of:

if (pos <= inputSpan.Length - 4 && pos == 0)

it'd be:

if (pos == 0 && inputSpan.Length == 4)

But this would only be viable with a /z anchor, not /Z or $, which as previously noted allow for an optional \n at the end, so the usefulness of this optimization is significantly lessened.