Repository: dotnet/runtime
File: src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFindOptimizations.cs (C#)

Code before:
            if (prefix is { Length: > 1 })
            {
                LeadingPrefix = prefix;
                FindMode = FindNextStartingPositionMode.LeadingString_OrdinalIgnoreCase_LeftToRight;
                return;
            }

            // We're now left-to-right only and looking for multiple prefixes and/or sets.

            // If there are multiple leading strings, we can search for any of them.
            if (!interpreter) // this works in the interpreter, but we avoid it due to additional cost during construction
            {
                if (RegexPrefixAnalyzer.FindPrefixes(root, ignoreCase: true) is { Length: > 1 } caseInsensitivePrefixes)
                {
                    LeadingPrefixes = caseInsensitivePrefixes;
                    FindMode = FindNextStartingPositionMode.LeadingStrings_OrdinalIgnoreCase_LeftToRight;
#if SYSTEM_TEXT_REGULAREXPRESSIONS
                    LeadingStrings = SearchValues.Create(LeadingPrefixes, StringComparison.OrdinalIgnoreCase);
#endif
                    return;
                }
            }

            // Look for case-sensitive prefixes. We don't commit to using them yet; we'll compare
            // their value against the best FixedDistanceSet below.
            string[]? caseSensitivePrefixes = !interpreter ? RegexPrefixAnalyzer.FindPrefixes(root, ignoreCase: false) : null;

            // Build up a list of all of the sets that are a fixed distance from the start of the expression.
            List<FixedDistanceSet>? fixedDistanceSets = RegexPrefixAnalyzer.FindFixedDistanceSets(root, thorough: !interpreter);
            Debug.Assert(fixedDistanceSets is null || fixedDistanceSets.Count != 0);

            // See if we can make a string of at least two characters long out of those sets.  We should have already caught
            // one at the beginning of the pattern, but there may be one hiding at a non-zero fixed distance into the pattern.
            if (fixedDistanceSets is not null &&
                FindFixedDistanceString(fixedDistanceSets) is (string String, int Distance) bestFixedDistanceString)
            {
                FindMode = FindNextStartingPositionMode.FixedDistanceString_LeftToRight;
                FixedDistanceLiteral = ('\0', bestFixedDistanceString.String, bestFixedDistanceString.Distance);
                return;
            }

            // As a backup, see if we can find a literal after a leading atomic loop.  That might be better than whatever sets we find, so
            // we want to know whether we have one in our pocket before deciding whether to use a leading set (we'll prefer a leading
            // set if it's something for which we can search efficiently).
            (RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal)? literalAfterLoop = RegexPrefixAnalyzer.FindLiteralFollowingLeadingLoop(root);

            // If we got such sets, we'll likely use them.  However, if the best of them is something that doesn't support an efficient
            // search and we did successfully find a literal after an atomic loop we could search instead, we prefer the efficient search.
            // For example, if we have a negated set, we will still prefer the literal-after-an-atomic-loop because negated sets typically
            // contain _many_ characters (e.g. [^a] is everything but 'a') and are thus more likely to very quickly match, which means any
            // vectorization employed is less likely to kick in and be worth the startup overhead.

Review comment (security):
Do we need to compute this here? Or could we instead move it down to L224 so that we only do this expensive computation if we may actually use it, e.g.
```csharp
if (!interpreter &&
    HasHighFrequencyChars(fixedDistanceSets[0]) &&
    RegexPrefixAnalyzer.FindPrefixes(root, ignoreCase: false) is { Length: > 1 } caseSensitivePrefixes)
{
    ...
}
```

Code after:
            if (prefix is { Length: > 1 })
            {
                LeadingPrefix = prefix;
                FindMode = FindNextStartingPositionMode.LeadingString_OrdinalIgnoreCase_LeftToRight;
                return;
            }

            // We're now left-to-right only and looking for multiple prefixes and/or sets.

            // If there are multiple case-insensitive leading strings, we can search for any of them.
            if (!interpreter && // this works in the interpreter, but we avoid it due to additional cost during construction
                RegexPrefixAnalyzer.FindPrefixes(root, ignoreCase: true) is { Length: > 1 } caseInsensitivePrefixes)
            {
                LeadingPrefixes = caseInsensitivePrefixes;
                FindMode = FindNextStartingPositionMode.LeadingStrings_OrdinalIgnoreCase_LeftToRight;
#if SYSTEM_TEXT_REGULAREXPRESSIONS
                LeadingStrings = SearchValues.Create(LeadingPrefixes, StringComparison.OrdinalIgnoreCase);
#endif
                return;
            }

            // Build up a list of all of the sets that are a fixed distance from the start of the expression.
            List<FixedDistanceSet>? fixedDistanceSets = RegexPrefixAnalyzer.FindFixedDistanceSets(root, thorough: !interpreter);
            Debug.Assert(fixedDistanceSets is null || fixedDistanceSets.Count != 0);

            // See if we can make a string of at least two characters long out of those sets.  We should have already caught
            // one at the beginning of the pattern, but there may be one hiding at a non-zero fixed distance into the pattern.
            if (fixedDistanceSets is not null &&
                FindFixedDistanceString(fixedDistanceSets) is (string String, int Distance) bestFixedDistanceString)
            {
                FindMode = FindNextStartingPositionMode.FixedDistanceString_LeftToRight;
                FixedDistanceLiteral = ('\0', bestFixedDistanceString.String, bestFixedDistanceString.Distance);
                return;
            }

            // As a backup, see if we can find a literal after a leading atomic loop.  That might be better than whatever sets we find, so
            // we want to know whether we have one in our pocket before deciding whether to use a leading set (we'll prefer a leading
            // set if it's something for which we can search efficiently).
            (RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal)? literalAfterLoop = RegexPrefixAnalyzer.FindLiteralFollowingLeadingLoop(root);

            // If we got such sets, we'll likely use them.  However, if the best of them is something that doesn't support an efficient
            // search and we did successfully find a literal after an atomic loop we could search instead, we prefer the efficient search.
            // For example, if we have a negated set, we will still prefer the literal-after-an-atomic-loop because negated sets typically
            // contain _many_ characters (e.g. [^a] is everything but 'a') and are thus more likely to very quickly match, which means any
            // vectorization employed is less likely to kick in and be worth the startup overhead.
            if (fixedDistanceSets is not null)
            {
                // Sort the sets by "quality", such that whatever set is first is the one deemed most efficient to use.
                // In some searches, we may use multiple sets, so we want the subsequent ones to also be the efficiency runners-up.
                RegexPrefixAnalyzer.SortFixedDistanceSetsByQuality(fixedDistanceSets);