Fix source generated regex compilation failure due to mismatched notion of atomic...
authorStephen Toub <stoub@microsoft.com>
Fri, 4 Mar 2022 20:45:33 +0000 (15:45 -0500)
committerGitHub <noreply@github.com>
Fri, 4 Mar 2022 20:45:33 +0000 (15:45 -0500)
commit39626e59544c0c949d2439d1e94ac3fc06343c27
tree0d93453e22393b9d9d2ae817e4124edf9f705af6
parentb259ef087d3faf2e3147e2bc21369b03794eae0d
Fix source generated regex compilation failure due to mismatched notion of atomic (#66195)

During and post-parsing, we apply various optimizations to the regex node tree, in particular trying to annotate as much as possible as atomic in order to eliminate unnecessary backtracking.  Then later when RegexCompiler and the source generator view the final tree, they also compute for every node whether a child may backtrack, as doing so enables avoiding unnecessary backtracking-related code generation if the child is known to not backtrack (e.g. because it's now marked as atomic).  However, things can go awry if the compiler / source generator's view of what's atomic differs from what's actually generated.  Because of how optimizations are applied to the node tree, it's possible for a late optimization to make a transformation that then would enable a node to be made atomic, but we don't run that phase of the optimizer again, and thus the node is left non-atomic.  Then the source generator comes along, does its analysis, and sees that the node should be treated as atomic.  That leads to problems, because the node itself will have unnecessary backtracking code generated but the parent will rightly assume there wasn't anyway and won't generate the code necessary to compensate for it, or alternatively will generate code that causes problems (e.g. the source generator uses this information to determine whether it can output scopes).

Our outer loop tests that source gen our full regex corpus caught a case where this was happening.  A couple fixes, either of which on their own is sufficient to address this particular case, but each of which also brings other benefits:
1. When rendering a single-char loop, it consults the computed atomicity table to determine whether the rest of the source generation views it as atomic.  If it does, it instead does an atomic rendering.
2. When we do our ending backtracking elimination pass (i.e. walking down the right-hand side of atomic nodes to make anything that ends them also be atomic), we should also recur into lookarounds.

This also removes some duplicated code for reducing lookarounds, and renames some stale method names.
src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexCompiler.cs
src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexNode.cs