RegexGenerator.Emitter.cs

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System;
using System.Buffers.Binary;
using System.CodeDom.Compiler;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using System.Text;
using System.Threading;
using Microsoft.CodeAnalysis.CSharp;

// NOTE: The logic in this file is largely a copy of logic in RegexCompiler, emitting C# instead of MSIL.
// Most changes made to this file should be kept in sync, so far as bug fixes and relevant optimizations
// are concerned.

namespace System.Text.RegularExpressions.Generator
{
    public partial class RegexGenerator
    {
        /// <summary>Code for a [GeneratedCode] attribute to put on the top-level generated members.</summary>
        private static readonly string s_generatedCodeAttribute = $"[global::System.CodeDom.Compiler.GeneratedCodeAttribute(\"{typeof(RegexGenerator).Assembly.GetName().Name}\", \"{typeof(RegexGenerator).Assembly.GetName().Version}\")]";
        /// <summary>Header comments and usings to include at the top of every generated file.</summary>
        private static readonly string[] s_headers = new string[]
        {
            "// <auto-generated/>",
            "#nullable enable",
            "#pragma warning disable CS0162 // Unreachable code",
            "#pragma warning disable CS0164 // Unreferenced label",
            "#pragma warning disable CS0168 // Variable declared but never used",
            "#pragma warning disable CS0219 // Variable assigned but never used",
            "",
        };

        /// <summary>Generates the code for one regular expression class.</summary>
        private static string EmitRegexType(RegexType regexClass)
        {
            var sb = new StringBuilder(1024);
            var writer = new IndentedTextWriter(new StringWriter(sb));

            // Emit the namespace
            if (!string.IsNullOrWhiteSpace(regexClass.Namespace))
            {
                writer.WriteLine($"namespace {regexClass.Namespace}");
                writer.WriteLine("{");
                writer.Indent++;
            }

            // Emit containing types
            RegexType? parent = regexClass.ParentClass;
            var parentClasses = new Stack<string>();
            while (parent is not null)
            {
                parentClasses.Push($"partial {parent.Keyword} {parent.Name} {parent.Constraints}");
                parent = parent.ParentClass;
            }
            while (parentClasses.Count != 0)
            {
                writer.WriteLine($"{parentClasses.Pop()}");
                writer.WriteLine("{");
                writer.Indent++;
            }

            // Emit the direct parent type
            writer.WriteLine($"partial {regexClass.Keyword} {regexClass.Name} {regexClass.Constraints}");
            writer.WriteLine("{");
            writer.Indent++;

            // Generate a name to describe the regex instance.  This includes the method name
            // the user provided and a non-randomized (for determinism) hash of it to try to make
            // the name that much harder to predict.
            Debug.Assert(regexClass.Method is not null);
            string generatedName = $"GeneratedRegex_{regexClass.Method.MethodName}_";
            generatedName += ComputeStringHash(generatedName).ToString("X");

            // Generate the regex type
            EmitRegexMethod(writer, regexClass.Method, generatedName);

            while (writer.Indent != 0)
            {
                writer.Indent--;
                writer.WriteLine("}");
            }

            writer.Flush();
            return sb.ToString();

            // FNV-1a hash function.  The actual algorithm used doesn't matter; just something simple
            // to create a pseudo-random value based on input text.
            static uint ComputeStringHash(string s)
            {
                uint hashCode = 2166136261;
                foreach (char c in s)
                {
                    hashCode = (c ^ hashCode) * 16777619;
                }
                return hashCode;
            }
        }

        /// <summary>Gets whether a given regular expression method is supported by the code generator.</summary>
        private static bool SupportsCustomCodeGeneration(RegexMethod rm) =>
            // The generator doesn't currently know how to emit code for NonBacktracking.
            (rm.Options & RegexOptions.NonBacktracking) == 0;

        /// <summary>Generates the code for a regular expression method.</summary>
        private static void EmitRegexMethod(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            string patternExpression = Literal(rm.Pattern);
            string optionsExpression = $"(global::System.Text.RegularExpressions.RegexOptions)({(int)rm.Options})";
            string timeoutExpression = rm.MatchTimeout == Timeout.Infinite ?
                "global::System.Threading.Timeout.InfiniteTimeSpan" :
                $"global::System.TimeSpan.FromMilliseconds({rm.MatchTimeout.ToString(CultureInfo.InvariantCulture)})";

            writer.WriteLine(s_generatedCodeAttribute);
            writer.WriteLine($"{rm.Modifiers} global::System.Text.RegularExpressions.Regex {rm.MethodName}() => {id}.Instance;");
            writer.WriteLine();
            writer.WriteLine(s_generatedCodeAttribute);
            writer.WriteLine("[global::System.ComponentModel.EditorBrowsable(global::System.ComponentModel.EditorBrowsableState.Never)]");
            writer.WriteLine($"{(writer.Indent != 0 ? "private" : "internal")} sealed class {id} : global::System.Text.RegularExpressions.Regex");
            writer.WriteLine("{");
            writer.Write("    public static global::System.Text.RegularExpressions.Regex Instance { get; } = ");

            // If we can't support custom generation for this regex, spit out a Regex constructor call.
            if (!SupportsCustomCodeGeneration(rm))
            {
                writer.WriteLine($"new global::System.Text.RegularExpressions.Regex({patternExpression}, {optionsExpression}, {timeoutExpression});");
                writer.WriteLine("}");
                return;
            }

            writer.WriteLine($"new {id}();");
            writer.WriteLine();
            writer.WriteLine($"    private {id}()");
            writer.WriteLine($"    {{");
#if DEBUG
            writer.WriteLine("        /*");
            writer.WriteLine($"{rm.Code.Tree.ToString().Replace("*/", @"* /")}");
            writer.WriteLine("        */");
#endif
            writer.WriteLine($"        base.pattern = {patternExpression};");
            writer.WriteLine($"        base.roptions = {optionsExpression};");
            writer.WriteLine($"        base.internalMatchTimeout = {timeoutExpression};");
            writer.WriteLine($"        base.factory = new RunnerFactory();");
            if (rm.Code.Caps is not null)
            {
                writer.Write("        base.Caps = new global::System.Collections.Hashtable {");
                AppendHashtableContents(writer, rm.Code.Caps);
                writer.WriteLine(" };");
            }
            if (rm.Code.Tree.CapNames is not null)
            {
                writer.Write("        base.CapNames = new global::System.Collections.Hashtable {");
                AppendHashtableContents(writer, rm.Code.Tree.CapNames);
                writer.WriteLine(" };");
            }
            if (rm.Code.Tree.CapsList is not null)
            {
                writer.Write("        base.capslist = new string[] {");
                string separator = "";
                foreach (string s in rm.Code.Tree.CapsList)
                {
                    writer.Write(separator);
                    writer.Write(Literal(s));
                    separator = ", ";
                }
                writer.WriteLine(" };");
            }
            writer.WriteLine($"        base.capsize = {rm.Code.CapSize};");
            writer.WriteLine($"        base.InitializeReferences();");
            writer.WriteLine($"    }}");
            writer.WriteLine("    ");
            writer.WriteLine($"    private sealed class RunnerFactory : global::System.Text.RegularExpressions.RegexRunnerFactory");
            writer.WriteLine($"    {{");
            writer.WriteLine($"        protected override global::System.Text.RegularExpressions.RegexRunner CreateInstance() => new Runner();");
            writer.WriteLine();
            writer.WriteLine($"        private sealed class Runner : global::System.Text.RegularExpressions.RegexRunner");
            writer.WriteLine($"        {{");

            // Main implementation methods
            writer.WriteLine($"            protected override void InitTrackCount() => base.runtrackcount = {rm.Code.TrackCount};");
            writer.WriteLine();
            writer.WriteLine($"            protected override bool FindFirstChar()");
            writer.WriteLine($"            {{");
            writer.Indent += 4;
            EmitFindFirstChar(writer, rm, id);
            writer.Indent -= 4;
            writer.WriteLine($"            }}");
            writer.WriteLine();
            writer.WriteLine($"            protected override void Go()");
            writer.WriteLine($"            {{");
            writer.Indent += 4;
            EmitGo(writer, rm, id);
            writer.Indent -= 4;
            writer.WriteLine($"            }}");
            writer.WriteLine($"        }}");
            writer.WriteLine($"    }}");
            writer.WriteLine("}");

            static void AppendHashtableContents(IndentedTextWriter writer, Hashtable ht)
            {
                IDictionaryEnumerator en = ht.GetEnumerator();
                string separator = "";
                while (en.MoveNext())
                {
                    writer.Write(separator);
                    separator = ", ";

                    writer.Write(" { ");
                    if (en.Key is int key)
                    {
                        writer.Write(key);
                    }
                    else
                    {
                        writer.Write($"\"{en.Key}\"");
                    }
                    writer.Write($", {en.Value} }} ");
                }
            }
        }

        /// <summary>Emits the body of the FindFirstChar override.</summary>
        private static void EmitFindFirstChar(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            RegexOptions options = (RegexOptions)rm.Options;
            RegexCode code = rm.Code;
            bool rtl = code.RightToLeft;
            bool hasTextInfo = false;

            // Emit locals initialization
            writer.WriteLine("string runtext = base.runtext!;");
            writer.WriteLine("int runtextpos = base.runtextpos;");
            writer.WriteLine("int runtextend = base.runtextend;");
            if (rtl)
            {
                writer.WriteLine("int runtextbeg = base.runtextbeg;");
            }
            writer.WriteLine("int ch;");
            writer.WriteLine();

            // Generate length check.  If the input isn't long enough to possibly match, fail quickly.
            // It's rare for min required length to be 0, so we don't bother special-casing the check,
            // especially since we want the "return false" code regardless.
            int minRequiredLength = rm.Code.Tree.MinRequiredLength;
            Debug.Assert(minRequiredLength >= 0);
            string clause = !rtl ?
                minRequiredLength switch
                {
                    0 => "if (runtextpos <= runtextend)",
                    1 => "if (runtextpos < runtextend)",
                    _ => $"if (runtextpos < runtextend - {minRequiredLength - 1})"
                } :
                minRequiredLength switch
                {
                    0 => "if (runtextpos >= runtextbeg)",
                    1 => "if (runtextpos > runtextbeg)",
                    _ => $"if (runtextpos - {minRequiredLength - 1} > runtextbeg)"
                };
            using (EmitBlock(writer, clause))
            {
                // Emit any anchors.
                if (!EmitAnchors())
                {
                    // Either anchors weren't specified, or they don't completely root all matches to a specific location.

                    // If whatever search operation we need to perform entails case-insensitive operations
                    // that weren't already handled via creation of sets, we need to get an store the
                    // TextInfo object to use (unless RegexOptions.CultureInvariant was specified).
                    EmitTextInfo(writer, ref hasTextInfo, rm);

                    // Emit the code for whatever find mode has been determined.
                    switch (code.FindOptimizations.FindMode)
                    {
                        case FindNextStartingPositionMode.LeadingPrefix_LeftToRight_CaseSensitive:
                            Debug.Assert(!string.IsNullOrEmpty(code.FindOptimizations.LeadingCaseSensitivePrefix));
                            EmitIndexOf_LeftToRight(code.FindOptimizations.LeadingCaseSensitivePrefix);
                            break;

                        case FindNextStartingPositionMode.LeadingPrefix_RightToLeft_CaseSensitive:
                            Debug.Assert(!string.IsNullOrEmpty(code.FindOptimizations.LeadingCaseSensitivePrefix));
                            EmitIndexOf_RightToLeft(code.FindOptimizations.LeadingCaseSensitivePrefix);
                            break;

                        case FindNextStartingPositionMode.FixedSets_LeftToRight_CaseSensitive:
                        case FindNextStartingPositionMode.FixedSets_LeftToRight_CaseInsensitive:
                        case FindNextStartingPositionMode.LeadingSet_LeftToRight_CaseSensitive:
                        case FindNextStartingPositionMode.LeadingSet_LeftToRight_CaseInsensitive:
                            Debug.Assert(code.FindOptimizations.FixedDistanceSets is { Count: > 0 });
                            EmitFixedSet_LeftToRight();
                            break;

                        case FindNextStartingPositionMode.LeadingSet_RightToLeft_CaseSensitive:
                        case FindNextStartingPositionMode.LeadingSet_RightToLeft_CaseInsensitive:
                            Debug.Assert(code.FindOptimizations.FixedDistanceSets is { Count: > 0 });
                            EmitFixedSet_RightToLeft();
                            break;

                        default:
                            Debug.Fail($"Unexpected mode: {code.FindOptimizations.FindMode}");
                            goto case FindNextStartingPositionMode.NoSearch;

                        case FindNextStartingPositionMode.NoSearch:
                            writer.WriteLine("return true;");
                            break;
                    }
                }
            }
            writer.WriteLine();

            writer.WriteLine("// No match");
            writer.WriteLine("ReturnFalse:");
            writer.WriteLine(!rm.Code.RightToLeft ? "base.runtextpos = runtextend;" : "base.runtextpos = runtextbeg;");
            writer.WriteLine("return false;");

            // Emits any anchors.  Returns true if the anchor roots any match to a specific location and thus no further
            // searching is required; otherwise, false.
            bool EmitAnchors()
            {
                // Generate anchor checks.
                if ((code.FindOptimizations.LeadingAnchor & (RegexPrefixAnalyzer.Beginning | RegexPrefixAnalyzer.Start | RegexPrefixAnalyzer.EndZ | RegexPrefixAnalyzer.End | RegexPrefixAnalyzer.Bol)) != 0)
                {
                    // TODO: Interpreted and Compiled differ in various places as to whether they update positions, as do LTR vs RTL. Determine why.
                    switch (code.FindOptimizations.LeadingAnchor)
                    {
                        case RegexPrefixAnalyzer.Beginning:
                            writer.WriteLine("// Beginning \\A anchor");
                            if (!rtl)
                            {
                                using (EmitBlock(writer, "if (runtextpos > runtextbeg)"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                            }
                            else
                            {
                                // TODO: RegexOptions.Compiled doesn't ever return false here. Instead it updates the position. Why?
                                using (EmitBlock(writer, "if (runtextpos > runtextbeg)"))
                                {
                                    writer.WriteLine("base.runtextpos = runtextbeg;");
                                }
                            }
                            writer.WriteLine("return true;");
                            return true;

                        case RegexPrefixAnalyzer.Start:
                            writer.WriteLine("// Start \\G anchor");
                            if (!rtl)
                            {
                                using (EmitBlock(writer, "if (runtextpos > runtextstart)"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                            }
                            else
                            {
                                // TODO: RegexOptions.Compiled doesn't ever return false here. Instead it updates the position. Why?
                                using (EmitBlock(writer, "if (runtextpos < runtextstart)"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                            }
                            writer.WriteLine("return true;");
                            return true;

                        case RegexPrefixAnalyzer.EndZ:
                            // TODO: Why are the LTR and RTL cases inconsistent here with RegexOptions.Compiled?
                            writer.WriteLine("// End \\Z anchor");
                            if (!rtl)
                            {
                                using (EmitBlock(writer, "if (runtextpos < runtextend - 1)"))
                                {
                                    writer.WriteLine("base.runtextpos = runtextend - 1;");
                                }
                            }
                            else
                            {
                                // TODO: This differs subtly between interpreted and compiled. Why?
                                using (EmitBlock(writer, "if (runtextpos < runtextend - 1 || (runtextpos == runtextend - 1 && runtext[runtextpos] != '\\n'))"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                            }
                            writer.WriteLine("return true;");
                            return true;

                        case RegexPrefixAnalyzer.End:
                            writer.WriteLine("// End \\z anchor");
                            if (!rtl)
                            {
                                using (EmitBlock(writer, "if (runtextpos < runtextend)"))
                                {
                                    writer.WriteLine("base.runtextpos = runtextend;");
                                }
                            }
                            else
                            {
                                using (EmitBlock(writer, "if (runtextpos < runtextend)"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                            }
                            writer.WriteLine("return true;");
                            return true;

                        case RegexPrefixAnalyzer.Bol:
                            // Optimize the handling of a Beginning-Of-Line (BOL) anchor.  BOL is special, in that unlike
                            // other anchors like Beginning, there are potentially multiple places a BOL can match.  So unlike
                            // the other anchors, which all skip all subsequent processing if found, with BOL we just use it
                            // to boost our position to the next line, and then continue normally with any searches.
                            Debug.Assert(!rtl, "RightToLeft isn't implemented and should have been filtered out previously");
                            writer.WriteLine("// Beginning-of-line anchor");
                            using (EmitBlock(writer, "if (runtextpos > runtextbeg && runtext[runtextpos - 1] != '\\n')"))
                            {
                                writer.WriteLine("int newlinePos = runtext.IndexOf('\\n', runtextpos);");
                                using (EmitBlock(writer, "if (newlinePos == -1 || newlinePos + 1 > runtextend)"))
                                {
                                    writer.WriteLine("goto ReturnFalse;");
                                }
                                writer.WriteLine("runtextpos = newlinePos + 1;");
                            }
                            writer.WriteLine();
                            break;
                    }
                }

                return false;
            }

            // Emits a case-sensitive left-to-right prefix search for a string at the beginning of the pattern.
            void EmitIndexOf_LeftToRight(string prefix)
            {
                writer.WriteLine($"int i = global::System.MemoryExtensions.IndexOf(global::System.MemoryExtensions.AsSpan(runtext, runtextpos, runtextend - runtextpos), {Literal(prefix)});");
                writer.WriteLine("if (i >= 0)");
                writer.WriteLine("{");
                writer.WriteLine("    base.runtextpos = runtextpos + i;");
                writer.WriteLine("    return true;");
                writer.WriteLine("}");
            }

            // Emits a case-sensitive right-to-left prefix search for a string at the beginning of the pattern.
            void EmitIndexOf_RightToLeft(string prefix)
            {
                writer.WriteLine($"int i = global::System.MemoryExtensions.LastIndexOf(global::System.MemoryExtensions.AsSpan(runtext, runtextbeg, runtextpos - runtextbeg), {Literal(prefix)});");
                writer.WriteLine("if (i >= 0)");
                writer.WriteLine("{");
                writer.WriteLine($"    base.runtextpos = runtextbeg + i + {prefix.Length};");
                writer.WriteLine("    return true;");
                writer.WriteLine("}");
            }

            // Emits a right-to-left search for a set at a fixed position from the start of the pattern.
            // (Currently that position will always be a distance of 0, meaning the start of the pattern itself.)
            void EmitFixedSet_RightToLeft()
            {
                (char[]? Chars, string Set, int Distance, bool CaseInsensitive) set = code.FindOptimizations.FixedDistanceSets![0];
                Debug.Assert(set.Distance == 0);

                if (set.Chars is { Length: 1 } && !set.CaseInsensitive)
                {
                    writer.WriteLine($"int i = global::System.MemoryExtensions.LastIndexOf(global::System.MemoryExtensions.AsSpan(runtext, runtextbeg, runtextpos - runtextbeg), {Literal(set.Chars[0])});");
                    writer.WriteLine("if (i >= 0)");
                    writer.WriteLine("{");
                    writer.WriteLine("    base.runtextpos = runtextbeg + i + 1;");
                    writer.WriteLine("    return true;");
                    writer.WriteLine("}");
                }
                else
                {
                    using (EmitBlock(writer, "for (int i = runtextpos - 1; i >= runtextbeg; i--)"))
                    {
                        using (EmitBlock(writer, $"if ({MatchCharacterClass(hasTextInfo, options, "runtext[i]", set.Set, set.CaseInsensitive)})"))
                        {
                            writer.WriteLine("base.runtextpos = i + 1;");
                            writer.WriteLine("return true;");
                        }
                    }
                }
            }

            // Emits a left-to-right search for a set at a fixed position from the start of the pattern,
            // and potentially other sets at other fixed positions in the pattern.
            void EmitFixedSet_LeftToRight()
            {
                List<(char[]? Chars, string Set, int Distance, bool CaseInsensitive)>? sets = code.FindOptimizations.FixedDistanceSets;
                (char[]? Chars, string Set, int Distance, bool CaseInsensitive) primarySet = sets![0];
                const int MaxSets = 4;
                int setsToUse = Math.Min(sets.Count, MaxSets);

                // If we can use IndexOf{Any}, try to accelerate the skip loop via vectorization to match the first prefix.
                // We can use it if this is a case-sensitive class with a small number of characters in the class.
                int setIndex = 0;
                bool canUseIndexOf = !primarySet.CaseInsensitive && primarySet.Chars is not null;
                bool needLoop = !canUseIndexOf || setsToUse > 1;

                FinishEmitScope loopBlock = default;
                if (needLoop)
                {
                    writer.WriteLine("global::System.ReadOnlySpan<char> span = global::System.MemoryExtensions.AsSpan(runtext, runtextpos, runtextend - runtextpos);");
                    string upperBound = "span.Length" + (setsToUse > 1 || primarySet.Distance != 0 ? $" - {minRequiredLength - 1}" : "");
                    loopBlock = EmitBlock(writer, $"for (int i = 0; i < {upperBound}; i++)");
                }

                if (canUseIndexOf)
                {
                    string span = needLoop ?
                        "span" :
                        "global::System.MemoryExtensions.AsSpan(runtext, runtextpos, runtextend - runtextpos)";

                    span = (needLoop, primarySet.Distance) switch
                    {
                        (false, 0) => span,
                        (true, 0) => $"{span}.Slice(i)",
                        (false, _) => $"{span}.Slice({primarySet.Distance})",
                        (true, _) => $"{span}.Slice(i + {primarySet.Distance})",
                    };

                    string indexOf = primarySet.Chars!.Length switch
                    {
                        1 => $"global::System.MemoryExtensions.IndexOf({span}, {Literal(primarySet.Chars[0])})",
                        2 => $"global::System.MemoryExtensions.IndexOfAny({span}, {Literal(primarySet.Chars[0])}, {Literal(primarySet.Chars[1])})",
                        3 => $"global::System.MemoryExtensions.IndexOfAny({span}, {Literal(primarySet.Chars[0])}, {Literal(primarySet.Chars[1])}, {Literal(primarySet.Chars[2])})",
                        _ => $"global::System.MemoryExtensions.IndexOfAny({span}, {Literal(new string(primarySet.Chars))})",
                    };

                    if (needLoop)
                    {
                        writer.WriteLine($"int indexOfPos = {indexOf};");
                        using (EmitBlock(writer, "if (indexOfPos < 0)"))
                        {
                            writer.WriteLine("goto ReturnFalse;");
                        }
                        writer.WriteLine("i += indexOfPos;");
                        writer.WriteLine();

                        if (setsToUse > 1)
                        {
                            using (EmitBlock(writer, $"if (i >= span.Length - {minRequiredLength - 1})"))
                            {
                                writer.WriteLine("goto ReturnFalse;");
                            }
                            writer.WriteLine();
                        }
                    }
                    else
                    {
                        writer.WriteLine($"int i = {indexOf};");
                        using (EmitBlock(writer, "if (i >= 0)"))
                        {
                            writer.WriteLine("base.runtextpos = runtextpos + i;");
                            writer.WriteLine("return true;");
                        }
                    }

                    setIndex = 1;
                }

                if (needLoop)
                {
                    Debug.Assert(setIndex == 0 || setIndex == 1);
                    bool hasCharClassConditions = false;
                    if (setIndex < setsToUse)
                    {
                        // if (CharInClass(textSpan[i + charClassIndex], prefix[0], "...") &&
                        //     ...)
                        Debug.Assert(needLoop);
                        int start = setIndex;
                        for (; setIndex < setsToUse; setIndex++)
                        {
                            string spanIndex = $"span[i{(sets[setIndex].Distance > 0 ? $" + {sets[setIndex].Distance}" : "")}]";
                            string charInClassExpr = MatchCharacterClass(hasTextInfo, options, spanIndex, sets[setIndex].Set, sets[setIndex].CaseInsensitive);

                            if (setIndex == start)
                            {
                                writer.Write($"if ({charInClassExpr}");
                            }
                            else
                            {
                                writer.WriteLine(" &&");
                                writer.Write($"    {charInClassExpr}");
                            }
                        }
                        writer.WriteLine(")");
                        hasCharClassConditions = true;
                    }

                    using (hasCharClassConditions ? EmitBlock(writer, null) : default)
                    {
                        writer.WriteLine("base.runtextpos = runtextpos + i;");
                        writer.WriteLine("return true;");
                    }
                }

                loopBlock.Dispose();
            }

            // If a TextInfo is needed to perform ToLower operations, emits a local initialized to the TextInfo to use.
            static void EmitTextInfo(IndentedTextWriter writer, ref bool hasTextInfo, RegexMethod rm)
            {
                // Emit local to store current culture if needed
                if ((rm.Options & RegexOptions.CultureInvariant) == 0)
                {
                    bool needsCulture = rm.Code.FindOptimizations.FindMode switch
                    {
                        FindNextStartingPositionMode.FixedLiteral_LeftToRight_CaseInsensitive or
                        FindNextStartingPositionMode.LeadingLiteral_RightToLeft_CaseInsensitive or
                        FindNextStartingPositionMode.FixedSets_LeftToRight_CaseInsensitive or
                        FindNextStartingPositionMode.LeadingSet_LeftToRight_CaseInsensitive or
                        FindNextStartingPositionMode.LeadingSet_RightToLeft_CaseInsensitive => true,

                        _ when rm.Code.FindOptimizations.FixedDistanceSets is List<(char[]? Chars, string Set, int Distance, bool CaseInsensitive)> sets => sets.Exists(set => set.CaseInsensitive),

                        _ => false,
                    };

                    if (needsCulture)
                    {
                        hasTextInfo = true;
                        writer.WriteLine("global::System.Globalization.TextInfo textInfo = global::System.Globalization.CultureInfo.CurrentCulture.TextInfo;");
                    }
                }
            }
        }

        /// <summary>Emits the body of the Go override.</summary>
        private static void EmitGo(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            Debug.Assert(rm.Code.Tree.Root.Type == RegexNode.Capture);

            if ((rm.Options & RegexOptions.NonBacktracking) != 0)
            {
                EmitNonBacktrackingGo(writer, rm, id);
                return;
            }
            RegexNode root = rm.Code.Tree.Root;
            if (!ExceedsMaxDepthForSimpleCodeGeneration(root) &&
                root.Child(0).SupportsSimplifiedCodeGenerationImplementation() &&
                (((RegexOptions)root.Options) & RegexOptions.RightToLeft) == 0)
            {
                EmitSimplifiedGo(writer, rm, id);
                return;
            }

            EmitCompleteGo(writer, rm, id);

            // Deep RegexNode trees used with the simplified code generator can result in
            // emitting C# code that exceeds C# compiler limitations, leading to "CS8078: An
            // expression is too long or complex to compile". Place an artificial limit on
            // max tree depth in order to mitigate such issues.
            static bool ExceedsMaxDepthForSimpleCodeGeneration(RegexNode node, int maxDepth = 30)
            {
                if (maxDepth <= 0)
                {
                    return true;
                }

                int childCount = node.ChildCount();
                for (int i = 0; i < childCount; i++)
                {
                    if (ExceedsMaxDepthForSimpleCodeGeneration(node.Child(i), maxDepth - 1))
                    {
                        return true;
                    }
                }

                return false;
            }
        }

        /// <summary>Emits the body of a Go method supporting RegexOptions.NonBacktracking.</summary>
        private static void EmitNonBacktrackingGo(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            // TODO: Implement this and remove SupportsCustomCodeGeneration.
        }

        /// <summary>Emits the body of a simplified Go implementation that's possible when there's minimal backtracking required by the expression.</summary>
        private static void EmitSimplifiedGo(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            // Arbitrary limit for unrolling vs creating a loop.  We want to balance size in the generated
            // code with other costs, like the (small) overhead of slicing to create the temp span to iterate.
            const int MaxUnrollSize = 16;

            RegexOptions options = (RegexOptions)rm.Options;
            RegexCode code = rm.Code;
            bool rtl = code.RightToLeft;
            bool hasTimeout = false;

            int localCounter = 0;
            string NextLocalName(string prefix) => $"{prefix}{localCounter++}";

            RegexNode node = rm.Code.Tree.Root;
            Debug.Assert(node.Type == RegexNode.Capture, "Every generated tree should begin with a capture node");
            Debug.Assert(node.ChildCount() == 1, "Capture nodes should have one child");

            // Skip the Capture node. We handle the implicit root capture specially.
            node = node.Child(0);

            // If there's any backtracking in the expression, nodes may emit labels that their peers
            // need to jump to. Scopes (which we emit for readability) get in the way of that.  As such,
            // for nodes that emit such labels, we emit faux, commented-out scopes instead.
            HashSet<RegexNode> nodesWithCrossScopeLabels = NodesWithCrossScopeLabels(node);

            // In some limited cases, FindFirstChar will only return true if it successfully matched the whole thing.
            // This is the case, in particular, for strings.  We can special case these to do essentially nothing
            // in Go other than emit the capture.
            if (!IsCaseInsensitive(node)) // FindFirstChar may not be 100% accurate on casing in all cultures
            {
                switch (node.Type)
                {
                    case RegexNode.Multi:
                    case RegexNode.Notone:
                    case RegexNode.One:
                    case RegexNode.Set:
                        writer.WriteLine($"int start = base.runtextpos;");
                        writer.WriteLine($"int end = start + {(node.Type == RegexNode.Multi ? node.Str!.Length : 1)};");
                        writer.WriteLine("base.Capture(0, start, end);");
                        writer.WriteLine("base.runtextpos = end;");
                        return;
                }
            }

            // Declare some locals.
            string textSpanLocal = "textSpan";
            writer.WriteLine("string runtext = base.runtext!;");
            writer.WriteLine("int runtextpos = base.runtextpos;");
            writer.WriteLine("int runtextend = base.runtextend;");
            writer.WriteLine("int originalruntextpos = runtextpos;");
            writer.WriteLine("global::System.ReadOnlySpan<byte> byteSpan;");
            writer.WriteLine("char ch;");
            hasTimeout = EmitLoopTimeoutCounterIfNeeded(writer, rm);

            // TextInfo textInfo = CultureInfo.CurrentCulture.TextInfo; // only if the whole expression or any subportion is ignoring case, and we're not using invariant
            bool hasTextInfo = EmitInitializeCultureForGoIfNecessary(writer, rm);

            // The implementation tries to use const indexes into the span wherever possible, which we can do
            // in all places except for variable-length loops.  For everything else, we know at any point in
            // the regex exactly how far into it we are, and we can use that to index into the span created
            // at the beginning of the routine to begin at exactly where we're starting in the input.  For
            // variable-length loops, we index at this textSpanPos + i, and then after the loop we slice the input
            // by i so that this position is still accurate for everything after it.
            int textSpanPos = 0;
            LoadTextSpanLocal(writer, defineLocal: true);
            writer.WriteLine();

            int labelCounter = 0;
            string DefineLabel(string prefix = "L") => $"{prefix}{labelCounter++}";
            void MarkLabel(string label, bool addEmptyStatement = false) => writer.WriteLine($"{label}:{(addEmptyStatement ? " ;" : "")}");
            void Goto(string label) => writer.WriteLine($"goto {label};");
            string doneLabel = "NoMatch";
            string originalDoneLabel = doneLabel;

            // Emit the code for all nodes in the tree.
            bool expressionHasCaptures = (node.Options & RegexNode.HasCapturesFlag) != 0;
            EmitNode(node);

            // Emit success
            writer.WriteLine("// Match");
            if (textSpanPos > 0)
            {
                EmitAdd(writer, "runtextpos", textSpanPos);
            }
            writer.WriteLine("base.runtextpos = runtextpos;");
            writer.WriteLine("base.Capture(0, originalruntextpos, runtextpos);");
            writer.WriteLine("return;");
            writer.WriteLine();

            // Emit failure
            writer.WriteLine("// No match");
            MarkLabel(originalDoneLabel, !expressionHasCaptures);
            if (expressionHasCaptures)
            {
                EmitUncaptureUntil("0");
            }
            return;

            static bool IsCaseInsensitive(RegexNode node) => (node.Options & RegexOptions.IgnoreCase) != 0;

            // Creates a span for runtext starting at runtextpos until base.runtextend.
            void LoadTextSpanLocal(IndentedTextWriter writer, bool defineLocal = false)
            {
                if (defineLocal)
                {
                    writer.Write("global::System.ReadOnlySpan<char> ");
                }
                writer.WriteLine($"{textSpanLocal} = global::System.MemoryExtensions.AsSpan(runtext, runtextpos, runtextend - runtextpos);");
            }

            // Emits the sum of a constant and a value from a local.
            string Sum(int constant, string? local = null) =>
                local is null ? constant.ToString() :
                constant == 0 ? local :
                $"{constant} + {local}";

            // Emits a check that the span is large enough at the currently known static position to handle the required additional length.
            void EmitSpanLengthCheck(int requiredLength, string? dynamicRequiredLength = null)
            {
                Debug.Assert(requiredLength > 0);
                using (EmitBlock(writer, $"if ({SpanLengthCheck(requiredLength, dynamicRequiredLength)})"))
                {
                    writer.WriteLine($"goto {doneLabel};");
                }
            }

            string SpanLengthCheck(int requiredLength, string? dynamicRequiredLength = null) =>
                $"(uint){textSpanLocal}.Length < {Sum(textSpanPos + requiredLength, dynamicRequiredLength)}";

            // Adds the value of textSpanPos into the runtextpos local, slices textspan by the corresponding amount,
            // and zeros out textSpanPos.
            void TransferTextSpanPosToRunTextPos()
            {
                if (textSpanPos > 0)
                {
                    EmitAdd(writer, "runtextpos", textSpanPos);
                    writer.WriteLine($"{textSpanLocal} = {textSpanLocal}.Slice({textSpanPos});");
                    textSpanPos = 0;
                }
            }

            string AddTextSpanPos() => textSpanPos > 0 ? $" + {textSpanPos}" : "";

            // Emits the code for an atomic alternate, one that once a branch successfully matches is non-backtracking into it.
            // This amounts to generating the code for each branch, with failures in a branch resetting state to what it was initially
            // and then jumping to the next branch. We don't need to worry about uncapturing, because capturing is only allowed for the
            // implicit capture that happens for the whole match at the end.
            void EmitAtomicAlternate(RegexNode node)
            {
                int childCount = node.ChildCount();
                Debug.Assert(childCount >= 2);

                // If no child branch overlaps with another child branch, we can emit more streamlined code
                // that avoids checking unnecessary branches, e.g. with abc|def|ghi if the next character in
                // the input is 'a', we needn't try the def or ghi branches.  A simple, relatively common case
                // of this is if every branch begins with a specific, unique character, in which case
                // the whole alternation can be treated as a simple switch, so we special-case that.
                var seenChars = new HashSet<char>();
                bool allBranchesStartUnique = true;
                for (int i = 0; i < childCount; i++)
                {
                    if (node.Child(i).FindBranchOneOrMultiStart() is not RegexNode oneOrMulti ||
                        !seenChars.Add(oneOrMulti.FirstCharOfOneOrMulti()))
                    {
                        allBranchesStartUnique = false;
                        break;
                    }
                }

                if (allBranchesStartUnique)
                {
                    // Note: This optimization does not exist with RegexOptions.Compiled.  Here we rely on the
                    // C# compiler to lower the C# switch statement with appropriate optimizations.
                    EmitSwitchedBranches();
                }
                else
                {
                    EmitAllBranches();
                }

                void EmitSwitchedBranches()
                {
                    EmitSpanLengthCheck(1);
                    writer.WriteLine();

                    using (EmitBlock(writer, $"switch ({ToLowerIfNeeded(hasTextInfo, options, $"{textSpanLocal}[{textSpanPos++}]", IsCaseInsensitive(node))})"))
                    {
                        int startingTextSpanPos = textSpanPos;
                        for (int i = 0; i < childCount; i++)
                        {
                            textSpanPos = startingTextSpanPos;

                            RegexNode child = node.Child(i);
                            Debug.Assert(child.Type is RegexNode.One or RegexNode.Multi or RegexNode.Concatenate, child.Description());
                            Debug.Assert(child.Type is not RegexNode.Concatenate || (child.ChildCount() >= 2 && child.Child(0).Type is RegexNode.One or RegexNode.Multi));

                            RegexNode? childStart = child.FindBranchOneOrMultiStart();
                            Debug.Assert(childStart is not null, child.Description());

                            writer.WriteLine($"case {Literal(childStart.FirstCharOfOneOrMulti())}:");
                            writer.Indent++;

                            // Emit the code for the branch, without the first character that was already matched in the switch.
                            switch (child.Type)
                            {
                                case RegexNode.Multi:
                                    EmitNode(CloneMultiWithoutFirstChar(child));
                                    break;

                                case RegexNode.Concatenate:
                                    var newConcat = new RegexNode(RegexNode.Concatenate, child.Options);
                                    if (childStart.Type == RegexNode.Multi)
                                    {
                                        newConcat.AddChild(CloneMultiWithoutFirstChar(childStart));
                                    }
                                    int concatChildCount = child.ChildCount();
                                    for (int j = 1; j < concatChildCount; j++)
                                    {
                                        newConcat.AddChild(child.Child(j));
                                    }
                                    EmitNode(newConcat.Reduce());
                                    break;

                                static RegexNode CloneMultiWithoutFirstChar(RegexNode node)
                                {
                                    Debug.Assert(node.Type is RegexNode.Multi);
                                    Debug.Assert(node.Str!.Length >= 2);
                                    return node.Str!.Length == 2 ?
                                        new RegexNode(RegexNode.One, node.Options, node.Str![1]) :
                                        new RegexNode(RegexNode.Multi, node.Options, node.Str!.Substring(1));
                                }
                            }

                            // If we get here in the generated code, the branch completed successfully.
                            // Before jumping to the end, we need to zero out textSpanPos, so that no
                            // matter what the value is after the branch, whatever follows the alternate
                            // will see the same textSpanPos.
                            TransferTextSpanPosToRunTextPos();
                            writer.WriteLine($"break;");
                            writer.WriteLine();

                            writer.Indent--;
                        }

                        // Default branch if the character didn't match the start of any branches.
                        writer.WriteLine("default:");
                        writer.Indent++;
                        writer.WriteLine($"goto {doneLabel};");
                        writer.Indent--;
                    }
                }

                void EmitAllBranches()
                {
                    // Label to jump to when any branch completes successfully.
                    string doneAlternateLabel = DefineLabel("Match");

                    // Save off runtextpos.  We'll need to reset this each time a branch fails.
                    string startingRunTextPosName = NextLocalName("startingRunTextPos");
                    writer.WriteLine($"int {startingRunTextPosName} = runtextpos;");
                    int startingTextSpanPos = textSpanPos;

                    // If the alternation's branches contain captures, save off the relevant
                    // state.  Note that this is only about subexpressions within the alternation,
                    // as the alternation is atomic, so we're not concerned about captures after
                    // the alternation.
                    bool hasStartingCrawlpos = (node.Options & RegexNode.HasCapturesFlag) != 0;
                    string startingCrawlPos = NextLocalName("startingCrawlPos");
                    if (hasStartingCrawlpos)
                    {
                        writer.WriteLine($"int {startingCrawlPos} = base.Crawlpos();");
                    }
                    writer.WriteLine();

                    // A failure in a branch other than the last should jump to the next
                    // branch, not to the final done.
                    string postAlternateDoneLabel = doneLabel;

                    for (int i = 0; i < childCount - 1; i++)
                    {
                        using var __ = EmitScope(writer, $"Branch {i}");

                        string nextBranch = DefineLabel("NoMatch");
                        doneLabel = nextBranch;

                        // Emit the code for each branch.
                        EmitNode(node.Child(i));

                        // If we get here in the generated code, the branch completed successfully.
                        // Before jumping to the end, we need to zero out textSpanPos, so that no
                        // matter what the value is after the branch, whatever follows the alternate
                        // will see the same textSpanPos.
                        TransferTextSpanPosToRunTextPos();
                        writer.WriteLine($"goto {doneAlternateLabel};");

                        // Reset state for next branch and loop around to generate it.  This includes
                        // setting runtextpos back to what it was at the beginning of the alternation,
                        // updating textSpan to be the full length it was, and if there's a capture that
                        // needs to be reset, uncapturing it.
                        MarkLabel(nextBranch);
                        writer.WriteLine($"runtextpos = {startingRunTextPosName};");
                        LoadTextSpanLocal(writer);
                        textSpanPos = startingTextSpanPos;
                        if (hasStartingCrawlpos)
                        {
                            EmitUncaptureUntil(startingCrawlPos);
                        }
                    }

                    // If the final branch fails, that's like any other failure, and we jump to
                    // done (unless we have captures we need to unwind first, in which case we uncapture
                    // them and then jump to done).
                    using (EmitScope(writer, $"Branch {childCount - 1}"))
                    {
                        if (hasStartingCrawlpos)
                        {
                            string uncapture = DefineLabel("Uncapture");
                            doneLabel = uncapture;
                            EmitNode(node.Child(childCount - 1));
                            doneLabel = postAlternateDoneLabel;
                            TransferTextSpanPosToRunTextPos();
                            writer.WriteLine($"goto {doneAlternateLabel};");
                            MarkLabel(uncapture);
                            EmitUncaptureUntil(startingCrawlPos);
                            writer.WriteLine($"goto {doneLabel};");
                        }
                        else
                        {
                            doneLabel = postAlternateDoneLabel;
                            EmitNode(node.Child(childCount - 1));
                            TransferTextSpanPosToRunTextPos();
                        }
                    }

                    // Successfully completed the alternate.
                    MarkLabel(doneAlternateLabel);
                    writer.WriteLine(";");
                    Debug.Assert(textSpanPos == 0);
                }
            }

            // Emits the code for a Capture node.
            void EmitCapture(RegexNode node, RegexNode? subsequent = null)
            {
                Debug.Assert(node.N == -1);

                // Get the capture number.  This needs to be kept in sync with MapCapNum in RegexWriter.
                Debug.Assert(node.Type == RegexNode.Capture);
                Debug.Assert(node.N == -1, "Currently only support capnum, not uncapnum");
                int capnum = node.M;
                if (capnum != -1 && rm.Code.Caps != null)
                {
                    capnum = (int)rm.Code.Caps[capnum]!;
                }

                TransferTextSpanPosToRunTextPos();
                string startingRunTextPosName = NextLocalName("startingRunTextPos");
                writer.WriteLine($"int {startingRunTextPosName} = runtextpos;");

                // Emit child node.
                EmitNode(node.Child(0), subsequent);

                TransferTextSpanPosToRunTextPos();
                writer.WriteLine($"base.Capture({capnum}, {startingRunTextPosName}, runtextpos);");
            }

            // Emits code to unwind the capture stack until the crawl position specified in the provided local.
            void EmitUncaptureUntil(string crawlpos)
            {
                using (EmitBlock(writer, $"while (base.Crawlpos() != {crawlpos})"))
                {
                    writer.WriteLine("base.Uncapture();");
                }
            }

            // Emits the code to handle a positive lookahead assertion.
            void EmitPositiveLookaheadAssertion(RegexNode node)
            {
                // Save off runtextpos.  We'll need to reset this upon successful completion of the lookahead.
                string startingRunTextPosName = NextLocalName("startingRunTextPos");
                writer.WriteLine($"int {startingRunTextPosName} = runtextpos;");
                int startingTextSpanPos = textSpanPos;

                // Emit the child.
                EmitNode(node.Child(0));

                // After the child completes successfully, reset the text positions.
                // Do not reset captures, which persist beyond the lookahead.
                writer.WriteLine($"runtextpos = {startingRunTextPosName};");
                LoadTextSpanLocal(writer);
                textSpanPos = startingTextSpanPos;
            }

            // Emits the code to handle a negative lookahead assertion.
            void EmitNegativeLookaheadAssertion(RegexNode node)
            {
                // Save off runtextpos.  We'll need to reset this upon successful completion of the lookahead.
                string startingRunTextPosName = NextLocalName("startingRunTextPos");
                writer.WriteLine($"int {startingRunTextPosName} = runtextpos;");
                int startingTextSpanPos = textSpanPos;

                string originalDoneLabel = doneLabel;
                string negativeLookaheadDoneLabel = DefineLabel("Match");
                doneLabel = negativeLookaheadDoneLabel;

                // Emit the child.
                EmitNode(node.Child(0));

                // If the generated code ends up here, it matched the lookahead, which actually
                // means failure for a _negative_ lookahead, so we need to jump to the original done.
                Goto(originalDoneLabel);

                // Failures (success for a negative lookahead) jump here.
                MarkLabel(negativeLookaheadDoneLabel);
                Debug.Assert(doneLabel == negativeLookaheadDoneLabel);
                doneLabel = originalDoneLabel;

                // After the child completes in failure (success for negative lookahead), reset the text positions.
                writer.WriteLine($"runtextpos = {startingRunTextPosName};");
                LoadTextSpanLocal(writer);
                textSpanPos = startingTextSpanPos;
            }

            static string DescribeNode(RegexNode node) => SymbolDisplay.FormatLiteral(node.Description(), quote: false);

            // Emits the code for the node.
            void EmitNode(RegexNode node, RegexNode? subsequent = null, bool emitLengthChecksIfRequired = true)
            {
                if (!StackHelper.TryEnsureSufficientExecutionStack())
                {
                    StackHelper.CallOnEmptyStack(EmitNode, node, subsequent, emitLengthChecksIfRequired);
                    return;
                }

                // Separate out several node types that, for conciseness, don't need a header and scope written into the source.
                switch (node.Type)
                {
                    case RegexNode.Empty:
                        return;

                    case RegexNode.Atomic:
                        EmitNode(node.Child(0), subsequent);
                        return;
                }

                // Put the node's code into its own scope. If the node contains labels that may need to
                // be visible outside of its scope, the scope is still emitted for clarity but is commented out.
                using var _ = EmitScope(writer, DescribeNode(node), nodesWithCrossScopeLabels.Contains(node));

                switch (node.Type)
                {
                    case RegexNode.One:
                    case RegexNode.Notone:
                    case RegexNode.Set:
                        EmitSingleChar(node, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Boundary:
                    case RegexNode.NonBoundary:
                    case RegexNode.ECMABoundary:
                    case RegexNode.NonECMABoundary:
                        EmitBoundary(node);
                        break;

                    case RegexNode.Beginning:
                    case RegexNode.Start:
                    case RegexNode.Bol:
                    case RegexNode.Eol:
                    case RegexNode.End:
                    case RegexNode.EndZ:
                        EmitAnchors(node);
                        break;

                    case RegexNode.Multi:
                        EmitMultiChar(node, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Oneloopatomic:
                    case RegexNode.Notoneloopatomic:
                    case RegexNode.Setloopatomic:
                        EmitSingleCharAtomicLoop(node, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Loop:
                        EmitAtomicNodeLoop(node);
                        break;

                    case RegexNode.Onelazy:
                    case RegexNode.Notonelazy:
                    case RegexNode.Setlazy:
                    case RegexNode.Lazyloop:
                        EmitLazy(node, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Alternate:
                        EmitAtomicAlternate(node);
                        break;

                    case RegexNode.Oneloop:
                    case RegexNode.Notoneloop:
                    case RegexNode.Setloop:
                        EmitSingleCharLoop(node, subsequent, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Concatenate:
                        EmitConcatenation(node, subsequent, emitLengthChecksIfRequired);
                        break;

                    case RegexNode.Capture:
                        EmitCapture(node, subsequent);
                        break;

                    case RegexNode.Require:
                        EmitPositiveLookaheadAssertion(node);
                        break;

                    case RegexNode.Prevent:
                        EmitNegativeLookaheadAssertion(node);
                        break;

                    case RegexNode.Nothing:
                        writer.WriteLine($"goto {doneLabel};");
                        break;

                    case RegexNode.UpdateBumpalong:
                        EmitUpdateBumpalong();
                        break;

                    default:
                        Debug.Fail($"Unexpected node type: {node.Type}");
                        break;
                }
            }

            /// <summary>
            /// Provides a set of all the nodes in the node tree that contains a node
            /// which triggers backtracking and thus may emit labels that peer nodes need
            /// to be able to see.
            /// </summary>
            static HashSet<RegexNode> NodesWithCrossScopeLabels(RegexNode node)
            {
                var results = new HashSet<RegexNode>();
                NodesWithCrossScopeLabels(node, results);
                return results;

                static bool NodesWithCrossScopeLabels(RegexNode node, HashSet<RegexNode> results)
                {
                    if (!StackHelper.TryEnsureSufficientExecutionStack())
                    {
                        return StackHelper.CallOnEmptyStack(NodesWithCrossScopeLabels, node, results);
                    }

                    // Nodes that trigger backtracking and thus may emit labels that need to be reached by non-descendants.
                    bool contains = node.InstigatesBacktracking;

                    int childcount = node.ChildCount();
                    for (int i = 0; i < childcount; i++)
                    {
                        contains |= NodesWithCrossScopeLabels(node.Child(i), results);
                    }

                    if (contains)
                    {
                        results.Add(node);
                    }

                    return contains;
                }
            }

            // Emits the code to handle updating base.runtextpos to runtextpos in response to
            // an UpdateBumpalong node.  This is used when we want to inform the scan loop that
            // it should bump from this location rather than from the original location.
            void EmitUpdateBumpalong()
            {
                TransferTextSpanPosToRunTextPos();
                writer.WriteLine("base.runtextpos = runtextpos;");
            }

            void EmitConcatenation(RegexNode node, RegexNode? subsequent, bool emitLengthChecksIfRequired)
            {
                int childCount = node.ChildCount();
                for (int i = 0; i < childCount; i++)
                {
                    if (emitLengthChecksIfRequired && node.TryGetJoinableLengthCheckChildRange(i, out int requiredLength, out int exclusiveEnd))
                    {
                        bool wroteClauses = true;
                        writer.Write($"if ({SpanLengthCheck(requiredLength)}");

                        while (i < exclusiveEnd)
                        {
                            for (; i < exclusiveEnd; i++)
                            {
                                void WriteSingleCharChild(RegexNode child)
                                {
                                    if (wroteClauses)
                                    {
                                        writer.WriteLine(" ||");
                                        writer.Write("    ");
                                    }
                                    else
                                    {
                                        writer.Write("if (");
                                    }
                                    EmitSingleChar(child, emitLengthCheck: false, clauseOnly: true);
                                    wroteClauses = true;
                                }

                                RegexNode child = node.Child(i);
                                if (child.Type is RegexNode.One or RegexNode.Notone or RegexNode.Set)
                                {
                                    WriteSingleCharChild(child);
                                    writer.Write($" /* {DescribeNode(child)} */");
                                }
                                else if (child.Type is RegexNode.Oneloop or RegexNode.Onelazy or RegexNode.Oneloopatomic or
                                                       RegexNode.Setloop or RegexNode.Setlazy or RegexNode.Setloopatomic or
                                                       RegexNode.Notoneloop or RegexNode.Notonelazy or RegexNode.Notoneloopatomic &&
                                         child.M == child.N &&
                                         child.M <= MaxUnrollSize)
                                {
                                    for (int c = 0; c < child.M; c++)
                                    {
                                        WriteSingleCharChild(child);
                                        if (c == 0)
                                        {
                                            writer.Write($" /* {DescribeNode(child)} */");
                                        }
                                    }
                                }
                                else
                                {
                                    break;
                                }
                            }

                            if (wroteClauses)
                            {
                                writer.WriteLine(")");
                                using (EmitBlock(writer, null))
                                {
                                    writer.WriteLine($"goto {doneLabel};");
                                }
                                wroteClauses = false;
                            }

                            if (i < exclusiveEnd)
                            {
                                writer.WriteLine();
                                EmitNode(node.Child(i), i + 1 < childCount ? node.Child(i + 1) : subsequent, emitLengthChecksIfRequired: false);
                                i++;
                            }
                        }

                        i--;
                    }
                    else
                    {
                        EmitNode(node.Child(i), i + 1 < childCount ? node.Child(i + 1) : subsequent, emitLengthChecksIfRequired: emitLengthChecksIfRequired);
                    }
                }
            }

            // Emits the code to handle a single-character match.
            void EmitSingleChar(RegexNode node, bool emitLengthCheck = true, string? offset = null, bool clauseOnly = false)
            {
                // This only emits a single check, but it's called from the looping constructs in a loop
                // to generate the code for a single check, so we map those looping constructs to the
                // appropriate single check.

                string expr = $"{textSpanLocal}[{Sum(textSpanPos, offset)}]";

                if (node.IsSetFamily)
                {
                    expr = $"!{MatchCharacterClass(hasTextInfo, options, expr, node.Str!, IsCaseInsensitive(node))}";
                }
                else
                {
                    expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive(node));
                    expr = $"{expr} {(node.IsOneFamily ? "!=" : "==")} {Literal(node.Ch)}";
                }

                if (clauseOnly)
                {
                    writer.Write(expr);
                }
                else
                {
                    using (EmitBlock(writer, emitLengthCheck ? $"if ({SpanLengthCheck(1, offset)} || {expr})" : $"if ({expr})"))
                    {
                        writer.WriteLine($"goto {doneLabel};");
                    }
                }

                textSpanPos++;
            }

            // Emits the code to handle a boundary check on a character.
            void EmitBoundary(RegexNode node)
            {
                string call;
                switch (node.Type)
                {
                    case RegexNode.Boundary:
                        call = "!base.IsBoundary";
                        break;

                    case RegexNode.NonBoundary:
                        call = "base.IsBoundary";
                        break;

                    case RegexNode.ECMABoundary:
                        call = "!base.IsECMABoundary";
                        break;

                    default:
                        Debug.Assert(node.Type == RegexNode.NonECMABoundary);
                        call = "base.IsECMABoundary";
                        break;
                }

                using (EmitBlock(writer, $"if ({call}(runtextpos{AddTextSpanPos()}, base.runtextbeg, runtextend))"))
                {
                    writer.WriteLine($"goto {doneLabel};");
                }
            }

            // Emits the code to handle various anchors.
            void EmitAnchors(RegexNode node)
            {
                Debug.Assert(textSpanPos >= 0);
                switch (node.Type)
                {
                    case RegexNode.Beginning:
                    case RegexNode.Start:
                        if (textSpanPos > 0)
                        {
                            // If we statically know we've already matched part of the regex, there's no way we're at the
                            // beginning or start, as we've already progressed past it.
                            Goto(doneLabel);
                        }
                        else
                        {
                            using (EmitBlock(writer, node.Type == RegexNode.Beginning ? "if (runtextpos != runtextbeg)" : "if (runtextpos != runtextstart)"))
                            {
                                writer.WriteLine($"goto {doneLabel};");
                            }
                        }
                        break;

                    case RegexNode.Bol:
                        if (textSpanPos > 0)
                        {
                            using (EmitBlock(writer, $"if ({textSpanLocal}[{textSpanPos - 1}] != '\\n')"))
                            {
                                writer.WriteLine($"goto {doneLabel};");
                            }
                        }
                        else
                        {
                            // We can't use our textSpan in this case, because we'd need to access textSpan[-1], so we access the runtext field directly:
                            using (EmitBlock(writer, $"if (runtextpos > runtextbeg && runtext[runtextpos - 1] != '\\n')"))
                            {
                                writer.WriteLine($"goto {doneLabel};");
                            }
                        }
                        break;

                    case RegexNode.End:
                        using (EmitBlock(writer, $"if ({textSpanLocal}.Length > {textSpanPos})"))
                        {
                            writer.WriteLine($"goto {doneLabel};");
                        }
                        break;

                    case RegexNode.EndZ:
                        writer.WriteLine($"if ({textSpanPos} < {textSpanLocal}.Length - 1 || ({textSpanPos} < {textSpanLocal}.Length && {textSpanLocal}[{textSpanPos}] != '\\n'))");
                        using (EmitBlock(writer, null))
                        {
                            writer.WriteLine($"goto {doneLabel};");
                        }
                        break;

                    case RegexNode.Eol:
                        using (EmitBlock(writer, $"if ({textSpanPos} < {textSpanLocal}.Length && {textSpanLocal}[{textSpanPos}] != '\\n')"))
                        {
                            writer.WriteLine($"goto {doneLabel};");
                        }
                        break;
                }
            }

            // Emits the code to handle a multiple-character match.
            void EmitMultiChar(RegexNode node, bool emitLengthCheck = true)
            {
                bool caseInsensitive = IsCaseInsensitive(node);

                string str = node.Str!;
                Debug.Assert(str.Length != 0);

                const int MaxUnrollLength = 64;
                if (str.Length <= MaxUnrollLength)
                {
                    // Unroll shorter strings.

                    // For strings more than two characters and when performing case-sensitive searches, we try to do fewer comparisons
                    // by comparing 2 or 4 characters at a time.  Because we might be compiling on one endianness and running on another,
                    // both little and big endian values are emitted and which is used is selected at run-time.
                    ReadOnlySpan<byte> byteStr = MemoryMarshal.AsBytes(str.AsSpan());
                    bool useMultiCharReads = !caseInsensitive && byteStr.Length >= sizeof(uint);
                    if (useMultiCharReads)
                    {
                        writer.WriteLine($"byteSpan = global::System.Runtime.InteropServices.MemoryMarshal.AsBytes({textSpanLocal});");
                    }

                    writer.Write("if (");

                    bool emittedFirstCheck = false;
                    if (emitLengthCheck)
                    {
                        writer.Write($"(uint){textSpanLocal}.Length < {textSpanPos + str.Length}");
                        emittedFirstCheck = true;
                    }

                    void EmitOr()
                    {
                        if (emittedFirstCheck)
                        {
                            writer.WriteLine(" ||");
                            writer.Write("    ");
                        }
                        emittedFirstCheck = true;
                    }

                    if (useMultiCharReads)
                    {
                        while (byteStr.Length >= sizeof(ulong))
                        {
                            EmitOr();
                            string byteSpan = textSpanPos > 0 ? $"byteSpan.Slice({textSpanPos * sizeof(char)})" : "byteSpan";
                            writer.Write($"global::System.Buffers.Binary.BinaryPrimitives.ReadUInt64LittleEndian({byteSpan}) != 0x{BinaryPrimitives.ReadUInt64LittleEndian(byteStr):X}ul");
                            textSpanPos += sizeof(ulong) / sizeof(char);
                            byteStr = byteStr.Slice(sizeof(ulong));
                        }

                        while (byteStr.Length >= sizeof(uint))
                        {
                            EmitOr();
                            string byteSpan = textSpanPos > 0 ? $"byteSpan.Slice({textSpanPos * sizeof(char)})" : "byteSpan";
                            writer.Write($"global::System.Buffers.Binary.BinaryPrimitives.ReadUInt32LittleEndian({byteSpan}) != 0x{BinaryPrimitives.ReadUInt32LittleEndian(byteStr):X}u");
                            textSpanPos += sizeof(uint) / sizeof(char);
                            byteStr = byteStr.Slice(sizeof(uint));
                        }
                    }

                    // Emit remaining comparisons character by character.
                    for (int i = (str.Length * sizeof(char) - byteStr.Length) / sizeof(char); i < str.Length; i++)
                    {
                        EmitOr();
                        writer.Write($"{ToLowerIfNeeded(hasTextInfo, options, $"{textSpanLocal}[{textSpanPos}]", caseInsensitive)} != {Literal(str[i])}");
                        textSpanPos++;
                    }

                    writer.WriteLine(")");
                    using (EmitBlock(writer, null))
                    {
                        writer.WriteLine($"goto {doneLabel};");
                    }
                }
                else
                {
                    // Longer strings are compared character by character.  If this is a case-sensitive comparison, we can simply
                    // delegate to StartsWith.  If this is case-insensitive, we open-code the comparison loop, as we need to lowercase
                    // each character involved, and none of the StringComparison options provide the right semantics of comparing
                    // character-by-character while respecting the culture.
                    if (!caseInsensitive)
                    {
                        string sourceSpan = textSpanPos > 0 ? $"{textSpanLocal}.Slice({textSpanPos})" : textSpanLocal;
                        using (EmitBlock(writer, $"if (!global::System.MemoryExtensions.StartsWith({sourceSpan}, {Literal(node.Str)}))"))
                        {
                            writer.WriteLine($"goto {doneLabel};");
                        }
                        textSpanPos += node.Str.Length;
                    }
                    else
                    {
                        EmitSpanLengthCheck(str.Length);
                        string i = NextLocalName("i");
                        using (EmitBlock(writer, $"for (int {i} = 0; {i} < {Literal(node.Str)}.Length; {i}++)"))
                        {
                            string textSpanIndex = textSpanPos > 0 ? $"{i} + {textSpanPos}" : i;
                            using (EmitBlock(writer, $"if ({ToLower(hasTextInfo, options, $"{textSpanLocal}[{textSpanIndex}]")} != {Literal(str)}[{i}])"))
                            {
                                writer.WriteLine($"goto {doneLabel};");
                            }
                        }
                        textSpanPos += node.Str.Length;
                    }
                }
            }

            void EmitSingleCharLoop(RegexNode node, RegexNode? subsequent = null, bool emitLengthChecksIfRequired = true)
            {
                // If this is actually a repeater, emit that instead; no backtracking necessary.
                if (node.M == node.N)
                {
                    EmitSingleCharFixedRepeater(node, emitLengthChecksIfRequired);
                    return;
                }

                // Emit backtracking around an atomic single char loop.  We can then implement the backtracking
                // as an afterthought, since we know exactly how many characters are accepted by each iteration
                // of the wrapped loop (1).

                Debug.Assert(node.M < node.N);
                string backtrackingLabel = DefineLabel("Backtrack");
                string endLoop = DefineLabel("EndLoop");
                string startingPos = NextLocalName("startingRunTextPos");
                string endingPos = NextLocalName("endingRunTextPos");

                // We're about to enter a loop, so ensure our text position is 0.
                TransferTextSpanPosToRunTextPos();

                // Grab the current position, then emit the loop as atomic, and then
                // grab the current position again.  Even though we emit the loop without
                // knowledge of backtracking, we can layer it on top by just walking back
                // through the individual characters (a benefit of the loop matching exactly
                // one character per iteration, no possible captures within the loop, etc.)
                writer.WriteLine($"int {startingPos} = runtextpos;");
                EmitSingleCharAtomicLoop(node);
                TransferTextSpanPosToRunTextPos();
                writer.WriteLine($"int {endingPos} = runtextpos;");
                string? crawlPos = null;
                if (expressionHasCaptures)
                {
                    crawlPos = NextLocalName("crawlPos");
                    writer.WriteLine($"int {crawlPos} = base.Crawlpos();");
                }
                if (node.M > 0)
                {
                    writer.WriteLine($"{startingPos} += {node.M};");
                }
                writer.WriteLine($"goto {endLoop};");
                writer.WriteLine();

                // Backtracking section. Subsequent failures will jump to here, at which
                // point we decrement the matched count as long as it's above the minimum
                // required, and try again by flowing to everything that comes after this.
                MarkLabel(backtrackingLabel);
                string originalDoneLabel = doneLabel;
                using (EmitBlock(writer, $"if ({startingPos} >= {endingPos})"))
                {
                    writer.WriteLine($"goto {originalDoneLabel};");
                }
                doneLabel = backtrackingLabel; // leave set to the backtracking label for all subsequent nodes

                if (expressionHasCaptures)
                {
                    // Uncapture any captures if the expression has any.  It's possible the captures it has
                    // are before this node, in which case this is wasted effort, but still functionally correct.
                    EmitUncaptureUntil(crawlPos);
                }

                if (subsequent?.FindStartingCharacter() is char subsequentCharacter)
                {
                    writer.WriteLine($"{endingPos} = runtext.LastIndexOf({Literal(subsequentCharacter)}, {endingPos} - 1, {endingPos} - {startingPos});");
                    using (EmitBlock(writer, $"if ({endingPos} < 0)"))
                    {
                        writer.WriteLine($"goto {originalDoneLabel};");
                    }
                    writer.WriteLine($"runtextpos = {endingPos};");
                }
                else
                {
                    writer.WriteLine($"runtextpos = --{endingPos};");
                }

                LoadTextSpanLocal(writer);
                writer.WriteLine();

                MarkLabel(endLoop);

                // We explicitly do not reset doneLabel back to originalDoneLabel.
                // It's left pointing to the backtracking label for everything subsequent in the expression.
            }

            void EmitLazy(RegexNode node, bool emitLengthChecksIfRequired = true)
            {
                bool isSingleChar = node.IsOneFamily || node.IsNotoneFamily || node.IsSetFamily;

                // Emit the min iterations as a repeater.  Any failures here don't necessitate backtracking,
                // as the lazy itself failed to match.
                if (node.M > 0)
                {
                    if (isSingleChar)
                    {
                        EmitSingleCharFixedRepeater(node, emitLengthChecksIfRequired);
                    }
                    else
                    {
                        EmitNodeRepeater(node);
                    }
                }

                // If the whole thing was actually that repeater, we're done. Similarly, if this is actually an atomic
                // lazy loop, nothing will ever backtrack into this node, so we never need to iterate more than the minimum.
                if (node.M == node.N || node.Next is { Type: RegexNode.Atomic })
                {
                    return;
                }

                Debug.Assert(node.M < node.N);

                // We now need to match one character at a time, each time allowing the remainder of the expression
                // to try to match, and only matching another character if the subsequent expression fails to match.

                // We're about to enter a loop, so ensure our text position is 0.
                TransferTextSpanPosToRunTextPos();

                // If the loop isn't unbounded, track the number of iterations and the max number to allow.
                string? iterationCount = null;
                string? maxIterations = null;
                if (node.N != int.MaxValue)
                {
                    iterationCount = NextLocalName("i");
                    maxIterations = NextLocalName("maxIterations");
                    writer.WriteLine($"int {iterationCount} = 0;");
                    writer.WriteLine($"int {maxIterations} = {node.N - node.M};");
                }

                // Track the current crawl position.  Upon backtracking, we'll unwind any captures beyond this point.
                string? crawlPos = null;
                if (expressionHasCaptures)
                {
                    crawlPos = NextLocalName("crawlPos");
                    writer.WriteLine($"int {crawlPos} = base.Crawlpos();");
                }

                // Track the current runtextpos.  Each time we backtrack, we'll reset to the stored position, which
                // is also incremented each time we match another character in the loop.
                string nextPos = NextLocalName("nextPos");
                writer.WriteLine($"int {nextPos} = runtextpos;");

                // Skip the backtracking section for the initial subsequent matching.  We've already matched the
                // minimum number of iterations, which means we can successfully match with zero additional iterations.
                string endLoopLabel = DefineLabel("endLoop");
                writer.WriteLine($"goto {endLoopLabel};");
                writer.WriteLine();

                // Backtracking section. Subsequent failures will jump to here.
                string backtrackingLabel = DefineLabel("Backtrack");
                MarkLabel(backtrackingLabel);

                // Uncapture any captures if the expression has any.  It's possible the captures it has
                // are before this node, in which case this is wasted effort, but still functionally correct.
                if (expressionHasCaptures)
                {
                    EmitUncaptureUntil(crawlPos);
                }

                // If there's a max number of iterations, see if we've exceeded the maximum number of characters
                // to match.  If we haven't, increment the iteration count.
                if (maxIterations is not null)
                {
                    using (EmitBlock(writer, $"if ({iterationCount} >= {maxIterations})"))
                    {
                        writer.WriteLine($"goto {doneLabel};");
                    }
                    writer.WriteLine($"{iterationCount}++;");
                }

                // Now match the next character in the lazy loop.  We need to reset the runtextpos to the position
                // just after the last character in this loop was matched, and we need to store the resulting position
                // for the next time we backtrack.
                writer.WriteLine($"runtextpos = {nextPos};");
                LoadTextSpanLocal(writer);
                if (isSingleChar)
                {
                    EmitSingleChar(node);
                }
                else
                {
                    writer.WriteLine();
                    EmitNode(node.Child(0));
                }
                TransferTextSpanPosToRunTextPos();
                writer.WriteLine($"{nextPos} = runtextpos;");

                // Update the done label for everything that comes after this node.  This is done after we emit the single char
                // matching, as that failing indicates the loop itself has failed to match.
                string originalDoneLabel = doneLabel;
                doneLabel = backtrackingLabel; // leave set to the backtracking label for all subsequent nodes

                writer.WriteLine();
                MarkLabel(endLoopLabel, addEmptyStatement: true);

                // We explicitly do not reset doneLabel back to originalDoneLabel.
                // It's left pointing to the backtracking label for everything subsequent in the expression.
            }

            // Emits the code to handle a loop (repeater) with a fixed number of iterations.
            // RegexNode.M is used for the number of iterations; RegexNode.N is ignored.
            void EmitSingleCharFixedRepeater(RegexNode node, bool emitLengthCheck = true)
            {
                int iterations = node.M;
                if (iterations == 0)
                {
                    // No iterations, nothing to do.
                    return;
                }

                // if ((uint)(textSpanPos + iterations - 1) >= (uint)textSpan.Length) goto doneLabel;
                if (emitLengthCheck)
                {
                    EmitSpanLengthCheck(iterations);
                }

                if (iterations <= MaxUnrollSize)
                {
                    // if (textSpan[textSpanPos] != c1 ||
                    //     textSpan[textSpanPos + 1] != c2 ||
                    //     ...)
                    //       goto doneLabel;
                    for (int i = 0; i < iterations; i++)
                    {
                        EmitSingleChar(node, emitLengthCheck: false);
                    }
                }
                else
                {
                    string spanLocal = "slice"; // As this repeater doesn't wrap arbitrary node emits, this shouldn't conflict with anything
                    writer.WriteLine($"global::System.ReadOnlySpan<char> {spanLocal} = {textSpanLocal}.Slice({textSpanPos}, {iterations});");
                    string i = NextLocalName("i");
                    using (EmitBlock(writer, $"for (int {i} = 0; {i} < {spanLocal}.Length; {i}++)"))
                    {
                        EmitTimeoutCheck(writer, hasTimeout);

                        string tmpTextSpanLocal = textSpanLocal; // we want EmitSingleChar to refer to this temporary
                        int tmpTextSpanPos = textSpanPos;
                        textSpanLocal = spanLocal;
                        textSpanPos = 0;
                        EmitSingleChar(node, emitLengthCheck: false, offset: i);
                        textSpanLocal = tmpTextSpanLocal;
                        textSpanPos = tmpTextSpanPos;
                    }
                    textSpanPos += iterations;
                }
            }

            // Emits the code to handle a loop (repeater) with a fixed number of iterations.
            // This is used both to handle the case of A{5, 5} where the min and max are equal,
            // and also to handle part of the case of A{3, 5}, where this method is called to
            // handle the A{3, 3} portion, and then remaining A{0, 2} is handled separately.
            void EmitNodeRepeater(RegexNode node)
            {
                int iterations = node.M;
                Debug.Assert(iterations > 0);
                Debug.Assert(node.ChildCount() == 1);

                if (iterations == 1)
                {
                    EmitNode(node.Child(0));
                    return;
                }

                // Ensure textSpanPos is 0 prior to emitting the child.
                TransferTextSpanPosToRunTextPos();

                string i = NextLocalName("i");
                using (EmitBlock(writer, $"for (int {i} = 0; {i} < {iterations}; {i}++)"))
                {
                    EmitTimeoutCheck(writer, hasTimeout);
                    EmitNode(node.Child(0));
                    TransferTextSpanPosToRunTextPos();
                    Debug.Assert(textSpanPos == 0);
                }
            }

            // Emits the code to handle a non-backtracking, variable-length loop around a single character comparison.
            void EmitSingleCharAtomicLoop(RegexNode node, bool emitLengthChecksIfRequired = true)
            {
                // If this is actually a repeater, emit that instead.
                if (node.M == node.N)
                {
                    EmitSingleCharFixedRepeater(node, emitLengthChecksIfRequired);
                    return;
                }

                // If this is actually an optional single char, emit that instead.
                if (node.M == 0 && node.N == 1)
                {
                    EmitAtomicSingleCharZeroOrOne(node);
                    return;
                }

                Debug.Assert(node.N > node.M);
                int minIterations = node.M;
                int maxIterations = node.N;

                Span<char> setChars = stackalloc char[5]; // 5 is max optimized by IndexOfAny today
                int numSetChars = 0;

                string iterationLocal = NextLocalName("i");
                if (node.IsNotoneFamily &&
                    maxIterations == int.MaxValue &&
                    (!IsCaseInsensitive(node)))
                {
                    // For Notone, we're looking for a specific character, as everything until we find
                    // it is consumed by the loop.  If we're unbounded, such as with ".*" and if we're case-sensitive,
                    // we can use the vectorized IndexOf to do the search, rather than open-coding it.  The unbounded
                    // restriction is purely for simplicity; it could be removed in the future with additional code to
                    // handle the unbounded case.

                    writer.Write($"int {iterationLocal} = global::System.MemoryExtensions.IndexOf({textSpanLocal}");
                    if (textSpanPos > 0)
                    {
                        writer.Write($".Slice({textSpanPos})");
                    }
                    writer.WriteLine($", {Literal(node.Ch)});");
                    
                    using (EmitBlock(writer, $"if ({iterationLocal} == -1)"))
                    {
                        writer.WriteLine(textSpanPos > 0 ?
                            $"{iterationLocal} = {textSpanLocal}.Length - {textSpanPos};" :
                            $"{iterationLocal} = {textSpanLocal}.Length;");
                    }
                }
                else if (node.IsSetFamily &&
                    maxIterations == int.MaxValue &&
                    !IsCaseInsensitive(node) &&
                    (numSetChars = RegexCharClass.GetSetChars(node.Str!, setChars)) != 0 &&
                    RegexCharClass.IsNegated(node.Str!))
                {
                    // If the set is negated and contains only a few characters (if it contained 1 and was negated, it should
                    // have been reduced to a Notone), we can use an IndexOfAny to find any of the target characters.
                    // As with the notoneloopatomic above, the unbounded constraint is purely for simplicity.
                    Debug.Assert(numSetChars > 1);

                    writer.Write($"int {iterationLocal} = global::System.MemoryExtensions.IndexOfAny({textSpanLocal}");
                    if (textSpanPos != 0)
                    {
                        writer.Write($".Slice({textSpanPos})");
                    }
                    writer.WriteLine(numSetChars switch
                    {
                        2 => $", {Literal(setChars[0])}, {Literal(setChars[1])});",
                        3 => $", {Literal(setChars[0])}, {Literal(setChars[1])}, {Literal(setChars[2])});",
                        _ => $", {Literal(setChars.Slice(0, numSetChars).ToString())});",
                    });
                    using (EmitBlock(writer, $"if ({iterationLocal} == -1)"))
                    {
                        writer.WriteLine(textSpanPos > 0 ?
                            $"{iterationLocal} = {textSpanLocal}.Length - {textSpanPos};" :
                            $"{iterationLocal} = {textSpanLocal}.Length;");
                    }
                }
                else if (node.IsSetFamily && maxIterations == int.MaxValue && node.Str == RegexCharClass.AnyClass)
                {
                    // .* was used with RegexOptions.Singleline, which means it'll consume everything.  Just jump to the end.
                    // The unbounded constraint is the same as in the Notone case above, done purely for simplicity.

                    // int i = runtextend - runtextpos;
                    TransferTextSpanPosToRunTextPos();
                    writer.WriteLine($"int {iterationLocal} = runtextend - runtextpos;");
                }
                else
                {
                    // For everything else, do a normal loop.

                    string expr = $"{textSpanLocal}[{iterationLocal}]";
                    if (node.IsSetFamily)
                    {
                        expr = MatchCharacterClass(hasTextInfo, options, expr, node.Str!, IsCaseInsensitive(node));
                    }
                    else
                    {
                        expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive(node));
                        expr = $"{expr} {(node.IsOneFamily ? "==" : "!=")} {Literal(node.Ch)}";
                    }

                    if (minIterations != 0 || maxIterations != int.MaxValue)
                    {
                        // For any loops other than * loops, transfer text pos to runtextpos in
                        // order to zero it out to be able to use the single iteration variable
                        // for both iteration count and indexer.
                        TransferTextSpanPosToRunTextPos();
                    }

                    writer.WriteLine($"int {iterationLocal} = {textSpanPos};");
                    textSpanPos = 0;

                    string maxClause = maxIterations != int.MaxValue ? $"{iterationLocal} < {maxIterations} && " : "";
                    using (EmitBlock(writer, $"while ({maxClause}(uint){iterationLocal} < (uint){textSpanLocal}.Length && {expr})"))
                    {
                        EmitTimeoutCheck(writer, hasTimeout);
                        writer.WriteLine($"{iterationLocal}++;");
                    }
                }

                // Check to ensure we've found at least min iterations.
                if (minIterations > 0)
                {
                    using (EmitBlock(writer, $"if ({iterationLocal} < {minIterations})"))
                    {
                        writer.WriteLine($"goto {doneLabel};");
                    }
                }

                // Now that we've completed our optional iterations, advance the text span
                // and runtextpos by the number of iterations completed.

                writer.WriteLine($"{textSpanLocal} = {textSpanLocal}.Slice({iterationLocal});");
                writer.WriteLine($"runtextpos += {iterationLocal};");
            }

            // Emits the code to handle a non-backtracking optional zero-or-one loop.
            void EmitAtomicSingleCharZeroOrOne(RegexNode node)
            {
                Debug.Assert(node.M == 0 && node.N == 1);

                string expr = $"{textSpanLocal}[{textSpanPos}]";
                if (node.IsSetFamily)
                {
                    expr = MatchCharacterClass(hasTextInfo, options, expr, node.Str!, IsCaseInsensitive(node));
                }
                else
                {
                    expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive(node));
                    expr = $"{expr} {(node.IsOneFamily ? "==" : "!=")} {Literal(node.Ch)}";
                }

                using (EmitBlock(writer, $"if ((uint){textSpanPos} < (uint){textSpanLocal}.Length && {expr})"))
                {
                    writer.WriteLine($"{textSpanLocal} = {textSpanLocal}.Slice(1);");
                    writer.WriteLine($"runtextpos++;");
                }
            }

            // Emits the code to handle a non-backtracking, variable-length loop around another node.
            void EmitAtomicNodeLoop(RegexNode node)
            {
                Debug.Assert(node.Type == RegexNode.Loop, $"Unexpected type: {node.Type}");
                Debug.Assert(node.M < int.MaxValue, $"Unexpected M={node.M}");
                Debug.Assert(node.N >= node.M, $"Unexpected M={node.M}, N={node.N}");
                int minIterations = node.M;
                int maxIterations = node.N;

                // If this is actually a repeater, emit that instead.
                if (minIterations == maxIterations)
                {
                    EmitNodeRepeater(node);
                    return;
                }

                string originalDoneLabel = doneLabel;
                string atomicNodeLabel = DefineLabel("NoMatch");
                doneLabel = atomicNodeLabel;

                // We might loop any number of times.  In order to ensure this loop
                // and subsequent code sees textSpanPos the same regardless, we always need it to contain
                // the same value, and the easiest such value is 0.  So, we transfer
                // textSpanPos to runtextpos, and ensure that any path out of here has
                // textSpanPos as 0.
                TransferTextSpanPosToRunTextPos();

                // int i = 0;
                string iterationLocal = NextLocalName("iter");
                writer.WriteLine($"int {iterationLocal} = 0;");
                using (EmitBlock(writer, maxIterations == int.MaxValue ? "while (true)" : $"while ({iterationLocal} < {maxIterations})"))
                {
                    EmitTimeoutCheck(writer, hasTimeout);
                    string successfulIterationLabel = DefineLabel("Match");

                    // Iteration body

                    string prevDone = doneLabel;
                    string iterationLabel = DefineLabel("NoMatch");
                    doneLabel = iterationLabel;

                    // Save off runtextpos.
                    string startingRunTextPosLocal = NextLocalName("startingRunTextPos");
                    writer.WriteLine($"int {startingRunTextPosLocal} = runtextpos;");

                    // Emit the child.
                    Debug.Assert(textSpanPos == 0);
                    EmitNode(node.Child(0));
                    TransferTextSpanPosToRunTextPos(); // ensure textSpanPos remains 0
                    Goto(successfulIterationLabel); // iteration succeeded

                    // If the generated code gets here, the iteration failed.
                    // Reset state, branch to done.
                    MarkLabel(iterationLabel);
                    Debug.Assert(doneLabel == iterationLabel);
                    doneLabel = prevDone; // reset done label
                    writer.WriteLine($"runtextpos = {startingRunTextPosLocal};");
                    Goto(doneLabel);

                    // Successful iteration.
                    MarkLabel(successfulIterationLabel);
                    writer.WriteLine($"{iterationLocal}++;");
                }

                // Done:
                MarkLabel(atomicNodeLabel);
                Debug.Assert(doneLabel == atomicNodeLabel);
                doneLabel = originalDoneLabel;

                // Check to ensure we've found at least min iterations.
                if (minIterations > 0)
                {
                    using (EmitBlock(writer, $"if ({iterationLocal} < {minIterations})"))
                    {
                        writer.WriteLine($"goto {originalDoneLabel};");
                    }
                }
                else
                {
                    // Labels require a statement after them.
                    writer.WriteLine(";");
                }
            }
        }

        /// <summary>Emits the body of a complete Go implementation that fully supports backtracking.</summary>
        private static void EmitCompleteGo(IndentedTextWriter writer, RegexMethod rm, string id)
        {
            const int Stackpop = 0;       // pop one
            const int Stackpop2 = 1;      // pop two
            const int Capback = 3;        // uncapture
            const int Capback2 = 4;       // uncapture 2
            const int Branchmarkback2 = 5;      // back2 part of branchmark
            const int Lazybranchmarkback2 = 6;  // back2 part of lazybranchmark
            const int Branchcountback2 = 7;     // back2 part of branchcount
            const int Lazybranchcountback2 = 8; // back2 part of lazybranchcount
            const int Forejumpback = 9;         // back part of forejump
            const int Uniquecount = 10;
            const string Backtrack = "Backtrack"; // label for backtracking

            int[] codes = rm.Code.Codes;
            RegexOptions options = rm.Options;

            int labelCounter = 0;
            string DefineLabel(string prefix = "L") => $"{prefix}{labelCounter++}";
            void MarkLabel(string label) => writer.WriteLine($"{label}:");

            var labels = new string?[codes.Length]; // a label for every operation in _codes
            BacktrackNote[]? notes = null; // a list of the backtracking states to be generated
            int noteCount = 0; // true count of _notes (allocation grows exponentially)
            
            int currentOpcode = 0; // the current opcode being processed
            int currentCodePos = 0; // the current code being translated
            int currentBacktrackNote = 0; // the current backtrack-note being translated
            
            // special code fragments
            var uniqueNote = new int[Uniquecount]; // notes indices for code that should be emitted <= once
            var forwardJumpsThroughSwitch = new int[codes.Length]; // indices for forward-jumps-through-switch (for allocations)

            // Generates the forward logic corresponding directly to the regex codes.
            // In the absence of backtracking, this is all we would need.
            writer.WriteLine("string runtext = base.runtext!;");
            writer.WriteLine("int runtextbeg = base.runtextbeg;");
            writer.WriteLine("int runtextend = base.runtextend;");
            writer.WriteLine("int runtextpos = base.runtextpos;");
            writer.WriteLine("int[] runtrack = base.runtrack!;");
            writer.WriteLine("int runtrackpos = base.runtrackpos;");
            writer.WriteLine("int[] runstack = base.runstack!;");
            writer.WriteLine("int runstackpos = base.runstackpos;");
            writer.WriteLine("int tmp1, tmp2, ch;");
            bool hasTimeout = EmitLoopTimeoutCounterIfNeeded(writer, rm);
            bool hasTextInfo = EmitInitializeCultureForGoIfNecessary(writer, rm);
            writer.WriteLine();

            uniqueNote.AsSpan().Fill(-1);
            for (int codepos = 0; codepos < codes.Length; codepos += RegexCode.OpcodeSize(codes[codepos]))
            {
                forwardJumpsThroughSwitch[codepos] = -1;
                labels[codepos] = DefineLabel();
            }

            currentBacktrackNote = -1;
            for (int codepos = 0; codepos < codes.Length; codepos += RegexCode.OpcodeSize(codes[codepos]))
            {
                currentCodePos = codepos;
                currentOpcode = codes[codepos];
                EmitOneCode(labels[codepos]);
                writer.WriteLine();
            }

            // Generate the backtracking switch jump table that allows us to simulate a stack of addresses,
            // and contains the calls that expand the tracking and the grouping stack when they get too full.
            MarkLabel(Backtrack);

            // (Equivalent of EnsureStorage, but written to avoid unnecessary local spilling.)
            writer.WriteLine("int limit = base.runtrackcount * 4;");
            using (EmitBlock(writer, "if (runstackpos < limit)"))
            {
                writer.WriteLine("base.runstackpos = runstackpos;");
                writer.WriteLine("base.DoubleStack(); // might change runstackpos and runstack");
                writer.WriteLine("runstackpos = base.runstackpos;");
                writer.WriteLine("runstack = base.runstack!;");
            }
            using (EmitBlock(writer, "if (runtrackpos < limit)"))
            {
                writer.WriteLine("base.runtrackpos = runtrackpos;");
                writer.WriteLine("base.DoubleTrack(); // might change runtrackpos and runtrack");
                writer.WriteLine("runtrackpos = base.runtrackpos;");
                writer.WriteLine("runtrack = base.runtrack!;");
            }
            writer.WriteLine();
            using (EmitBlock(writer, "switch (runtrack[runtrackpos++])"))
            {
                for (int i = 0; i < noteCount; i++)
                {
                    using (EmitBlock(writer, $"case {i}:"))
                    {
                        Debug.Assert(notes is not null);
                        BacktrackNote n = notes[i];
                        if (n.flags != 0)
                        {
                            currentCodePos = n.codepos;
                            currentBacktrackNote = i;
                            currentOpcode = codes[n.codepos] | n.flags;
                            EmitOneCode(null); // should always end in a goto
                        }
                        else
                        {
                            writer.WriteLine($"goto {n.label};");
                        }
                    }

                    writer.WriteLine();
                }

                using (EmitBlock(writer, "default:"))
                {
                    writer.WriteLine("global::System.Diagnostics.Debug.Fail($\"Unexpected backtracking state {runtrack[runtrackpos - 1]}\");");
                    writer.WriteLine("break;");
                }
            }

            return;

            /// <summary>
            /// The main translation function. It translates the logic for a single opcode at
            /// the current position. The structure of this function exactly mirrors
            /// the structure of the inner loop of RegexInterpreter.Go().
            /// </summary>
            /// <remarks>
            /// Note that since we're generating code, we can collapse many cases that are
            /// dealt with one-at-a-time in RegexIntepreter. We can also unroll loops that
            /// iterate over constant strings or sets.
            /// </remarks>
            void EmitOneCode(string? label)
            {
                writer.WriteLine($"// {SymbolDisplay.FormatLiteral(RegexCode.OpcodeDescription(currentCodePos, rm.Code.Codes, rm.Code.Strings), quote: false)}");

                if (label is not null)
                {
                    MarkLabel(label);
                }

                // Before executing any Regex code in the unrolled loop,
                // we try checking for the match timeout:
                EmitTimeoutCheck(writer, hasTimeout);

                // Now generate the code for the Regex code saved in _regexopcode.
                switch (currentOpcode)
                {
                    case RegexCode.Stop:
                        writer.WriteLine("base.runtextpos = runtextpos;");
                        writer.WriteLine("return;");
                        break;

                    case RegexCode.Nothing:
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.UpdateBumpalong:
                        // UpdateBumpalong should only exist in the code stream at such a point where the root
                        // of the backtracking stack contains the runtextpos from the start of this Go call. Replace
                        // that tracking value with the current runtextpos value.
                        writer.WriteLine("runtrack[^1] = runtextpos;");
                        break;

                    case RegexCode.Goto:
                        Goto(Operand(0));
                        break;

                    case RegexCode.Testref:
                        using (EmitBlock(writer, $"if (!base.IsMatched({Operand(0)}))"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Lazybranch:
                        PushTrack("runtextpos");
                        Track();
                        break;

                    case RegexCode.Lazybranch | RegexCode.Back:
                        writer.WriteLine($"runtextpos = {PopTrack()};");
                        Goto(Operand(0));
                        break;

                    case RegexCode.Nullmark:
                        PushStack(-1);
                        TrackUnique(Stackpop);
                        break;

                    case RegexCode.Setmark:
                        PushStack("runtextpos");
                        TrackUnique(Stackpop);
                        break;

                    case RegexCode.Nullmark | RegexCode.Back:
                    case RegexCode.Setmark | RegexCode.Back:
                        PopDiscardStack();
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Getmark:
                        writer.WriteLine($"runtextpos = {PopStack()};");
                        PushTrack("runtextpos");
                        Track();
                        break;

                    case RegexCode.Getmark | RegexCode.Back:
                        PushStack(PopTrack());
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Capturemark:
                        {
                            if (Operand(1) != -1)
                            {
                                using (EmitBlock(writer, $"if (!base.IsMatched({Operand(1)}))"))
                                {
                                    writer.WriteLine($"goto {Backtrack};");
                                }
                            }

                            const string Stacked = "tmp1";
                            writer.WriteLine($"{Stacked} = {PopStack()};");
                            writer.WriteLine(Operand(1) != -1 ?
                                $"base.TransferCapture({Operand(0)}, {Operand(1)}, {Stacked}, runtextpos);" :
                                $"base.Capture({Operand(0)}, {Stacked}, runtextpos);");
                            PushTrack(Stacked);
                            TrackUnique(Operand(0) != -1 && Operand(1) != -1 ? Capback2 : Capback);
                        }
                        break;

                    case RegexCode.Capturemark | RegexCode.Back:
                        PushStack(PopTrack());
                        writer.WriteLine("base.Uncapture();");
                        if (Operand(0) != -1 && Operand(1) != -1)
                        {
                            writer.WriteLine("base.Uncapture();");
                        }
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Branchmark:
                        {
                            const string Mark = "tmp1";
                            writer.WriteLine($"{Mark} = {PopStack()}; // mark");
                            PushTrack(Mark);
                            using (EmitBlock(writer, $"if (runtextpos != {Mark})"))
                            {
                                PushTrack("runtextpos");
                                PushStack("runtextpos");
                                Track();
                                Goto(Operand(0));
                            }
                            using (EmitBlock(writer, "else"))
                            {
                                TrackUnique2(Branchmarkback2);
                            }
                        }
                        break;

                    case RegexCode.Branchmark | RegexCode.Back:
                        writer.WriteLine($"runtextpos = {PopTrack()};");
                        PopDiscardStack();
                        TrackUnique2(Branchmarkback2); // track spot 0 is already in place
                        Advance();
                        break;

                    case RegexCode.Branchmark | RegexCode.Back2:
                        PushStack(PopTrack());
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Lazybranchmark:
                        {
                            const string Mark = "tmp1";
                            writer.WriteLine($"{Mark} = {PopStack()}; // mark");
                            PushTrack($"{Mark} != -1 ? {Mark} : runtextpos");
                            using (EmitBlock(writer, $"if (runtextpos != {Mark})"))
                            {
                                PushTrack("runtextpos");
                                Track();
                                Advance();
                            }
                            PushStack(Mark);
                            TrackUnique2(Lazybranchmarkback2);
                        }
                        break;

                    case RegexCode.Lazybranchmark | RegexCode.Back:
                        writer.WriteLine($"runtextpos = {PopTrack()};");
                        PushStack("runtextpos");
                        TrackUnique2(Lazybranchmarkback2);
                        Goto(Operand(0));
                        break;

                    case RegexCode.Lazybranchmark | RegexCode.Back2:
                        writer.WriteLine($"{ReadyReplaceStack(0)} = {PopTrack()};");
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Nullcount:
                        PushStack(-1);
                        PushStack(Operand(0));
                        TrackUnique(Stackpop2);
                        break;

                    case RegexCode.Setcount:
                        PushStack("runtextpos");
                        PushStack(Operand(0));
                        TrackUnique(Stackpop2);
                        break;

                    case RegexCode.Nullcount | RegexCode.Back:
                    case RegexCode.Setcount | RegexCode.Back:
                        PopDiscardStack(2);
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Branchcount:
                        {
                            const string Count = "tmp1";
                            const string Mark = "tmp2";
                            writer.WriteLine($"{Count} = {PopStack()}; // count");
                            writer.WriteLine($"{Mark} = {PopStack()}; // mark");
                            PushTrack(Mark);
                            using (EmitBlock(writer, $"if ({Count} < ({Mark} == runtextpos ? 0 : {Operand(1)}))"))
                            {
                                PushStack("runtextpos");
                                PushStack($"{Count} + 1");
                                Track();
                                Goto(Operand(0));
                            }
                            PushTrack(Count);
                            TrackUnique2(Branchcountback2);
                        }
                        break;

                    case RegexCode.Branchcount | RegexCode.Back:
                        {
                            const string Count = "tmp1";
                            writer.WriteLine($"{Count} = {PopStack()} - 1; // count");
                            using (EmitBlock(writer, $"if ({Count} >= 0)"))
                            {
                                writer.WriteLine($"runtextpos = {PopStack()};");
                                PushTrack(Count);
                                TrackUnique2(Branchcountback2);
                                Advance();
                            }
                            writer.WriteLine($"{ReadyReplaceStack(0)} = {PopTrack()};");
                            PushStack(Count);
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Branchcount | RegexCode.Back2:
                        {
                            const string Mark = "tmp1";
                            writer.WriteLine($"{Mark} = {PopTrack()}; // mark");
                            PushStack(PopTrack());
                            PushStack(Mark);
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Lazybranchcount:
                        {
                            const string Count = "tmp1";
                            writer.WriteLine($"{Count} = {PopStack()}; // count");
                            PushTrack(PopStack()); // mark
                            using (EmitBlock(writer, $"if ({Count} < 0)"))
                            {
                                PushStack("runtextpos");
                                PushStack($"{Count} + 1");
                                TrackUnique2(Lazybranchcountback2);
                                Goto(Operand(0));
                            }
                            PushTrack(Count);
                            PushTrack("runtextpos");
                            Track();
                        }
                        break;

                    case RegexCode.Lazybranchcount | RegexCode.Back:
                        {
                            const string C = "tmp1";
                            writer.WriteLine($"runtextpos = {PopTrack()};");
                            writer.WriteLine($"{C} = {PopTrack()}; // c");
                            using (EmitBlock(writer, $"if ({C} < {Operand(1)} && runtextpos != {TopTrack()})"))
                            {
                                PushStack("runtextpos");
                                PushStack($"{C} + 1");
                                TrackUnique2(Lazybranchcountback2);
                                Goto(Operand(0));
                            }
                            PushStack(PopTrack());
                            PushStack(C);
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Lazybranchcount | RegexCode.Back2:
                        writer.WriteLine($"{ReadyReplaceStack(1)} = {PopTrack()};");
                        writer.WriteLine($"{ReadyReplaceStack(0)} = {TopStack()} - 1;");
                        ReadyReplaceStack(0);
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Setjump:
                        PushStack("runtrack.Length - runtrackpos");
                        PushStack("base.Crawlpos()");
                        TrackUnique(Stackpop2);
                        break;

                    case RegexCode.Setjump | RegexCode.Back:
                        PopDiscardStack(2);
                        writer.WriteLine($"goto {Backtrack};");
                        break;

                    case RegexCode.Backjump:
                        {
                            const string Stacked = "tmp1";
                            writer.WriteLine($"{Stacked} = {PopStack()}; // stacked");
                            writer.WriteLine($"runtrackpos = runtrack.Length - {PopStack()};");
                            writer.WriteLine($"while (base.Crawlpos() != {Stacked}) base.Uncapture();");
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Forejump:
                        {
                            const string Stacked = "tmp1";
                            writer.WriteLine($"{Stacked} = {PopStack()}; // stacked");
                            writer.WriteLine($"runtrackpos = runtrack.Length - {PopStack()};");
                            PushTrack(Stacked);
                            TrackUnique(Forejumpback);
                        }
                        break;

                    case RegexCode.Forejump | RegexCode.Back:
                        {
                            const string TrackedCrawlpos = "tmp1";
                            writer.WriteLine($"{TrackedCrawlpos} = {PopTrack()}; // tracked crawlpos");
                            writer.WriteLine($"while (base.Crawlpos() != {TrackedCrawlpos}) base.Uncapture();");
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Bol:
                        using (EmitBlock(writer, $"if (runtextpos <= runtextbeg)"))
                        {
                            writer.WriteLine($"goto {labels[NextCodepos()]};");
                        }
                        using (EmitBlock(writer, $"if ({Leftchar()} != '\\n')"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Eol:
                        using (EmitBlock(writer, $"if (runtextpos >= runtextend)"))
                        {
                            writer.WriteLine($"goto {labels[NextCodepos()]};");
                        }
                        using (EmitBlock(writer, $"if ({Rightchar()} != '\\n')"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Boundary:
                    case RegexCode.NonBoundary:
                        using (EmitBlock(writer, $"if ({(Code() == RegexCode.Boundary ? "!" : "")}base.IsBoundary(runtextpos, runtextbeg, runtextend))"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.ECMABoundary:
                    case RegexCode.NonECMABoundary:
                        using (EmitBlock(writer, $"if ({(Code() == RegexCode.ECMABoundary ? "!" : "")}base.IsECMABoundary(runtextpos, runtextbeg, runtextend))"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Beginning:
                        using (EmitBlock(writer, $"if (runtextpos > runtextbeg)"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.Start:
                        using (EmitBlock(writer, $"if (runtextpos != runtextstart)"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.EndZ:
                        using (EmitBlock(writer, $"if (runtextpos < runtextend - 1)"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        using (EmitBlock(writer, $"if (runtextpos >= runtextend)"))
                        {
                            writer.WriteLine($"goto {labels[NextCodepos()]};");
                        }
                        using (EmitBlock(writer, $"if ({Rightchar()} != '\\n')"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.End:
                        using (EmitBlock(writer, $"if (runtextpos < runtextend)"))
                        {
                            writer.WriteLine($"goto {Backtrack};");
                        }
                        break;

                    case RegexCode.One:
                    case RegexCode.Notone:
                    case RegexCode.Set:
                    case RegexCode.One | RegexCode.Rtl:
                    case RegexCode.Notone | RegexCode.Rtl:
                    case RegexCode.Set | RegexCode.Rtl:
                    case RegexCode.One | RegexCode.Ci:
                    case RegexCode.Notone | RegexCode.Ci:
                    case RegexCode.Set | RegexCode.Ci:
                    case RegexCode.One | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Notone | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Set | RegexCode.Ci | RegexCode.Rtl:
                        {
                            string clause;
                            string expr;
                            if (!IsRightToLeft())
                            {
                                clause = $"runtextpos >= runtextend || ";
                                expr = Rightcharnext();
                            }
                            else
                            {
                                clause = $"runtextpos <= runtextbeg || ";
                                expr = Leftcharnext();
                            }

                            clause += Code() == RegexCode.Set ?
                                $"!{MatchCharacterClass(hasTextInfo, options, expr, rm.Code.Strings[Operand(0)], IsCaseInsensitive())}" :
                                $"{ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive())} {(Code() == RegexCode.One ? "!=" : "==")} {Operand(0)}";

                            using (EmitBlock(writer, $"if ({clause})"))
                            {
                                writer.WriteLine($"goto {Backtrack};");
                            }
                        }
                        break;

                    case RegexCode.Multi:
                    case RegexCode.Multi | RegexCode.Ci:
                        {
                            string str = rm.Code.Strings[Operand(0)];
                            Debug.Assert(str.Length != 0);
                            writer.WriteLine($"if (runtextend - runtextpos < {str.Length} ||");
                            for (int i = 0; i < str.Length; i++)
                            {
                                writer.Write($"    {ToLowerIfNeeded(hasTextInfo, options, $"runtext[runtextpos{(i == 0 ? "" : $" + {i}")}]", IsCaseInsensitive())} != {Literal(str[i])}");
                                writer.WriteLine(i < str.Length - 1 ? " ||" : ")");
                            }
                            using (EmitBlock(writer, null))
                            {
                                writer.WriteLine($"goto {Backtrack};");
                            }
                            EmitAdd(writer, "runtextpos", str.Length);
                            break;
                        }

                    case RegexCode.Multi | RegexCode.Rtl:
                    case RegexCode.Multi | RegexCode.Ci | RegexCode.Rtl:
                        {
                            string str = rm.Code.Strings[Operand(0)];
                            Debug.Assert(str.Length != 0);
                            writer.WriteLine($"if (runtextpos - runtextbeg < {str.Length} ||");
                            for (int i = str.Length; i > 0;)
                            {
                                i--;
                                writer.Write($"    {ToLowerIfNeeded(hasTextInfo, options, $"runtext[runtextpos - {str.Length - i}]", IsCaseInsensitive())} != {Literal(str[i])}");
                                writer.WriteLine(i == 0 ? ")" : " ||");
                            }
                            using (EmitBlock(writer, null))
                            {
                                writer.WriteLine($"goto {Backtrack};");
                            }
                            writer.WriteLine($"runtextpos -= {str.Length};");
                            break;
                        }

                    case RegexCode.Ref:
                    case RegexCode.Ref | RegexCode.Ci:
                    case RegexCode.Ref | RegexCode.Rtl:
                    case RegexCode.Ref | RegexCode.Ci | RegexCode.Rtl:
                        {
                            const string Length = "tmp1";
                            const string Index = "tmp2";

                            using (EmitBlock(writer, $"if (!base.IsMatched({Operand(0)}))"))
                            {
                                writer.WriteLine($"goto {((options & RegexOptions.ECMAScript) != 0 ? AdvanceLabel() : Backtrack)};");
                            }

                            writer.WriteLine($"{Length} = base.MatchLength({Operand(0)}); // length");

                            using (EmitBlock(writer, !IsRightToLeft() ? $"if (runtextend - runtextpos < {Length})" : $"if (runtextpos - runtextbeg < {Length})"))
                            {
                                writer.WriteLine($"goto {Backtrack};");
                            }

                            if (!IsRightToLeft())
                            {
                                writer.WriteLine($"{Index} = base.MatchIndex({Operand(0)}) + {Length}; // index");
                                writer.WriteLine($"runtextpos += {Length};");
                            }
                            else
                            {
                                writer.WriteLine($"{Index} = base.MatchIndex({Operand(0)}); // index");
                                writer.WriteLine($"runtextpos -= {Length};");
                            }

                            using (EmitBlock(writer, "while (true)"))
                            {
                                using (EmitBlock(writer, $"if ({Length} <= 0)"))
                                {
                                    writer.WriteLine($"goto {AdvanceLabel()};");
                                }

                                using (EmitBlock(writer, !IsRightToLeft() ?
                                    $"if ({ToLowerIfNeeded(hasTextInfo, options, $"runtext[{Index} - {Length}]", IsCaseInsensitive())} != {ToLowerIfNeeded(hasTextInfo, options, $"runtext[runtextpos - {Length}--]", IsCaseInsensitive())})" :
                                    $"if ({ToLowerIfNeeded(hasTextInfo, options, $"runtext[{Index} + --{Length}]", IsCaseInsensitive())} != {ToLowerIfNeeded(hasTextInfo, options, $"runtext[runtextpos + {Length}]", IsCaseInsensitive())})"))
                                {
                                    writer.WriteLine($"break;");
                                }
                            }

                            writer.WriteLine($"goto {Backtrack};");
                            break;
                        }

                    case RegexCode.Onerep:
                    case RegexCode.Notonerep:
                    case RegexCode.Setrep:
                    case RegexCode.Onerep | RegexCode.Ci:
                    case RegexCode.Notonerep | RegexCode.Ci:
                    case RegexCode.Setrep | RegexCode.Ci:
                        {
                            int c = Operand(1);
                            if (c != 0)
                            {
                                using (EmitBlock(writer, $"if (runtextend - runtextpos < {c})"))
                                {
                                    writer.WriteLine($"goto {Backtrack};");
                                }

                                using (EmitBlock(writer, $"for (int i = 0; i < {c}; i++)"))
                                {
                                    string expr = "runtext[runtextpos + i]";
                                    if (Code() == RegexCode.Setrep)
                                    {
                                        EmitTimeoutCheck(writer, hasTimeout);
                                        expr = $"!{MatchCharacterClass(hasTextInfo, options, expr, rm.Code.Strings[Operand(0)], IsCaseInsensitive())}";
                                    }
                                    else
                                    {
                                        expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive());
                                        expr = $"{expr} {(Code() == RegexCode.Onerep ? "!=" : "==")} {Literal((char)Operand(0))}";
                                    }

                                    using (EmitBlock(writer, $"if ({expr})"))
                                    {
                                        writer.WriteLine($"goto {Backtrack};");
                                    }
                                }
                                EmitAdd(writer, "runtextpos", c);
                            }
                        }
                        break;

                    case RegexCode.Onerep | RegexCode.Rtl:
                    case RegexCode.Notonerep | RegexCode.Rtl:
                    case RegexCode.Setrep | RegexCode.Rtl:
                    case RegexCode.Onerep | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Notonerep | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Setrep | RegexCode.Ci | RegexCode.Rtl:
                        {
                            int c = Operand(1);
                            if (c != 0)
                            {
                                const string Length = "tmp1";

                                using (EmitBlock(writer, $"if (runtextpos - runtextbeg < {c})"))
                                {
                                    writer.WriteLine($"goto {Backtrack};");
                                }
                                writer.WriteLine($"runtextpos -= {c};");
                                writer.WriteLine($"{Length} = {c}; // length");

                                string l1 = DefineLabel();
                                MarkLabel(l1);

                                string expr = $"runtext[runtextpos + --{Length}]";
                                if (Code() == RegexCode.Setrep)
                                {
                                    EmitTimeoutCheck(writer, hasTimeout);
                                    using (EmitBlock(writer, $"if (!{MatchCharacterClass(hasTextInfo, options, expr, rm.Code.Strings[Operand(0)], IsCaseInsensitive())})"))
                                    {
                                        writer.WriteLine($"goto {Backtrack};");
                                    }
                                }
                                else
                                {
                                    expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive());
                                    string op = Code() == RegexCode.Onerep ? "!=" : "==";
                                    using (EmitBlock(writer, $"if ({expr} {op} {Literal((char)Operand(0))})"))
                                    {
                                        writer.WriteLine($"goto {Backtrack};");
                                    }
                                }

                                using (EmitBlock(writer, $"if ({Length} > 0)"))
                                {
                                    writer.WriteLine($"goto {l1};");
                                }
                            }
                            break;
                        }

                    case RegexCode.Oneloop:
                    case RegexCode.Notoneloop:
                    case RegexCode.Setloop:
                    case RegexCode.Oneloop | RegexCode.Rtl:
                    case RegexCode.Notoneloop | RegexCode.Rtl:
                    case RegexCode.Setloop | RegexCode.Rtl:
                    case RegexCode.Oneloop | RegexCode.Ci:
                    case RegexCode.Notoneloop | RegexCode.Ci:
                    case RegexCode.Setloop | RegexCode.Ci:
                    case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Setloop | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Oneloopatomic:
                    case RegexCode.Notoneloopatomic:
                    case RegexCode.Setloopatomic:
                    case RegexCode.Oneloopatomic | RegexCode.Rtl:
                    case RegexCode.Notoneloopatomic | RegexCode.Rtl:
                    case RegexCode.Setloopatomic | RegexCode.Rtl:
                    case RegexCode.Oneloopatomic | RegexCode.Ci:
                    case RegexCode.Notoneloopatomic | RegexCode.Ci:
                    case RegexCode.Setloopatomic | RegexCode.Ci:
                    case RegexCode.Oneloopatomic | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Notoneloopatomic | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Setloopatomic | RegexCode.Ci | RegexCode.Rtl:
                        {
                            int c = Operand(1);
                            if (c != 0)
                            {
                                const string Len = "tmp1";
                                const string I = "tmp2";

                                if (c == int.MaxValue)
                                {
                                    writer.WriteLine(!IsRightToLeft() ?
                                        $"{Len} = runtextend - runtextpos; // length" :
                                        $"{Len} = runtextpos - runtextbeg; // length");
                                }
                                else
                                {
                                    writer.WriteLine(!IsRightToLeft() ?
                                        $"{Len} = global::System.Math.Min(runtextend - runtextpos, {c}); // length" :
                                        $"{Len} = global::System.Math.Min(runtextpos - runtextbeg, {c}); // length");
                                }

                                string? set = Code() == RegexCode.Setloop || Code() == RegexCode.Setloopatomic ? rm.Code.Strings[Operand(0)] : null;
                                Span<char> setChars = stackalloc char[5]; // max optimized by IndexOfAny today
                                int numSetChars;

                                // If this is a notoneloop{atomic} and we're left-to-right and case-sensitive,
                                // we can use the vectorized IndexOf to search for the target character.
                                if ((Code() == RegexCode.Notoneloop || Code() == RegexCode.Notoneloopatomic) &&
                                    !IsRightToLeft() &&
                                    !IsCaseInsensitive())
                                {
                                    writer.WriteLine($"{I} = global::System.MemoryExtensions.IndexOf(global::System.MemoryExtensions.AsSpan(runtext, runtextpos, {Len}), {Literal((char)Operand(0))}); // i");
                                    using (EmitBlock(writer, $"if ({I} == -1)"))
                                    {
                                        writer.WriteLine($"runtextpos += {Len};");
                                        writer.WriteLine($"{I} = 0;");
                                    }
                                    using (EmitBlock(writer, "else"))
                                    {
                                        writer.WriteLine($"runtextpos += {I};");
                                        writer.WriteLine($"{I} = {Len} - {I};");
                                    }
                                }
                                else if ((Code() == RegexCode.Setloop || Code() == RegexCode.Setloopatomic) &&
                                    !IsRightToLeft() &&
                                    !IsCaseInsensitive() &&
                                    (numSetChars = RegexCharClass.GetSetChars(set!, setChars)) != 0 &&
                                    RegexCharClass.IsNegated(set!))
                                {
                                    // Similarly, if this is a setloop{atomic} and we're left-to-right and case-sensitive,
                                    // and if the set contains only a few negated chars, we can use the vectorized IndexOfAny
                                    // to search for those chars.
                                    Debug.Assert(numSetChars > 1);
                                    writer.WriteLine(numSetChars switch
                                    {
                                        2 => $"{I} = global::System.MemoryExtensions.IndexOfAny(global::System.MemoryExtensions.AsSpan(runtext, runtextpos, {Len}), {Literal(setChars[0])}, {Literal(setChars[1])}); // i",
                                        3 => $"{I} = global::System.MemoryExtensions.IndexOfAny(global::System.MemoryExtensions.AsSpan(runtext, runtextpos, {Len}), {Literal(setChars[0])}, {Literal(setChars[1])}, {Literal(setChars[2])}); // i",
                                        _ => $"{I} = global::System.MemoryExtensions.IndexOfAny(global::System.MemoryExtensions.AsSpan(runtext, runtextpos, {Len}), {Literal(setChars.Slice(0, numSetChars).ToString())}); // i",
                                    });
                                    using (EmitBlock(writer, $"if ({I} == -1)"))
                                    {
                                        writer.WriteLine($"runtextpos += {Len};");
                                        writer.WriteLine($"{I} = 0;");
                                    }
                                    using (EmitBlock(writer, "else"))
                                    {
                                        writer.WriteLine($"runtextpos += {I};");
                                        writer.WriteLine($"{I} = {Len} - {I};");
                                    }
                                }
                                else if ((Code() == RegexCode.Setloop || Code() == RegexCode.Setloopatomic) &&
                                    !IsRightToLeft() &&
                                    set == RegexCharClass.AnyClass)
                                {
                                    // If someone uses .* along with RegexOptions.Singleline, that becomes [anycharacter]*, which means it'll
                                    // consume everything.  As such, we can simply update our position to be the last allowed, without
                                    // actually checking anything.
                                    writer.WriteLine($"runtextpos += {Len};");
                                    writer.WriteLine($"{I} = 0;");
                                }
                                else
                                {
                                    // Otherwise, we emit the open-coded loop.
                                    writer.WriteLine($"{I} = {Len} + 1;");
                                    using (EmitBlock(writer, $"while (--{I} > {0})"))
                                    {
                                        string expr = !IsRightToLeft() ?
                                            Rightcharnext() :
                                            Leftcharnext();

                                        if (Code() == RegexCode.Setloop || Code() == RegexCode.Setloopatomic)
                                        {
                                            EmitTimeoutCheck(writer, hasTimeout);
                                            expr = $"!{MatchCharacterClass(hasTextInfo, options, expr, rm.Code.Strings[Operand(0)], IsCaseInsensitive())}";
                                        }
                                        else
                                        {
                                            string op = Code() == RegexCode.Oneloop || Code() == RegexCode.Oneloopatomic ? "!=" : "==";
                                            expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive());
                                            expr = $"{expr} {op} {Literal((char)Operand(0))}";
                                        }

                                        using (EmitBlock(writer, $"if ({expr})"))
                                        {
                                            writer.WriteLine(!IsRightToLeft() ?
                                                "runtextpos--;" :
                                                "runtextpos++;");
                                            writer.WriteLine("break;");
                                        }
                                    }
                                }

                                if (Code() != RegexCode.Oneloopatomic && Code() != RegexCode.Notoneloopatomic && Code() != RegexCode.Setloopatomic)
                                {
                                    using (EmitBlock(writer, $"if ({I} >= {Len})"))
                                    {
                                        writer.WriteLine($"goto {AdvanceLabel()};");
                                    }
                                    PushTrack($"{Len} - {I} - 1");
                                    PushTrack(!IsRightToLeft() ?
                                        "runtextpos - 1" :
                                        "runtextpos + 1");
                                    Track();
                                }
                            }
                            break;
                        }

                    case RegexCode.Oneloop | RegexCode.Back:
                    case RegexCode.Notoneloop | RegexCode.Back:
                    case RegexCode.Setloop | RegexCode.Back:
                    case RegexCode.Oneloop | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Notoneloop | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Setloop | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Setloop | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Setloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                        {
                            const string Position = "tmp1";
                            writer.WriteLine($"runtextpos = {PopTrack()};");
                            writer.WriteLine($"{Position} = {PopTrack()}; // position");
                            using (EmitBlock(writer, $"if ({Position} > 0)"))
                            {
                                PushTrack($"{Position} - 1");
                                PushTrack(!IsRightToLeft() ?
                                    "runtextpos - 1" :
                                    "runtextpos + 1");
                                Trackagain();
                            }
                            Advance();
                        }
                        break;

                    case RegexCode.Onelazy:
                    case RegexCode.Notonelazy:
                    case RegexCode.Setlazy:
                    case RegexCode.Onelazy | RegexCode.Rtl:
                    case RegexCode.Notonelazy | RegexCode.Rtl:
                    case RegexCode.Setlazy | RegexCode.Rtl:
                    case RegexCode.Onelazy | RegexCode.Ci:
                    case RegexCode.Notonelazy | RegexCode.Ci:
                    case RegexCode.Setlazy | RegexCode.Ci:
                    case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Rtl:
                    case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Rtl:
                        {
                            int count = Operand(1);
                            if (count != 0)
                            {
                                const string C = "tmp1";
                                if (count == int.MaxValue)
                                {
                                    writer.WriteLine(!IsRightToLeft() ?
                                        $"{C} = runtextend - runtextpos; // count" :
                                        $"{C} = runtextpos - runtextbeg; // count");
                                }
                                else
                                {
                                    writer.WriteLine(!IsRightToLeft() ?
                                        $"{C} = global::System.Math.Min(runtextend - runtextpos, {count}); // count" :
                                        $"{C} = global::System.Math.Min(runtextpos - runtextbeg, {count}); // count");
                                }

                                using (EmitBlock(writer, $"if ({C} <= 0)"))
                                {
                                    writer.WriteLine($"goto {AdvanceLabel()};");
                                }

                                PushTrack($"{C} - 1");
                                PushTrack("runtextpos");
                                Track();
                            }
                            break;
                        }

                    case RegexCode.Onelazy | RegexCode.Back:
                    case RegexCode.Notonelazy | RegexCode.Back:
                    case RegexCode.Setlazy | RegexCode.Back:
                    case RegexCode.Onelazy | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Notonelazy | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Setlazy | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Back:
                    case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                    case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
                        {
                            const string I = "tmp1";

                            writer.WriteLine($"runtextpos = {PopTrack()};");
                            writer.WriteLine($"{I} = {PopTrack()}; // i");

                            string expr = !IsRightToLeft() ?
                                Rightcharnext() :
                                Leftcharnext();

                            if (Code() == RegexCode.Setlazy)
                            {
                                EmitTimeoutCheck(writer, hasTimeout);
                                expr = $"!{MatchCharacterClass(hasTextInfo, options, expr, rm.Code.Strings[Operand(0)], IsCaseInsensitive())}";
                            }
                            else
                            {
                                expr = ToLowerIfNeeded(hasTextInfo, options, expr, IsCaseInsensitive());
                                expr = $"{expr} {(Code() == RegexCode.Onelazy ? "!=" : "==")} {Literal((char)Operand(0))}";
                            }

                            using (EmitBlock(writer, $"if ({expr})"))
                            {
                                writer.WriteLine($"goto {Backtrack};");
                            }

                            using (EmitBlock(writer, $"if ({I} > 0)"))
                            {
                                PushTrack($"{I} - 1");
                                PushTrack("runtextpos");
                                Trackagain();
                            }

                            Advance();
                        }
                        break;

                    default:
                        Debug.Fail($"Unimplemented state: {currentOpcode:X8}");
                        break;
                }
            }



            /// <summary>
            /// Branch to the label corresponding to the regex code at i
            /// </summary>
            /// <remarks>
            /// A trick: since track and stack space is gobbled up unboundedly
            /// only as a result of branching backwards, this is where we check
            /// for sufficient space and trigger reallocations.
            ///
            /// If the "goto" is backwards, we generate code that checks
            /// available space against the amount of space that would be needed
            /// in the worst case by code that will only go forward; if there's
            /// not enough, we push the destination on the tracking stack, then
            /// we jump to the place where we invoke the allocator.
            ///
            /// Since forward gotos pose no threat, they just turn into a Br.
            /// </remarks>
            void Goto(int i)
            {
                // When going backwards, ensure enough space.
                if (i < currentCodePos)
                {
                    using (EmitBlock(writer, $"if (runtrackpos <= {rm.Code.TrackCount * 4} || runstackpos <= {rm.Code.TrackCount * 3})"))
                    {
                        writer.WriteLine($"{ReadyPushTrack()} = {AddGoto(i)};");
                        writer.WriteLine($"goto {Backtrack};");
                    }
                }

                writer.WriteLine($"goto {labels[i]};");
            }

            string ReadyPushTrack() => "runtrack[--runtrackpos]";

            void Track() => PushTrack(AddTrack());

            /// <summary>
            /// Pushes the current switch index on the tracking stack so the backtracking
            /// logic will be repeated again next time we backtrack here.
            /// </summary>
            void Trackagain() => PushTrack(currentBacktrackNote);

            void PushTrack<T>(T expr) where T : notnull => writer.WriteLine($"{ReadyPushTrack()} = {(expr is IFormattable ? ((IFormattable)expr).ToString(null, CultureInfo.InvariantCulture) : expr.ToString())};");

            /// <summary>Retrieves the top entry on the tracking stack without popping.</summary>
            string TopTrack() => "runtrack[runtrackpos]";

            int Operand(int i) => codes[currentCodePos + i + 1];

            /// <summary>True if the current operation is marked for the leftward direction.</summary>
            bool IsRightToLeft() => (currentOpcode & RegexCode.Rtl) != 0;

            /// <summary>True if the current operation is marked for case insensitive operation.</summary>
            bool IsCaseInsensitive() => (currentOpcode & RegexCode.Ci) != 0;

            /// <summary>Returns the raw regex opcode (masking out Back and Rtl).</summary>
            int Code() => currentOpcode & RegexCode.Mask;

            /// <summary>Saves the value of a local variable on the grouping stack.</summary>
            void PushStack<T>(T expr) where T : notnull => writer.WriteLine($"{ReadyPushStack()} = {(expr is IFormattable ? ((IFormattable)expr).ToString(null, CultureInfo.InvariantCulture) : expr.ToString())};");

            string ReadyPushStack() => "runstack[--runstackpos]";

            /// <summary>Retrieves the top entry on the stack without popping.</summary>
            string TopStack() => "runstack[runstackpos]";

            void TrackUnique(int i) => PushTrack(AddUniqueTrack(i));

            void TrackUnique2(int i) => PushTrack(AddUniqueTrack(i, RegexCode.Back2));

            int AddUniqueTrack(int i, int flags = RegexCode.Back)
            {
                if (uniqueNote[i] == -1)
                {
                    uniqueNote[i] = AddTrack(flags);
                }

                return uniqueNote[i];
            }

            /// <summary>
            /// Returns the position of the next operation in the regex code, taking
            /// into account the different numbers of arguments taken by operations
            /// </summary>
            int NextCodepos() => currentCodePos + RegexCode.OpcodeSize(codes[currentCodePos]);

            /// <summary>The label for the next (forward) operation.</summary>
            string AdvanceLabel() => labels[NextCodepos()]!;

            /// <summary>Goto the next (forward) operation.</summary>
            void Advance() => writer.WriteLine($"goto {AdvanceLabel()};");

            /// <summary>Loads the char to the left of the current position.</summary>
            string Leftchar() => "runtext[runtextpos - 1]";

            /// <summary>Loads the char to the left of the current position and advances (leftward).</summary>
            string Leftcharnext() => "runtext[--runtextpos]";

            /// <summary>Loads the char to the right of the current position.</summary>
            string Rightchar() => "runtext[runtextpos]";

            /// <summary>Loads the char to the right of the current position and advances the current position.</summary>
            string Rightcharnext() => "runtext[runtextpos++]";

            /// <summary>
            /// Adds a backtrack note to the list of them, and returns the index of the new
            /// note (which is also the index for the jump used by the switch table)
            /// </summary>
            int AddBacktrackNote(int flags, string l, int codepos)
            {
                if (notes == null || noteCount >= notes.Length)
                {
                    var newnotes = new BacktrackNote[notes == null ? 16 : notes.Length * 2];
                    if (notes != null)
                    {
                        Array.Copy(notes, newnotes, noteCount);
                    }
                    notes = newnotes;
                }

                notes[noteCount] = new BacktrackNote(flags, l, codepos);
                return noteCount++;
            }

            /// <summary>
            /// Adds a backtrack note for the current operation; creates a new label for
            /// where the code will be, and returns the switch index.
            /// </summary>
            int AddTrack(int flags = RegexCode.Back) => AddBacktrackNote(flags, DefineLabel(), currentCodePos);

            int AddGoto(int destpos)
            {
                if (forwardJumpsThroughSwitch[destpos] == -1)
                {
                    forwardJumpsThroughSwitch[destpos] = AddBacktrackNote(0, labels[destpos]!, destpos);
                }

                return forwardJumpsThroughSwitch[destpos];
            }

            /// <summary>Pops an element off the tracking stack.</summary>
            string PopTrack() => "runtrack[runtrackpos++]";

            /// <summary>Pops an element off the grouping stack (leave it on the operand stack).</summary>
            string PopStack() => "runstack[runstackpos++]";

            /// <summary>Pops i elements off the grouping stack and discards them.</summary>
            void PopDiscardStack(int i = 1) => EmitAdd(writer, "runstackpos", i);

            /// <summary>Prologue to code that will replace the ith element on the grouping stack.</summary>
            string ReadyReplaceStack(int i) => i == 0 ? "runstack[runstackpos]" : $"runstack[runstackpos + {i}]";
        }

        /// <summary>
        /// Keeps track of an operation that needs to be referenced in the backtrack-jump
        /// switch table, and that needs backtracking code to be emitted (if flags != 0)
        /// </summary>
        private record BacktrackNote(int flags, string label, int codepos);

        private static bool EmitLoopTimeoutCounterIfNeeded(IndentedTextWriter writer, RegexMethod rm)
        {
            if (rm.MatchTimeout != Timeout.Infinite)
            {
                writer.WriteLine("int loopTimeoutCounter = 0;");
                return true;
            }

            return false;
        }

        /// <summary>Emits a timeout check.</summary>
        private static void EmitTimeoutCheck(IndentedTextWriter writer, bool hasTimeout)
        {
            const int LoopTimeoutCheckCount = 2048; // A conservative value to guarantee the correct timeout handling.
            if (hasTimeout)
            {
                // Increment counter for each loop iteration.
                // Emit code to check the timeout every 2048th iteration.
                using (EmitBlock(writer, $"if (++loopTimeoutCounter == {LoopTimeoutCheckCount})"))
                {
                    writer.WriteLine("loopTimeoutCounter = 0;");
                    writer.WriteLine("base.CheckTimeout();");
                }
                writer.WriteLine();
            }
        }

        private static bool EmitInitializeCultureForGoIfNecessary(IndentedTextWriter writer, RegexMethod rm)
        {
            if (((RegexOptions)rm.Options & RegexOptions.CultureInvariant) == 0)
            {
                bool needsCulture = ((RegexOptions)rm.Options & RegexOptions.IgnoreCase) != 0;
                if (!needsCulture)
                {
                    int[] codes = rm.Code.Codes;
                    for (int codepos = 0; codepos < codes.Length; codepos += RegexCode.OpcodeSize(codes[codepos]))
                    {
                        if ((codes[codepos] & RegexCode.Ci) == RegexCode.Ci)
                        {
                            needsCulture = true;
                            break;
                        }
                    }
                }

                if (needsCulture)
                {
                    writer.WriteLine("global::System.Globalization.TextInfo textInfo = global::System.Globalization.CultureInfo.CurrentCulture.TextInfo;");
                    return true;
                }
            }

            return false;
        }

        private static bool UseToLowerInvariant(bool hasTextInfo, RegexOptions options) => !hasTextInfo || (options & RegexOptions.CultureInvariant) != 0;

        private static string ToLower(bool hasTextInfo, RegexOptions options, string expression) => UseToLowerInvariant(hasTextInfo, options) ? $"char.ToLowerInvariant({expression})" : $"textInfo.ToLower({expression})";

        private static string ToLowerIfNeeded(bool hasTextInfo, RegexOptions options, string expression, bool toLower) => toLower ? ToLower(hasTextInfo, options, expression) : expression;

        private static string MatchCharacterClass(bool hasTextInfo, RegexOptions options, string chExpr, string charClass, bool caseInsensitive)
        {
            // We need to perform the equivalent of calling RegexRunner.CharInClass(ch, charClass),
            // but that call is relatively expensive.  Before we fall back to it, we try to optimize
            // some common cases for which we can do much better, such as known character classes
            // for which we can call a dedicated method, or a fast-path for ASCII using a lookup table.

            // First, see if the char class is a built-in one for which there's a better function
            // we can just call directly.  Everything in this section must work correctly for both
            // case-sensitive and case-insensitive modes, regardless of culture.
            switch (charClass)
            {
                case RegexCharClass.AnyClass:
                    // ideally this could just be "return true;", but we need to evaluate the expression for its side effects
                    return $"({chExpr} != -1)"; // a char is unsigned and thus won't ever be equal to -1, so this is equivalent to true

                case RegexCharClass.DigitClass:
                    return $"char.IsDigit({chExpr})";

                case RegexCharClass.NotDigitClass:
                    return $"!char.IsDigit({chExpr})";

                case RegexCharClass.SpaceClass:
                    return $"char.IsWhiteSpace({chExpr})";

                case RegexCharClass.NotSpaceClass:
                    return $"!char.IsWhiteSpace({chExpr})";
            }

            // If we're meant to be doing a case-insensitive lookup, and if we're not using the invariant culture,
            // lowercase the input.  If we're using the invariant culture, we may still end up calling ToLower later
            // on, but we may also be able to avoid it, in particular in the case of our lookup table, where we can
            // generate the lookup table already factoring in the invariant case sensitivity.  There are multiple
            // special-code paths between here and the lookup table, but we only take those if invariant is false;
            // if it were true, they'd need to use CallToLower().
            bool invariant = false;
            if (caseInsensitive)
            {
                invariant = UseToLowerInvariant(hasTextInfo, options);
                if (!invariant)
                {
                    chExpr = ToLower(hasTextInfo, options, chExpr);
                }
            }

            // Next, handle simple sets of one range, e.g. [A-Z], [0-9], etc.  This includes some built-in classes, like ECMADigitClass.
            if (!invariant && RegexCharClass.TryGetSingleRange(charClass, out char lowInclusive, out char highInclusive))
            {
                bool invert = RegexCharClass.IsNegated(charClass);
                return lowInclusive == highInclusive ?
                    $"({chExpr} {(invert ? "!=" : "==")} {Literal(lowInclusive)})" :
                    $"(((uint){chExpr}) - {Literal(lowInclusive)} {(invert ? ">" : "<=")} (uint)({Literal(highInclusive)} - {Literal(lowInclusive)}))";
            }

            // Next if the character class contains nothing but a single Unicode category, we can calle char.GetUnicodeCategory and
            // compare against it.  It has a fast-lookup path for ASCII, so is as good or better than any lookup we'd generate (plus
            // we get smaller code), and it's what we'd do for the fallback (which we get to avoid generating) as part of CharInClass.
            if (!invariant && RegexCharClass.TryGetSingleUnicodeCategory(charClass, out UnicodeCategory category, out bool negated))
            {
                return $"(char.GetUnicodeCategory({chExpr}) {(negated ? "!=" : "==")} global::System.Globalization.UnicodeCategory.{category})";
            }

            // Next, if there's only 2, 3, or 4 chars in the set (fairly common due to the sets we create for prefixes),
            // it may be cheaper and smaller to compare against each than it is to use a lookup table.  We can also special-case
            // the very common case with case insensitivity of two characters next to each other being the upper and lowercase
            // ASCII variants of each other, in which case we can use bit manipulation to avoid a comparison.
            if (!invariant && !RegexCharClass.IsNegated(charClass))
            {
                Span<char> setChars = stackalloc char[4];
                switch (RegexCharClass.GetSetChars(charClass, setChars))
                {
                    case 2:
                        return (setChars[0] | 0x20) == setChars[1] ?
                            $"(({chExpr} | 0x20) == {Literal(setChars[1])})" :
                            $"(((ch = {chExpr}) == {Literal(setChars[0])}) | (ch == {Literal(setChars[1])}))";

                    case 3:
                        return (setChars[0] | 0x20) == setChars[1] ?
                            $"((((ch = {chExpr}) | 0x20) == {Literal(setChars[1])}) | (ch == {Literal(setChars[2])}))" :
                            $"(((ch = {chExpr}) == {Literal(setChars[0])}) | (ch == {Literal(setChars[1])}) | (ch == {Literal(setChars[2])}))";

                    case 4:
                        if (((setChars[0] | 0x20) == setChars[1]) &&
                            ((setChars[2] | 0x20) == setChars[3]))
                        {
                            return $"(((ch = ({chExpr} | 0x20)) == {Literal(setChars[1])}) | (ch == {Literal(setChars[3])}))";
                        }
                        break;
                }
            }

            // Analyze the character set more to determine what code to generate.
            RegexCharClass.CharClassAnalysisResults analysis = RegexCharClass.Analyze(charClass);

            if (!invariant) // if we're being asked to do a case insensitive, invariant comparison, use the lookup table
            {
                if (analysis.ContainsNoAscii)
                {
                    // We determined that the character class contains only non-ASCII,
                    // for example if the class were [\p{IsGreek}\p{IsGreekExtended}], which is
                    // the same as [\u0370-\u03FF\u1F00-1FFF]. (In the future, we could possibly
                    // extend the analysis to produce a known lower-bound and compare against
                    // that rather than always using 128 as the pivot point.)
                    return invariant ?
                        $"((ch = {chExpr}) >= 128 && global::System.Text.RegularExpressions.RegexRunner.CharInClass(char.ToLowerInvariant((char)ch), {Literal(charClass)}))" :
                        $"((ch = {chExpr}) >= 128 && global::System.Text.RegularExpressions.RegexRunner.CharInClass((char)ch, {Literal(charClass)}))";
                }

                if (analysis.AllAsciiContained)
                {
                    // We determined that every ASCII character is in the class, for example
                    // if the class were the negated example from case 1 above:
                    // [^\p{IsGreek}\p{IsGreekExtended}].
                    return invariant ?
                        $"((ch = {chExpr}) < 128 || global::System.Text.RegularExpressions.RegexRunner.CharInClass(char.ToLowerInvariant((char)ch), {Literal(charClass)}))" :
                        $"((ch = {chExpr}) < 128 || global::System.Text.RegularExpressions.RegexRunner.CharInClass((char)ch, {Literal(charClass)}))";
                }
            }

            // Now, our big hammer is to generate a lookup table that lets us quickly index by character into a yes/no
            // answer as to whether the character is in the target character class.  However, we don't want to store
            // a lookup table for every possible character for every character class in the regular expression; at one
            // bit for each of 65K characters, that would be an 8K bitmap per character class.  Instead, we handle the
            // common case of ASCII input via such a lookup table, which at one bit for each of 128 characters is only
            // 16 bytes per character class.  We of course still need to be able to handle inputs that aren't ASCII, so
            // we check the input against 128, and have a fallback if the input is >= to it.  Determining the right
            // fallback could itself be expensive.  For example, if it's possible that a value >= 128 could match the
            // character class, we output a call to RegexRunner.CharInClass, but we don't want to have to enumerate the
            // entire character class evaluating every character against it, just to determine whether it's a match.
            // Instead, we employ some quick heuristics that will always ensure we provide a correct answer even if
            // we could have sometimes generated better code to give that answer.

            // Generate the lookup table to store 128 answers as bits. We use a const string instead of a byte[] / static
            // data property because it lets IL emit handle all the details for us.
            string bitVectorString = StringExtensions.Create(8, (charClass, invariant), static (dest, state) => // String length is 8 chars == 16 bytes == 128 bits.
            {
                for (int i = 0; i < 128; i++)
                {
                    char c = (char)i;
                    bool isSet = state.invariant ?
                        RegexCharClass.CharInClass(char.ToLowerInvariant(c), state.charClass) :
                        RegexCharClass.CharInClass(c, state.charClass);
                    if (isSet)
                    {
                        dest[i >> 4] |= (char)(1 << (i & 0xF));
                    }
                }
            });

            // We determined that the character class may contain ASCII, so we
            // output the lookup against the lookup table.

            if (analysis.ContainsOnlyAscii)
            {
                // We know that all inputs that could match are ASCII, for example if the
                // character class were [A-Za-z0-9], so since the ch is now known to be >= 128, we
                // can just fail the comparison.
                return $"((ch = {chExpr}) < 128 && ({Literal(bitVectorString)}[ch >> 4] & (1 << (ch & 0xF))) != 0)";
            }

            if (analysis.AllNonAsciiContained)
            {
                // We know that all non-ASCII inputs match, for example if the character
                // class were [^\r\n], so since we just determined the ch to be >= 128, we can just
                // give back success.
                return $"((ch = {chExpr}) >= 128 || ({Literal(bitVectorString)}[ch >> 4] & (1 << (ch & 0xF))) != 0)";
            }

            // We know that the whole class wasn't ASCII, and we don't know anything about the non-ASCII
            // characters other than that some might be included, for example if the character class
            // were [\w\d], so since ch >= 128, we need to fall back to calling CharInClass.
            return invariant ?
                $"((ch = {chExpr}) < 128 ? ({Literal(bitVectorString)}[ch >> 4] & (1 << (ch & 0xF))) != 0 : global::System.Text.RegularExpressions.RegexRunner.CharInClass(char.ToLowerInvariant((char)ch), {Literal(charClass)}))" :
                $"((ch = {chExpr}) < 128 ? ({Literal(bitVectorString)}[ch >> 4] & (1 << (ch & 0xF))) != 0 : global::System.Text.RegularExpressions.RegexRunner.CharInClass((char)ch, {Literal(charClass)}))";
        }

        private static string Literal(char c) => SymbolDisplay.FormatLiteral(c, quote: true);

        private static string Literal(string s) => SymbolDisplay.FormatLiteral(s, quote: true);

        private static FinishEmitScope EmitScope(IndentedTextWriter writer, string title, bool faux = false) => EmitBlock(writer, $"// {title}", appendBlankLine: true, faux);

        private static FinishEmitScope EmitBlock(IndentedTextWriter writer, string? clause, bool appendBlankLine = false, bool faux = false)
        {
            if (clause is not null)
            {
                writer.WriteLine(clause);
            }
            writer.WriteLine(faux ? "//{" : "{");
            writer.Indent++;
            return new FinishEmitScope(writer, appendBlankLine, faux);
        }

        private static void EmitAdd(IndentedTextWriter writer, string variable, int value)
        {
            if (value == 0)
            {
                return;
            }

            writer.WriteLine(
                value == 1 ? $"{variable}++;" :
                value == -1 ? $"{variable}--;" :
                value > 0 ? $"{variable} += {value};" :
                value < 0 && value > int.MinValue ? $"{variable} -= {-value};" :
                $"{variable} += {value.ToString(CultureInfo.InvariantCulture)};");
        }

        private readonly struct FinishEmitScope : IDisposable
        {
            private readonly IndentedTextWriter _writer;
            private readonly bool _appendBlankLine;
            private readonly bool _faux;

            public FinishEmitScope(IndentedTextWriter writer, bool appendBlankLine, bool faux)
            {
                _writer = writer;
                _appendBlankLine = appendBlankLine;
                _faux = faux;
            }

            public void Dispose()
            {
                if (_writer is not null)
                {
                    _writer.Indent--;
                    _writer.WriteLine(_faux ? "//}" : "}");
                    if (_appendBlankLine)
                    {
                        _writer.WriteLine();
                    }
                }
            }
        }
    }
}