Investigate more regex reduction improvements

[danmoseley]

Analyzed all 17,434 real-world patterns from Regex_RealWorldPatterns.json across three tracks:

• Track A (Tree analysis): Ran smell-detection on reduced trees; found 6 categories of potential improvements. Confirmed existing reductions (Concat-with-Empty, Single-child-Concat/Alternate) are already fully effective. FinalReduce() (PR Improve regex optimizer through investigation of regex optimizer passes #125289) correctly simplifies 195 patterns (1.1%).
• Track B (Source generator codegen): Sampled 872 patterns then analyzed all 17,434. Most codegen "smells" (large code, many gotos) are inherent to pattern complexity; found 639 capture-free patterns that generate unnecessary backtracking infra.
• Track C (Cross-engine comparison with Rust): Compared literal extraction strategies against Rust's regex-cli. Discovered .NET misses suffix-based literal search — Rust extracts suffixes that could enable SIMD-accelerated IndexOf on 374+ patterns with no usable prefix.

Priority Ranking (impact × feasibility)

#	Finding	Perf Win	Cost	Risk	Verdict
1	Suffix search	★★★★★ (5-30x for FindFirstChar on 374+ patterns)	Medium (200-400 lines, new feature)	Moderate	Best ROI — significant win, manageable scope
2	Shared-prefix bailout	★☆☆☆☆ (negligible for 80%, modest for ~50)	Trivial (1 line)	Near zero	Just do it — trivial fix for a clear bug
3	Redundant-Atomic	☆☆☆☆☆ (zero measurable)	Trivial (4 lines)	Zero	Just do it — free cleanup
4	Better atomicity	★★★☆☆ (potentially large but hard to quantify)	Hard (100-300 lines, complex analysis)	High	Defer — high risk, uncertain reward

[danmoseley]

Putting this here for some future point I have time to work with Copilot to see whether there's anything useful here.

cc @stephentoub in case he has comments up front.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.

[stephentoub]

Suffix search

The hard part isn't identifying the suffix and enabling searching for it. The hard part is what to do after that. If memory serves, rust then does the equivalent of RTL after it finds the suffix, and we would presumably need to as well. We'd need to be super careful where we employed that, as it could result in different matches. We'd also want to invest more in RTL perf; since RegexOptions.RightToLeft is rare and lookbehinds are generally constrained, most of our recent optimization efforts have excluded RTL.

Shared-prefix bailout
Redundant-Atomic

What are these? If you already have the code for them (you know the line counts), there's low risk, and they're considered "just do it", can you just put up those PRs?

Better atomicity

Examples?

[danmoseley]

Sure, I'll throw up any easy ones.

[danmoseley]

Note

This comment was generated with AI assistance (GitHub Copilot).

Regex Reduction Improvement Investigation (click to expand)

Regex Reduction Improvement Investigation

Goal

After PR #125289 added FinalReduce(), regex reduction is pretty good. Investigate remaining opportunities by analyzing ~18k real-world patterns from Regex_RealWorldPatterns.json.

Infrastructure

• Worktree: C:\git\runtime-regex-analysis (branch dev/danmose/regex-reduction-analysis off upstream/main)
• Analysis tool: Test in UnitTests project (RegexReductionAnalysis.cs) — compiles regex source directly, no reflection needed
• Regex source: Built from worktree with #if DEBUG guards removed from RegexNode.ToString(), RegexCharClass.DescribeChar/DescribeSet
• Patterns JSON: Downloaded from dotnet/runtime-assets — 17,434 distinct patterns
• PR Improve regex optimizer through investigation of regex optimizer passes #125289 confirmed: PatternsReduceIdentically_Compiled test passes (all 9 cases), e.g. a|ab reduces to a

---

Progress

✅ Setup (done)

• Created worktree, verified PR fix, removed #if DEBUG guards, built libs+tests

✅ Track A: Tree analysis (done)

• Tool: RegexReductionAnalysis.cs in UnitTests project with 3 test methods
• All 3 tests pass, results saved to C:\git\notes\:
  • reduction-analysis-results.txt (10 MB) — full smell analysis with trees
  • all-reduced-trees.txt (12.7 MB) — every pattern's fully-reduced tree
  • final-reduce-diffs.txt (1.2 MB) — 195 patterns where FinalReduce changes the tree

✅ Track B: Source generator analysis (done)

• Tool: SourceGenReductionAnalysis.cs in FunctionalTests project
• Sampled 872 patterns (every 20th), ran Roslyn source generator on each
• Results saved to C:\git\notes\sourcegen-analysis-results.txt

✅ Track C: Cross-engine comparison (done — limited)

• No Rust toolchain available; Python's re/regex modules don't expose internal optimizations
• Wrote instructions for future Rust regex-cli comparison in C:\git\notes\cross-engine-comparison.txt

---

Findings — Track A

Summary

Category	Count	Actionable?	Impact
Nested-Capture	1798	❌ No — different capture indices	N/A
Shared-prefix-in-Alternate	1090	⚠️ Partially — some are already handled	Medium
Redundant-Atomic	383	✅ Yes — trivial fix	Low-Medium
Empty-branch-not-at-end	98	✅ Yes — move Empty to end	Low
Fixed-One-loop-not-Multi	20	✅ Yes — convert Oneloop{N,N} to Multi	Low
Nested-Loop	2	❌ No — semantically correct	N/A

Also verified: 0 patterns have Concat-with-Empty, Single-child-Concat, or Single-child-Alternate — those reductions are already fully effective.

FinalReduce still helps: 195 patterns (1.1%)

These are patterns where RegexOptions.Compiled (which triggers FinalReduce) produces a simpler tree than RegexOptions.None. This is working correctly.

---

Finding 1: Redundant-Atomic wrapping non-backtrackable nodes (383 patterns)

What: Atomic wrapping Set (365), Multi (17), or One (1). These nodes cannot backtrack, so the Atomic wrapper is dead weight — it adds a save/restore point that's never used.

Root cause: ReduceAtomic() handles Atomic(loop) → make-loop-atomic, and Atomic(Empty|Nothing) → unwrap. But it does NOT handle Atomic(One|Notone|Set|Multi) → unwrap.

How these arise: User writes (?>...) wrapping content that after reduction becomes a single One/Set/Multi. Example: (?>\u591C[\u665A\u91CC\u95F4]) reduces the alternation inside to Atomic(Set [...]).

Fix: In ReduceAtomic() (line ~720 of RegexNode.cs), add cases to unwrap Atomic from One, Notone, Set, Multi — similar to how it already unwraps Empty/Nothing.

// In ReduceAtomic(), after the existing Empty/Nothing check:
case RegexNodeKind.One:
case RegexNodeKind.Notone:
case RegexNodeKind.Set:
case RegexNodeKind.Multi:
    // These nodes inherently can't backtrack; Atomic wrapper is redundant.
    return child;

Impact: Small per-pattern improvement (avoids unnecessary Atomic node overhead in interpreter; slightly simpler generated code in source generator). Affects 383 of 17,434 patterns (2.2%).

---

Finding 2: Shared prefixes in non-adjacent alternation branches (1090 patterns)

What: Alternation branches that share a leading character but aren't factored together. Example: [^#;]|\\#|\\; — branches 1 and 2 (\\# and \\;) share prefix \ but aren't factored to \\[#;].

Root cause: ExtractCommonPrefixText() (line 1374) iterates branches from index 0. If children[startingIndex].FindBranchOneOrMultiStart() returns null (e.g., the branch is a Set node), the method does return alternation (line 1398), abandoning ALL prefix extraction — even for later branches that could be factored. This is clearly a bug — the loop is designed to scan for any consecutive run of text branches, but it gives up entirely if the first branch isn't text.

Fix: Change return alternation to continue at line 1398. One word. The inner loop already handles non-matching branches by breaking, and if (endingIndex - startingIndex <= 1) continue; on line 1454 correctly skips singleton runs. Zero risk.

Impact analysis (quantified):

Shared branch group size	Patterns	Assessment
2 branches sharing prefix	869 (80%)	Saves 1 branch try — negligible perf win
3 branches	122 (11%)	Minor
4 branches	47 (4%)	Small win from switch dispatch
5 branches	21	Moderate
6-8 branches	23	Good — enables switch dispatch over many branches
9-17 branches	7	Substantial — 9-17 branches consolidated behind a shared prefix

Most common shared chars: '2' (96 patterns, mostly IP validation), 'd' (94), 'M' (72), 'a' (70), 's' (69).

Verdict: Worth doing because it's a trivial one-line fix and the current return is clearly wrong behavior. But not a significant perf optimization for most patterns — 80% are just 2-branch cases saving one failed branch try. Only ~50-100 patterns with 4+ shared branches would see meaningful improvement. Primarily a code quality/correctness fix.

---

Finding 3: Empty branches not at end of alternation (98 patterns)

What: Alternation like (a||b) has an Empty branch in the middle position. In a non-atomic alternation, the backtracking engine tries branches left-to-right, so an early Empty branch means "try matching empty before trying later branches." Moving Empty to the end would change semantics (greedy vs. lazy matching).

Root cause: RemoveRedundantEmptiesAndNothings() removes duplicate Empty branches and all Nothing branches, but does NOT reorder Empty branches. For 2-branch alternations, ReduceAlternation converts (a|) → a? and (|a) → a??, but 3+ branch alternations with Empty in the middle are left as-is.

Nuance: Moving Empty to the end would change matching behavior from "try empty first" to "try empty last" — this is NOT always correct. The user may have intentionally written (|a|b) to prefer empty match. So this is NOT a simple reordering fix.

What IS actionable: In atomic alternations ((?>a||b)), the engine already trims branches after Empty (since once Empty matches, later branches are irrelevant). But for non-atomic alternations, the fix would need to be semantic-preserving — perhaps only moving trailing-equivalent Empty branches.

Impact: Low. The 98 patterns may not benefit from any change if the empty-in-middle is semantically intentional.

---

Finding 4: Fixed-count Oneloop not converted to Multi (20 patterns + general optimization)

What: Oneloop or Oneloopatomic with M==N (fixed repetition count, e.g., '{2}) that could be represented as a Multi node (e.g., Multi "''").

Examples:

• [\\]{2} → Oneloopatomic '\\'{2} — could be Multi "\\\\"
• [ ]{4} → Oneloop ' '{4} — could be Multi " "
• [#]{2} → Oneloop '#'{2} — could be Multi "##"

Root cause: MakeQuantifier() only converts One{M,N} where M==N to Multi. It does NOT convert Oneloop{M,N} where M==N. The Oneloop case is reached when the parser creates a loop from a character class like [\\]{2} — the [\\] is first a Set, reduced to One \, then made into Oneloop \{2,2}. But the M==N to Multi conversion happens in a different code path.

Small-N case (N ≤ MultiVsRepeaterLimit)

Convert the entire loop to Multi. Oneloopatomic '\\'{2} → Multi "\\\\".

Large-N case: Search layer already handles this!

Initially we thought large fixed-count loops like x{20000} could benefit from splitting into a Multi prefix + remaining loop to enable vectorized search. However, the engine already handles this at the search layer. RegexPrefixAnalyzer.FindPrefix() directly extracts multi-char prefixes from Oneloop nodes:

// RegexPrefixAnalyzer.cs, FindPrefix()
case RegexNodeKind.Oneloop or RegexNodeKind.Oneloopatomic or RegexNodeKind.Onelazy when node.M > 0:
    const int SingleCharIterationLimit = 32;
    int count = Math.Min(node.M, SingleCharIterationLimit);
    vsb.Append(node.Ch, count);  // extracts up to 32 chars from the loop

So a{500} already gets a 32-char "aaa...a" prefix for vectorized IndexOf search, without any tree transformation. The search optimization — which is where the big perf win would be — is already covered.

Remaining value (small only)

The Oneloop{N,N}→Multi conversion for small N still has minor value:

• Simpler matching: one SequenceEqual opcode vs a counted loop
• Source-gen emits span.StartsWith(...) vs a loop
• But this is a micro-optimization, not a search-layer improvement

Impact: Low. The search layer already compensates. Only the small-N matching path is slightly suboptimal.

---

Finding 5: Nested-Capture — FALSE POSITIVE (1798 patterns)

What: Capture(index=N) wrapping Capture(index=M) where N≠M. These are different capture groups — the user wrote ((...)) or the implicit group 0 wraps group 1. Cannot be reduced without changing capture group numbering.

Not actionable.

---

Finding 6: Nested-Loop — NOT ACTIONABLE (2 patterns)

What: Loop(0,∞) wrapping Loop(2,2) — from pattern (?:(?:...){2})*. This is (?:expr{2})* which is semantically different from expr*. Cannot be flattened.

Not actionable.

---

Prioritized Recommendations

#	Finding	Patterns	Fix	Perf Win
1	Shared-prefix bailout (return→continue in ExtractCommonPrefixText)	1090 (6.3%)	Small (1-line + testing)	Potentially meaningful — reduces backtracking, enables prefix scan
2	Redundant-Atomic stripping (Atomic wrapping One/Set/Multi)	383 (2.2%)	Trivial (4 lines)	Tiny — saves one unnecessary save/restore point per match
3	Fixed Oneloop{N,N} → Multi (small N only)	20 (0.1%)	Small	Negligible — search layer already extracts prefix from Oneloop
4	Empty-branch reordering	98 (0.6%)	Complex (semantic change)	Unclear — changes match behavior

---

Findings — Track B (Source Generator Codegen Quality)

Initial structural scan (872 sampled patterns)

Ran Roslyn source generator on 872 patterns and scanned for structural indicators. Found mostly inherent pattern complexity, not codegen inefficiency.

Representative pattern manual review (24 patterns)

Hand-reviewed generated code for 24 patterns spanning simple literals, long alternations, lazy/greedy loops, nested captures, lookaround, etc.

Key observations from manual review:

• LongAlt (Monday|Tuesday|...Sunday): Excellent codegen — uses SearchValues.Create("FMSTW") + multi-position bit-mask validation in TryFindNextPossibleStartingPosition, then nested switch dispatch by first/second char in TryMatchAtCurrentPosition with StartsWith for remainder.
• LazyQuant (<.*?>): Excellent — uses IndexOfAny('\n', '>') in backtrack path to skip chars in bulk.
• CSVField ((?:"([^"]|"")*"|[^,"]*)): Heavy backtracking infra (14 goto, 7 push) for inner [^"]|"" alternation in loop. Could theoretically be made atomic since branches can't conflict with what follows, but this is a tree-level (atomicity analysis) issue, not a codegen issue.
• ManyCaptures: Repetitive but intentionally unrolled for perf. UncaptureUntil(0) on early failures is trivially cheap.
• NamedCaptures (\d{4}): Unrolled to 4 individual char.IsDigit() checks — good and expected.

Verdict: Source generator codegen is already quite good. Improvements would come from the tree level (better atomicity, better prefix factoring).

Full codegen quality analysis (all 17,434 patterns)

Ran 11 codegen smell detectors on all 17,434 distinct patterns:

Smell	Count	%	Assessment
Greedy-backtrack-no-IndexOf	5,989	34.4%	Greedy loops backtrack char-by-char without IndexOf to skip. Inherent to non-atomic greedy loops where what follows isn't a simple literal.
Very-large-code (>400 lines)	4,508	25.9%	Complex patterns produce large matchers. Not a bug — reflects pattern complexity.
High-uncapture-ratio	3,630	20.8%	Many UncaptureUntil vs Capture calls. Inherent to patterns with captures + backtracking.
Excessive-slice-recompute (>10)	2,036	11.7%	Repeated slice = inputSpan.Slice(pos) re-assignments. Trade-off for simpler/safer codegen.
Heavy-backtracking (>20 goto + >5 push)	1,790	10.3%	Complex backtracking infrastructure. Inherent to backtracking patterns.
No-vectorized-search	1,589	9.1%	TryFindNextPossibleStartingPosition lacks IndexOf/SearchValues. Many are anchored (^) where it doesn't matter, or have char classes too broad for useful prefix.
Lazy-loop-no-IndexOf	1,424	8.2%	Lazy loops iterate without IndexOf to skip. Inherent when what follows isn't a simple literal.
Backtracking-without-captures	639	3.7%	Backtracking infra for capture-free patterns. Could potentially be converted to non-backtracking approach, but engine doesn't make that choice per-pattern.
Alt-without-switch-dispatch	511	2.9%	Alternation uses goto branching without switch/StartsWith. Branches don't start with distinct chars — correct not to switch-dispatch.
Many-IsDigit-calls (>8)	335	1.9%	Many char.IsDigit() calls from unrolled \d{N}. By design — unrolling is faster than a counted loop for small N.
No-FindFirstChar	268	1.5%	No TryFindNextPossibleStartingPosition — tries every position. Patterns that can match empty or at any position (e.g. `^*
Many-IsWordChar-calls (>8)	6	<0.1%	Similar to IsDigit — unrolled \w{N}.

Overall assessment: The smells detected are overwhelmingly inherent to the patterns themselves, not codegen deficiencies. The source generator makes appropriate trade-offs:

• Unrolling fixed-count loops into individual checks (faster than counted loops)
• Using SearchValues + multi-position validation for FindFirstChar
• Switch-dispatching alternations when branches have distinct leading chars
• Using IndexOf/IndexOfAny in backtrack paths when what follows is a literal

The main area where tree-level improvements could reduce codegen complexity is better atomicity detection (would eliminate backtracking infra for the 639 capture-free patterns and reduce the 5,989 greedy-backtrack-no-IndexOf count).

---

Findings — Track C (Cross-Engine Comparison with Rust regex-cli)

Rust toolchain: rustc 1.94.0, regex-cli 0.2.3. Ran regex-cli debug hir and regex-cli debug literal on all 18,924 distinct patterns.

Compatibility

• 15,917 patterns (84%) compile in Rust regex
• 3,007 patterns (16%) fail — Rust doesn't support backreferences, lookahead/behind, or some .NET-specific syntax

Key Finding: Suffix-Based Literal Search

Rust's literal extraction identifies both prefixes and suffixes of what any match must contain. .NET only does prefix-based searching.

Category	Count	Notes
Has prefix only	264	.NET handles these
Has suffix only (no prefix)	374	.NET has NO search optimization for these; Rust can search for suffix
Has both (same)	6,590	.NET already uses the prefix
Has both (different)	52	Suffix may be more selective than prefix
Neither	15,194	No literal optimization available

The 374 suffix-only patterns are the most interesting. These are patterns where .NET's TryFindNextPossibleStartingPosition either does a linear scan or relies only on a single-char set, but Rust can search for a multi-char suffix string using SIMD-accelerated IndexOf.

Examples of suffix-only patterns:

• (last|past|previous)\b — suffix "ast" or similar (shared by branches)
• Surname|(Last[_]?Name) — suffix "ame"
• (Given|First)[_]?Name — suffix "Name"
• (http|https):\/\/ — suffix "://"
• \\?/Date\((-?\d+)(-|\+)?([0-9]{4})?\)\\?/ — suffix "/Date("
• (?<keep>[aeiou]y)s$ — suffix "ys"

For the 52 patterns with both prefix and suffix but different values, the suffix is sometimes much more selective. Example: (?<midnight>midnight|mid-night|mid night) has prefix "mid" (3 chars) but suffix "night" (5 chars) — "night" is likely rarer in input text.

Prior discussion: This idea was discussed in dotnet/runtime#1349 (comment) in January 2020. @danmoseley noted Rust searches for literal suffixes; @stephentoub acknowledged it could work but noted variable-length regions before the suffix complicate things. No dedicated issue was filed.

Potential approach: For patterns where a common suffix exists and no prefix is available, emit IndexOf(suffix) in TryFindNextPossibleStartingPosition and then "back up" to try the full match. The suffix approach is often more selective than single-char prefix sets because multi-char substrings are exponentially rarer than single chars.

HIR Structure Comparison

Rust does NOT factor common prefixes in its HIR. abc|abd stays as two separate Literal nodes, not Concat(Literal("ab"), Alternation(...)). Rust handles prefix sharing at the automaton level (NFA state sharing), not the tree level. This means .NET's tree-level prefix factoring is an advantage .NET has that Rust doesn't replicate in its IR.

Structural features across 15,917 compilable patterns:

• Repetition: 12,107 (76%)
• Alternation: 5,491 (35%)
• Character class: 12,779 (80%)
• Look assertions: 8,179 (51%)
• Capture: 10,725 (67%)
• Concat: 13,823 (87%)

---

What's Already Working Well

• FinalReduce() handles 195 patterns (1.1%) — all converge in 2 rounds
• No Concat-with-Empty, Single-child-Concat, or Single-child-Alternate remain — these reductions are fully effective
• Prefix extraction works for consecutive One/Multi-starting branches
• Atomic loop promotion is comprehensive
• Character class merging (single-element [a] → a) is working
• Search layer already extracts multi-char prefixes from Oneloop{N,N} — up to 32 chars via RegexPrefixAnalyzer.FindPrefix(), so tree-level Oneloop→Multi conversion isn't needed for search performance
• Source generator codegen is high quality — switch-dispatch, SearchValues, IndexOf in backtrack paths, unrolled fixed loops, multi-position validation in FindFirstChar
• .NET's tree-level prefix factoring (e.g. abc|abd → ab[cd]) is an optimization Rust doesn't replicate in its HIR

---

Overall Summary

After analyzing all 17,434 real-world patterns across tree reduction (Track A), source generator codegen (Track B), and cross-engine comparison with Rust (Track C):

Actionable findings — impact and cost estimates

Perf estimates use sherlock.txt (595K English prose) as representative input.

1. Suffix-based literal search (374+ patterns, NEW optimization)

.NET only searches forward from prefix; Rust also extracts suffixes. For patterns with no usable prefix but a common suffix, this could enable SIMD-accelerated IndexOf searching. Previously discussed in #1349 but no issue filed.

Estimated perf win (on sherlock.txt):

• Monday|...|Sunday: suffix "day" gets 205 candidate hits vs prefix [FMSTW] getting 3,862 hits — 18.8x fewer false positives in FindFirstChar. Each false positive costs a failed TryMatchAtCurrentPosition. Even accounting for the "back up" cost of suffix search, net win is likely 5-15x faster for the search phase on sparse-match English text.
• (Given|First)[_]?Name: suffix "Name" gets 1 hit vs prefix [FG] getting 519 — 519x fewer false positives. Dramatic.
• 374 patterns with no prefix at all: currently linear scan (every position tried). Suffix IndexOf would skip most of the input via SIMD — 10-30x faster for FindFirstChar phase. This is the most impactful category.
• On match-dense inputs the win shrinks since you can't skip much either way.
• dotnet/performance benchmark wins: Perf_Regex_Industry_RustLang_Sherlock has [a-zA-Z]+ing (prefix [a-zA-Z] hits 447K positions vs suffix "ing" hits 2,846 — 157x fewer, est. 10-50x speedup), [a-q][^u-z]{13}x (prefix [a-q] hits 302K vs suffix "x" hits 567 — 533x fewer, est. 10-30x), and \s[a-zA-Z]{0,12}ing\s (est. 5-20x). Perf_Regex_Industry_Leipzig has [a-z]shing (prefix [a-z] hits 433K vs suffix "shing" hits 23 — 18,800x fewer, est. massive speedup). These are rebar-derived benchmarks, so wins directly improve cross-engine competitive numbers.

Estimated cost/complexity:

• Scope: New feature, not a bug fix. Touches 3-4 files: RegexPrefixAnalyzer.cs (suffix extraction), RegexFindOptimizations.cs (new FindNextStartingPositionMode), RegexGenerator.Emitter.cs (emit suffix-search code), RegexCompiler.cs (interpreter path).
• Size: ~200-400 lines of new code.
• Complexity: Medium-hard. Suffix extraction from alternations is straightforward (reverse of prefix extraction). The "back up" logic needs care: after finding suffix at position i, try match starting at i - (maxBranchLen - suffixLen) through i. Must handle: backing up past runtextstart, overlapping matches, variable-length branches.
• Risk: Moderate. New search mode, needs thorough testing. Wrong back-up distance could miss matches or produce false negatives. Well-scoped though — only activates when no prefix is available and a suffix exists.
• Reviewability: Medium. Conceptually clean ("search for suffix, back up, try match") but the details of back-up bounds and interaction with existing search modes need careful review.

Potential regressions:

• Back-up window cost: After finding a suffix hit, the engine must try match at multiple positions backwards. For patterns with highly variable-length branches (e.g., \w{1,100}foo), the back-up window can be large (up to 100 positions per suffix hit). If the suffix is moderately common, each hit costs N back-up tries × failed TryMatchAtCurrentPosition. This could be worse than a broad prefix if the suffix isn't rare enough to offset the per-hit cost. Mitigation: only use suffix search when back-up window is bounded and reasonably small (e.g., ≤ 20 chars); fall back to prefix/linear for unbounded patterns.
• Suffix less selective than prefix: For the 52 patterns that have BOTH prefix and suffix but different, the system must choose which to search for. Choosing suffix when prefix is actually more selective would regress. Mitigation: use a heuristic comparing selectivity — longer literal wins; multi-char string beats single-char set. Could also consider both and pick the one with fewer expected hits based on char frequency tables.
• Match-dense inputs: If the suffix appears very frequently (e.g., suffix is "e" on French text, or "s" on English text), IndexOf returns quickly but the engine gains little skip distance. Pays overhead of back-up logic for marginal gain vs. a simple leading-set check. Mitigation: single-char suffixes should only be preferred over prefix if prefix has zero selectivity (linear scan today).
• Code size / JIT cost: New search mode means more emitted code in source generator. Patterns that don't benefit from suffix search are unaffected (the mode only activates when chosen). But any pattern that now gets suffix-mode search has a slightly different (not larger) TryFindNextPossibleStartingPosition. JIT cost is negligible.
• Interaction with existing optimizations: If the engine currently uses a multi-position validation strategy (e.g., SearchValues + bit-mask for alternation branches) that's already quite selective, suffix search might not improve and could lose the multi-position validation advantage. Mitigation: suffix search should only be chosen as FindFirstChar strategy when it's demonstrably better than any existing strategy the engine would otherwise use.
• Overall regression risk: Low-to-moderate, manageable with conservative activation heuristics. The safest approach: only activate when no prefix search is available at all (the 374 suffix-only patterns) — this avoids all "suffix vs prefix" comparison pitfalls and still captures the biggest win category.

2. Shared-prefix bailout fix (1,090 patterns, tree reduction)

ExtractCommonPrefixText() bails on entire alternation when one non-text branch is encountered. Changing return to continue would allow factoring later consecutive text branches.

Estimated perf win:

• 869 of 1,090 (80%) are 2-branch cases — saves 1 failed branch try per non-matching position. Negligible (nanoseconds per match attempt).
• ~50 patterns with 4+ shared branches see 5-20% improvement in match phase — factored prefix enables switch dispatch instead of sequential tries.
• 7 patterns with 9-17 shared branches see more substantial improvement.
• Overall: Negligible for most patterns. Modest for a handful.
• dotnet/performance benchmark wins: The closest candidate is the IP pattern (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}... in Perf_Regex_Common and Perf_Regex_Industry_Mariomkas (inner alternation has "2" shared by 2/3 branches). But these benchmarks use tiny inputs (15-20 chars) where branch-try overhead is noise. No measurable impact on any existing benchmark.

Estimated cost/complexity:

• Scope: One word change. Line 1398 of RegexNode.cs: return alternation; → continue;
• Size: 1 line.
• Complexity: Trivial. The loop already handles all edge cases (inner loop breaks on non-matching branches, singleton runs are skipped, index management after consolidation works correctly).
• Risk: Near zero. The continue simply lets the outer loop advance to the next branch. All consolidation logic is unchanged.
• Reviewability: Trivial. Clear bug — the return was clearly not the intent of a loop designed to scan for any consecutive run of text branches.

Potential regressions:

• Deeper tree at compile time: Factoring creates an extra Concat node wrapping the shared prefix + reduced alternation. More nodes means marginally more work during reduction passes. In practice, undetectable — one extra node out of typically dozens.
• Branch order semantics: Factoring preserves relative order of the consolidated branches within their sub-alternation. The non-text branch that caused the current bailout stays in its original position — it's not moved or reordered. So match semantics are preserved: the non-text branch is still tried at its original index in the alternation.
• Patterns that were "correctly" bailing: The current return may have been intentional if the author believed non-text branches invalidated the entire factoring attempt. But analysis shows the loop is designed to find any consecutive run — the continue is clearly the correct intent. No case exists where factoring a later run would produce wrong results, because each run is processed independently.
• Overall regression risk: Near zero. The change only adds factoring that was previously skipped. Already-factored branches are unaffected. The only new work is on branches that currently get no optimization at all.

3. Redundant-Atomic stripping (383 patterns, tree reduction)

ReduceAtomic() doesn't unwrap Atomic from One/Set/Multi children that inherently can't backtrack. Trivial 4-line fix.

Estimated perf win:

• Source generator: Effectively zero. The Atomic wrapper generates one int startingPos = pos; save and one dead pos = startingPos; restore path. The JIT will optimize away the unused local and dead branch. No measurable difference.
• Interpreter: Saves one opcode dispatch per match (Atomic enter/exit). Negligible — sub-nanosecond.
• Overall: Zero measurable perf impact. Pure tree cleanliness.
• dotnet/performance benchmark wins: None. No benchmark patterns produce Atomic(One/Set/Multi) in their reduced trees. Even if they did, JIT eliminates the dead code. No measurable impact on any existing benchmark.

Estimated cost/complexity:

• Scope: 4 lines in ReduceAtomic() in RegexNode.cs.
• Size: 4 lines (add cases for One, Notone, Set, Multi → return child).
• Complexity: Trivial. Follows exact pattern of existing Empty/Nothing unwrapping.
• Risk: Zero. These nodes provably cannot backtrack. Unwrapping Atomic is always correct.
• Reviewability: Trivial. Self-evidently correct.

Potential regressions:

• None identified. Removing an Atomic wrapper from One/Set/Multi produces a semantically identical node with fewer tree levels. These nodes cannot backtrack by definition — they match exactly one character (or a fixed string for Multi) and advance. The Atomic wrapper only adds useless position save/restore scaffolding.
• Downstream optimization dependency: If any downstream pass relied on the presence of an Atomic node to trigger a beneficial optimization, removing it could prevent that. Code review shows no such dependency — Atomic is only checked to emit save/restore, which is the overhead we're removing.
• Overall regression risk: Zero.

4. Better atomicity detection (639+ patterns, tree+codegen)

Some patterns without captures generate full backtracking infrastructure (StackPush, goto labels, position save/restore). More aggressive atomicity analysis could eliminate unnecessary state saving.

Estimated perf win:

• On matching inputs: Small — backtrack paths aren't taken, so the infra is dead weight but never executes. Win is just code size / I-cache.
• On non-matching inputs with backtracking: Potentially significant — atomic matching fails fast without exploring backtrack paths. For patterns like ^\w+([_.-]\w+)*$ on non-matching input, could avoid O(n²) backtracking. But this depends heavily on the specific pattern and input.
• Overall: Potentially large for worst-case inputs, but hard to quantify across the 639 patterns without per-pattern analysis. Many of these may actually need backtracking for correctness — "capture-free" doesn't mean "can be made atomic."
• dotnet/performance benchmark wins: Perf_Regex_Common has .*(ss) and [^a]+\.[^z]+ which exercise backtracking, but backtracking is semantically required in both — better atomicity analysis wouldn't help. Perf_Regex_Industry_Leipzig has .{0,2}(Tom|...) and .{2,4}(Tom|...) where the .{N,M} prefix requires backtracking. The 639 capture-free patterns from Track A are not represented in the perf benchmarks. No measurable impact on any existing benchmark.

Estimated cost/complexity:

• Scope: Enhance atomicity analysis in ReduceAtomic() and related methods. Need to look past zero-min-count nodes to determine if backtracking can ever succeed. Touches RegexNode.cs (100-300 lines of changes to existing complex analysis code).
• Size: 100-300 lines of changes to existing code.
• Complexity: Hard. The current atomicity analysis is already ~200 lines of subtle correctness-critical code. Extending it to prove more constructs can be atomic requires analyzing "what follows" more deeply — looking past optional groups, past the end of loops, etc. Easy to get wrong.
• Risk: High. Incorrect atomicity detection silently changes matching semantics — a pattern that should backtrack and find a match instead fails. These bugs are subtle and hard to catch in testing.
• Reviewability: Hard. Requires deep understanding of backtracking semantics and the interaction between atomicity and what follows each node. Non-trivial to verify correctness by inspection.

Potential regressions:

• Correctness regression (the primary risk): If the analysis incorrectly determines a construct can be made atomic, the regex silently returns wrong results — it fails to match inputs it should match. Example: a(b|bc)c — making the inner alternation atomic causes failure on "abcc" because it greedily picks "b" and never backtracks to try "bc". This class of bug is silent, input-dependent, and hard to test exhaustively. The existing atomicity analysis in ReduceAtomic() is carefully scoped to cases that are provably safe; extending it risks introducing subtle correctness bugs.
• Perf regression on currently-fast patterns: Very unlikely. Making a construct atomic can only help or be neutral for performance — fewer backtrack paths means less work. The only scenario where it hurts: if the JIT was already eliminating dead backtrack code (which it does for simple cases), then the tree change doesn't help but doesn't hurt either.
• Interaction with other reductions: Marking more nodes atomic changes the tree shape, which could affect downstream reductions (e.g., FinalReduce() or prefix extraction). Could produce unexpected secondary effects. Needs careful integration testing.
• Overall regression risk: High for correctness, near zero for performance. This is the only finding where a regression could change match semantics rather than just timing.

Impact on dotnet/performance regex microbenchmarks

The dotnet/performance repo (C:\git\performance) has 9 benchmark classes in src/benchmarks/micro/libraries/System.Text.RegularExpressions/. The most relevant use sherlock.txt.gz (595K English prose) and 3200.txt.gz (Leipzig corpus). Here's how each finding maps to specific benchmarks.

Finding 1 (Suffix search) — benchmark impact

Perf_Regex_Industry_RustLang_Sherlock (sherlock.txt, 32 patterns):

Pattern	Current prefix search	Suffix alternative	Prefix hits	Suffix hits	False-positive ratio	Est. speedup
[a-zA-Z]+ing	[a-zA-Z] (every letter)	"ing" (3 chars)	447,145	2,846	157x	10-50x for FindFirstChar
\s[a-zA-Z]{0,12}ing\s	\s (every space)	"ing" (3 chars)	~100K	2,846	~35x	5-20x for FindFirstChar
[a-q][^u-z]{13}x	[a-q] (most lowercase)	"x" (1 char)	302,381	567	533x	10-30x for FindFirstChar
\b\w+n\b	\b (every word boundary)	"n" before \b	~50K	~30K	~1.7x	Marginal — single-char suffix
\w+\s+Holmes	\w (every word char)	"Holmes" (6 chars)	~450K	461	~976x	Large — but may already use fixed-distance optimization
\w+\s+Holmes\s+\w+	\w (every word char)	"Holmes" (6 chars)	~450K	461	~976x	Same caveat as above

The [a-zA-Z]+ing and [a-q][^u-z]{13}x benchmarks are directly from rebar's Sherlock suite — improving these would improve .NET's rebar numbers.

Perf_Regex_Industry_Leipzig (3200.txt, 12 patterns):

Pattern	Current prefix search	Suffix alternative	Est. ratio	Est. speedup
[a-z]shing	[a-z] (every lowercase)	"shing" (5 chars)	~18,800x (from sherlock proxy)	Massive — 5-char suffix nearly unique
.{0,2}(Tom|Sawyer|Huckleberry|Finn)	. (every position)	No common suffix	N/A	No change
.{2,4}(Tom|Sawyer|Huckleberry|Finn)	. (every position)	No common suffix	N/A	No change

Other benchmark classes: No suffix-searchable patterns. Perf_Regex_Common uses literals or anchored patterns. Perf_Regex_Industry_Mariomkas uses email/URI/IP patterns with good prefixes already. SliceSlice tests pure literal words. Rebar Russian/Chinese use multi-char literal alternations with good first-char sets.

Summary: Suffix search would show dramatic wins on 3-4 sherlock benchmarks and 1 Leipzig benchmark that are currently bottlenecked by broad prefix sets. These are rebar-derived benchmarks, so wins here directly translate to better cross-engine competitive numbers.

Finding 2 (Shared-prefix bailout) — benchmark impact

Benchmark	Pattern	Impact
Perf_Regex_Common / Mariomkas	(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}...	Inner alternation has "2" shared by 2/3 branches. But benchmarks use tiny inputs (15-20 chars). Negligible.
All other benchmarks	Various alternations	None have the specific pattern of consecutive text branches interrupted by a non-text branch. No impact.

Summary: No measurable impact on any existing benchmark. The IP pattern is the closest candidate but uses tiny inputs where branch-try overhead is noise.

Finding 3 (Redundant-Atomic) — benchmark impact

No impact on any benchmark. None of the benchmark patterns produce Atomic(One/Set/Multi) in their reduced trees. Even if they did, JIT eliminates the dead code.

Finding 4 (Better atomicity) — benchmark impact

Benchmark	Pattern	Impact
Perf_Regex_Common	.*(ss) (Backtracking benchmark)	Currently backtracks through entire input. Better atomicity could help if the engine can prove the .* doesn't need backtracking — but it does (needs to find "ss"). No change.
Perf_Regex_Common	[^a]+\.[^z]+ (OneNodeBacktracking)	Similar — backtracking is semantically required. No change.
Perf_Regex_Industry_Leipzig	.{0,2}(Tom|...) / .{2,4}(Tom|...)	The .{0,N} prefix needs backtracking to try different start positions. No change.

Summary: No measurable impact on any existing benchmark. The benchmarks that exercise backtracking do so because backtracking is semantically necessary. The 639 capture-free patterns from Track A are not represented in the perf benchmarks.

Priority ranking (impact × feasibility)

#	Finding	Perf Win	Cost	Risk	Verdict
1	Suffix search	★★★★★ (5-30x for FindFirstChar on 374+ patterns)	Medium (200-400 lines, new feature)	Moderate	Best ROI — significant win, manageable scope
2	Shared-prefix bailout	★☆☆☆☆ (negligible for 80%, modest for ~50)	Trivial (1 line)	Near zero	Just do it — trivial fix for a clear bug
3	Redundant-Atomic	☆☆☆☆☆ (zero measurable)	Trivial (4 lines)	Zero	Just do it — free cleanup
4	Better atomicity	★★★☆☆ (potentially large but hard to quantify)	Hard (100-300 lines, complex analysis)	High	Defer — high risk, uncertain reward

Not actionable / already handled

• Fixed Oneloop{N,N}→Multi: Search layer already extracts 32-char prefixes from Oneloop nodes
• Empty-branch reordering: Would change match semantics
• Nested-Capture / Nested-Loop: False positives or semantically correct
• Most source generator "smells" (large code, many gotos, etc.): Inherent to pattern complexity

---

Files

All analysis artifacts in C:\git\notes\:

• lowering.md — this document
• reduction-analysis-results.txt (10 MB) — Track A full results with trees
• all-reduced-trees.txt (12.7 MB) — every pattern's reduced tree
• final-reduce-diffs.txt (1.2 MB) — 195 FinalReduce diffs
• sourcegen-analysis-results.txt (126 KB) — Track B initial structural results
• sourcegen-codequality.txt (215 KB) — generated code for 24 representative patterns
• sourcegen-codequality-full-all.txt — Track B full codegen quality analysis (all 17,434 patterns)
• rust-comparison-results.txt — Track C literal extraction summary
• rust-suffix-analysis.txt — Track C suffix-only and divergent suffix/prefix cases
• rust-hir-comparison.txt — Track C HIR structural analysis
• clean_patterns.json — cleaned JSON (no comments/control chars) for scripting

Analysis tools in worktree C:\git\runtime-regex-analysis:

• tests/UnitTests/RegexReductionAnalysis.cs — Track A (3 test methods)
• tests/FunctionalTests/SourceGenReductionAnalysis.cs — Track B structural scan
• tests/FunctionalTests/SourceGenCodeQuality.cs — Track B codegen quality (11 smell detectors)