in src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs [1420:4850]
private static void EmitTryMatchAtCurrentPosition(IndentedTextWriter writer, RegexMethod rm, Dictionary<string, string[]> requiredHelpers, bool checkOverflow)
{
// In .NET Framework and up through .NET Core 3.1, the code generated for RegexOptions.Compiled was effectively an unrolled
// version of what RegexInterpreter would process. The RegexNode tree would be turned into a series of opcodes via
// RegexWriter; the interpreter would then sit in a loop processing those opcodes, and the RegexCompiler iterated through the
// opcodes generating code for each equivalent to what the interpreter would do albeit with some decisions made at compile-time
// rather than at run-time. This approach, however, lead to complicated code that wasn't pay-for-play (e.g. a big backtracking
// jump table that all compilations went through even if there was no backtracking), that didn't factor in the shape of the
// tree (e.g. it's difficult to add optimizations based on interactions between nodes in the graph), and that didn't read well
// when decompiled from IL to C# or when directly emitted as C# as part of a source generator.
//
// This implementation is instead based on directly walking the RegexNode tree and outputting code for each node in the graph.
// A dedicated for each kind of RegexNode emits the code necessary to handle that node's processing, including recursively
// calling the relevant function for any of its children nodes. Backtracking is handled not via a giant jump table, but instead
// by emitting direct jumps to each backtracking construct. This is achieved by having all match failures jump to a "done"
// label that can be changed by a previous emitter, e.g. before EmitLoop returns, it ensures that "doneLabel" is set to the
// label that code should jump back to when backtracking. That way, a subsequent EmitXx function doesn't need to know exactly
// where to jump: it simply always jumps to "doneLabel" on match failure, and "doneLabel" is always configured to point to
// the right location. In an expression without backtracking, or before any backtracking constructs have been encountered,
// "doneLabel" is simply the final return location from the TryMatchAtCurrentPosition method that will undo any captures and exit, signaling to
// the calling scan loop that nothing was matched.
// 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 = rm.Options;
RegexTree regexTree = rm.Tree;
// Helper to define names. Names start unadorned, but as soon as there's repetition,
// they begin to have a numbered suffix.
Dictionary<string, int> usedNames = new();
// Every RegexTree is rooted in the implicit Capture for the whole expression.
// Skip the Capture node. We handle the implicit root capture specially.
RegexNode node = regexTree.Root;
Debug.Assert(node.Kind == RegexNodeKind.Capture, "Every generated tree should begin with a capture node");
Debug.Assert(node.ChildCount() == 1, "Capture nodes should have one child");
node = node.Child(0);
// In some cases, we need to emit declarations at the beginning of the method, but we only discover we need them later.
// To handle that, we build up a collection of all the declarations to include, track where they should be inserted,
// and then insert them at that position once everything else has been output.
HashSet<string> additionalDeclarations = new();
Dictionary<string, string[]> additionalLocalFunctions = new();
// In debug builds, additional code is emitted to validate that the backtracking stack is being maintained appropriately.
// When state is pushed onto the backtracking stack, an additional known value is pushed, and when it's popped, it's
// the popped value is checked against that known value, throwing an exception if they don't match. This validation code
// is currently not part of RegexCompiler, though it could be added there in the future if desired.
#if DEBUG
#pragma warning disable RS1035 // Random isn't always deterministic, but this is only for debug builds, and we've seeded the Random with a constant
Random stackCookieGenerator = new(12345); // seed for deterministic behavior
#pragma warning restore RS1035
#endif
// Declare some locals.
string sliceSpan = "slice";
writer.WriteLine("int pos = base.runtextpos;");
writer.WriteLine($"int matchStart = pos;");
writer.Flush();
int additionalDeclarationsPosition = ((StringWriter)writer.InnerWriter).GetStringBuilder().Length;
int additionalDeclarationsIndent = writer.Indent;
// The implementation tries to use const indexes into the span wherever possible, which we can do
// for all fixed-length constructs. In such cases (e.g. single chars, repeaters, strings, etc.)
// 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. When we encounter a variable-length construct, we transfer the static value to
// pos, slicing the inputSpan appropriately, and then zero out the static position.
int sliceStaticPos = 0;
SliceInputSpan(defineLocal: true);
writer.WriteLine();
// doneLabel starts out as the top-level label for the whole expression failing to match. However,
// it may be changed by the processing of a node to point to whereever subsequent match failures
// should jump to, in support of backtracking or other constructs. For example, before emitting
// the code for a branch N, an alternation will set the doneLabel to point to the label for
// processing the next branch N+1: that way, any failures in the branch N's processing will
// implicitly end up jumping to the right location without needing to know in what context it's used.
string doneLabel = ReserveName("NoMatch");
string topLevelDoneLabel = doneLabel;
// Check whether there are captures anywhere in the expression. If there isn't, we can skip all
// the boilerplate logic around uncapturing, as there won't be anything to uncapture.
bool expressionHasCaptures = rm.Analysis.MayContainCapture(node);
// Emit the code for all nodes in the tree.
EmitNode(node);
// If we fall through to this place in the code, we've successfully matched the expression.
writer.WriteLine();
writer.WriteLine("// The input matched.");
if (sliceStaticPos > 0)
{
EmitAdd(writer, "pos", sliceStaticPos); // TransferSliceStaticPosToPos would also slice, which isn't needed here
}
writer.WriteLine("base.runtextpos = pos;");
writer.WriteLine("base.Capture(0, matchStart, pos);");
writer.WriteLine("return true;");
// We're done with the match.
// Patch up any additional declarations.
InsertAdditionalDeclarations(writer, additionalDeclarations, additionalDeclarationsPosition, additionalDeclarationsIndent);
// And emit any required helpers.
if (additionalLocalFunctions.Count != 0)
{
foreach (KeyValuePair<string, string[]> localFunctions in additionalLocalFunctions.OrderBy(k => k.Key))
{
writer.WriteLine();
foreach (string line in localFunctions.Value)
{
writer.WriteLine(line);
}
}
}
return;
// Helper to create a name guaranteed to be unique within the function.
string ReserveName(string prefix)
{
usedNames.TryGetValue(prefix, out int count);
usedNames[prefix] = count + 1;
return count == 0 ? prefix : $"{prefix}{count}";
}
// Helper to emit a label. As of C# 10, labels aren't statements of their own and need to adorn a following statement;
// if a label appears just before a closing brace, then, it's a compilation error. To avoid issues there, this by
// default implements a blank statement (a semicolon) after each label, but individual uses can opt-out of the semicolon
// when it's known the label will always be followed by a statement.
void MarkLabel(string label, bool emitSemicolon = true) => writer.WriteLine($"{label}:{(emitSemicolon ? ";" : "")}");
// Gets whether calling Goto(label) will result in exiting the match method.
bool GotoWillExitMatch(string label) => label == topLevelDoneLabel;
// Emits a goto to jump to the specified label. However, if the specified label is the top-level done label indicating
// that the entire match has failed, we instead emit our epilogue, uncapturing if necessary and returning out of TryMatchAtCurrentPosition.
void Goto(string label)
{
if (GotoWillExitMatch(label))
{
// We only get here in the code if the whole expression fails to match and jumps to
// the original value of doneLabel.
if (expressionHasCaptures)
{
EmitUncaptureUntil("0");
}
writer.WriteLine("return false; // The input didn't match.");
}
else
{
writer.WriteLine($"goto {label};");
}
}
// Emits a case or default line followed by an indented body.
void CaseGoto(string clause, string label)
{
writer.WriteLine(clause);
writer.Indent++;
Goto(label);
writer.Indent--;
}
// Slices the inputSpan starting at pos until end and stores it into slice.
void SliceInputSpan(bool defineLocal = false)
{
if (defineLocal)
{
writer.Write("ReadOnlySpan<char> ");
}
writer.WriteLine($"{sliceSpan} = inputSpan.Slice(pos);");
}
// Emits the sum of a constant and a value from a local.
string Sum(int constant, string? local = null) =>
local is null ? constant.ToString(CultureInfo.InvariantCulture) :
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)})"))
{
Goto(doneLabel);
}
}
// Returns a length check for the current span slice. The check returns true if
// the span isn't long enough for the specified length.
string SpanLengthCheck(int requiredLength, string? dynamicRequiredLength = null) =>
dynamicRequiredLength is null && sliceStaticPos + requiredLength == 1 ? $"{sliceSpan}.IsEmpty" :
$"(uint){sliceSpan}.Length < {Sum(sliceStaticPos + requiredLength, dynamicRequiredLength)}";
// Adds the value of sliceStaticPos into the pos local, slices slice by the corresponding amount,
// and zeros out sliceStaticPos.
void TransferSliceStaticPosToPos(bool forceSliceReload = false)
{
if (sliceStaticPos > 0)
{
EmitAdd(writer, "pos", sliceStaticPos);
sliceStaticPos = 0;
SliceInputSpan();
}
else if (forceSliceReload)
{
SliceInputSpan();
}
}
// Emits the code for an alternation.
void EmitAlternation(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Alternate, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() >= 2, $"Expected at least 2 children, found {node.ChildCount()}");
int childCount = node.ChildCount();
Debug.Assert(childCount >= 2);
string originalDoneLabel = doneLabel;
// Both atomic and non-atomic are supported. While a parent RegexNode.Atomic node will itself
// successfully prevent backtracking into this child node, we can emit better / cheaper code
// for an Alternate when it is atomic, so we still take it into account here.
Debug.Assert(node.Parent is not null);
bool isAtomic = rm.Analysis.IsAtomicByAncestor(node);
// 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. However,
// we can't goto _into_ switch cases, which means we can't use this approach if there's any
// possibility of backtracking into the alternation.
bool useSwitchedBranches = false;
if ((node.Options & RegexOptions.RightToLeft) == 0)
{
useSwitchedBranches = isAtomic;
if (!useSwitchedBranches)
{
useSwitchedBranches = true;
for (int i = 0; i < childCount; i++)
{
if (rm.Analysis.MayBacktrack(node.Child(i)))
{
useSwitchedBranches = false;
break;
}
}
}
}
// Detect whether every branch begins with one or more unique characters.
const int SetCharsSize = 64; // arbitrary limit; we want it to be large enough to handle ignore-case of common sets, like hex, the latin alphabet, etc.
Span<char> setChars = stackalloc char[SetCharsSize];
if (useSwitchedBranches)
{
// Iterate through every branch, seeing if we can easily find a starting One, Multi, or small Set.
// If we can, extract its starting char (or multiple in the case of a set), validate that all such
// starting characters are unique relative to all the branches.
var seenChars = new HashSet<char>();
for (int i = 0; i < childCount && useSwitchedBranches; i++)
{
// Look for the guaranteed starting node that's a one, multi, set,
// or loop of one of those with at least one minimum iteration. We need to exclude notones.
if (node.Child(i).FindStartingLiteralNode(allowZeroWidth: false) is not RegexNode startingLiteralNode ||
startingLiteralNode.IsNotoneFamily)
{
useSwitchedBranches = false;
break;
}
// If it's a One or a Multi, get the first character and add it to the set.
// If it was already in the set, we can't apply this optimization.
if (startingLiteralNode.IsOneFamily || startingLiteralNode.Kind is RegexNodeKind.Multi)
{
if (!seenChars.Add(startingLiteralNode.FirstCharOfOneOrMulti()))
{
useSwitchedBranches = false;
break;
}
}
else
{
// The branch begins with a set. Make sure it's a set of only a few characters
// and get them. If we can't, we can't apply this optimization.
Debug.Assert(startingLiteralNode.IsSetFamily);
int numChars;
if (RegexCharClass.IsNegated(startingLiteralNode.Str!) ||
(numChars = RegexCharClass.GetSetChars(startingLiteralNode.Str!, setChars)) == 0)
{
useSwitchedBranches = false;
break;
}
// Check to make sure each of the chars is unique relative to all other branches examined.
foreach (char c in setChars.Slice(0, numChars))
{
if (!seenChars.Add(c))
{
useSwitchedBranches = false;
break;
}
}
}
}
}
if (useSwitchedBranches)
{
// 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. In some
// cases there are enough branches that the compiler will emit a jump table. In others
// it'll optimize the order of checks in order to minimize the total number in the worst
// case. In any case, we get easier to read and reason about C#.
EmitSwitchedBranches();
}
else
{
EmitAllBranches();
}
return;
// Emits the code for a switch-based alternation of non-overlapping branches.
void EmitSwitchedBranches()
{
// We need at least 1 remaining character in the span, for the char to switch on.
EmitSpanLengthCheck(1);
writer.WriteLine();
// Emit a switch statement on the first char of each branch.
using (EmitBlock(writer, $"switch ({sliceSpan}[{sliceStaticPos}])"))
{
Span<char> setChars = stackalloc char[SetCharsSize]; // needs to be same size as detection check in caller
int startingSliceStaticPos = sliceStaticPos;
// Emit a case for each branch.
for (int i = 0; i < childCount; i++)
{
sliceStaticPos = startingSliceStaticPos;
// We know we're only in this code if every branch has a valid starting literal node. Get it.
// We also get the immediate child. Ideally they're the same, in which case we might be able to
// use the switch as the processing of that node, e.g. if the node is a One, then by matching the
// literal via the switch, we've fully processed it. But there may be other cases in which it's not
// sufficient, e.g. if that one was wrapped in a Capture, we still want to emit the capture code,
// and for simplicity, we still end up emitting the re-evaluation of that character. It's still much
// cheaper to do this than to emit the full alternation code.
RegexNode child = node.Child(i);
RegexNode? startingLiteralNode = child.FindStartingLiteralNode(allowZeroWidth: false);
Debug.Assert(startingLiteralNode is not null, "Unexpectedly couldn't find the branch starting node.");
// Emit the case for this branch to match on the first character.
if (startingLiteralNode.IsSetFamily)
{
int numChars = RegexCharClass.GetSetChars(startingLiteralNode.Str!, setChars);
Debug.Assert(numChars != 0);
writer.WriteLine($"case {string.Join(" or ", setChars.Slice(0, numChars).ToArray().Select(Literal))}:");
}
else
{
writer.WriteLine($"case {Literal(startingLiteralNode.FirstCharOfOneOrMulti())}:");
}
writer.Indent++;
// Emit the code for the branch, without the first character that was already matched in the switch.
RegexNode? remainder = null;
HandleChild:
switch (child.Kind)
{
case RegexNodeKind.One:
case RegexNodeKind.Set:
// The character was handled entirely by the switch. No additional matching is needed.
sliceStaticPos++;
break;
case RegexNodeKind.Multi:
// First character was handled by the switch. Emit matching code for the remainder of the multi string.
sliceStaticPos++;
EmitNode(child.Str!.Length == 2 ?
new RegexNode(RegexNodeKind.One, child.Options, child.Str![1]) :
new RegexNode(RegexNodeKind.Multi, child.Options, child.Str!.Substring(1)));
writer.WriteLine();
break;
case RegexNodeKind.Concatenate when child.Child(0) == startingLiteralNode && (startingLiteralNode.Kind is RegexNodeKind.One or RegexNodeKind.Set or RegexNodeKind.Multi):
// This is a concatenation where its first node is the starting literal we found and that starting literal
// is one of the nodes above that we know how to handle completely. This is a common
// enough case that we want to special-case it to avoid duplicating the processing for that character
// unnecessarily. So, we'll shave off that first node from the concatenation and then handle the remainder.
// Note that it's critical startingLiteralNode is something we can fully handle above: if it's not,
// we'll end up losing some of the pattern due to overwriting `remainder`.
remainder = child;
child = child.Child(0);
remainder.ReplaceChild(0, new RegexNode(RegexNodeKind.Empty, remainder.Options));
goto HandleChild; // reprocess just the first node that was saved; the remainder will then be processed below
default:
Debug.Assert(remainder is null);
remainder = child;
break;
}
if (remainder is not null)
{
// Emit a full match for whatever part of the child we haven't yet handled.
EmitNode(remainder);
writer.WriteLine();
}
// This is only ever used for atomic alternations, so we can simply reset the doneLabel
// after emitting the child, as nothing will backtrack here (and we need to reset it
// so that all branches see the original).
doneLabel = originalDoneLabel;
// If we get here in the generated code, the branch completed successfully.
// Before jumping to the end, we need to zero out sliceStaticPos, so that no
// matter what the value is after the branch, whatever follows the alternate
// will see the same sliceStaticPos.
TransferSliceStaticPosToPos();
writer.WriteLine($"break;");
writer.WriteLine();
writer.Indent--;
}
// Default branch if the character didn't match the start of any branches.
CaseGoto("default:", doneLabel);
}
}
void EmitAllBranches()
{
// Label to jump to when any branch completes successfully.
string matchLabel = ReserveName("AlternationMatch");
// Save off pos. We'll need to reset this each time a branch fails.
string startingPos = ReserveName("alternation_starting_pos");
bool canUseLocalsForAllState = !isAtomic && !rm.Analysis.IsInLoop(node);
if (canUseLocalsForAllState)
{
// Because of how control flow and definite assignment works in the C# compiler, we can end
// up in situations where backtracking by hopping between labels leads the compiler to see
// things as not definitely assigned even if in practice they will be. To avoid compilation
// errors with such complicated patterns we need to ensure the locals are declared and
// initialized at the beginning of the method.
additionalDeclarations.Add($"int {startingPos} = 0;");
writer.WriteLine($"{startingPos} = pos;");
}
else
{
writer.WriteLine($"int {startingPos} = pos;");
}
int startingSliceStaticPos = sliceStaticPos;
// We need to be able to undo captures in two situations:
// - If a branch of the alternation itself contains captures, then if that branch
// fails to match, any captures from that branch until that failure point need to
// be uncaptured prior to jumping to the next branch.
// - If the expression after the alternation contains captures, then failures
// to match in those expressions could trigger backtracking back into the
// alternation, and thus we need uncapture any of them.
// As such, if the alternation contains captures or if it's not atomic, we need
// to grab the current crawl position so we can unwind back to it when necessary.
// We can do all of the uncapturing as part of falling through to the next branch.
// If we fail in a branch, then such uncapturing will unwind back to the position
// at the start of the alternation. If we fail after the alternation, and the
// matched branch didn't contain any backtracking, then the failure will end up
// jumping to the next branch, which will unwind the captures. And if we fail after
// the alternation and the matched branch did contain backtracking, that backtracking
// construct is responsible for unwinding back to its starting crawl position. If
// it eventually ends up failing, that failure will result in jumping to the next branch
// of the alternation, which will again dutifully unwind the remaining captures until
// what they were at the start of the alternation. Of course, if there are no captures
// anywhere in the regex, we don't have to do any of that.
string? startingCapturePos = null;
if (expressionHasCaptures && (rm.Analysis.MayContainCapture(node) || !isAtomic))
{
startingCapturePos = ReserveName("alternation_starting_capturepos");
if (canUseLocalsForAllState)
{
additionalDeclarations.Add($"int {startingCapturePos} = 0;");
writer.WriteLine($"{startingCapturePos} = base.Crawlpos();");
}
else
{
writer.WriteLine($"int {startingCapturePos} = base.Crawlpos();");
}
}
writer.WriteLine();
// After executing the alternation, subsequent matching may fail, at which point execution
// will need to backtrack to the alternation. We emit a branching table at the end of the
// alternation, with a label that will be left as the "doneLabel" upon exiting emitting the
// alternation. The branch table is populated with an entry for each branch of the alternation,
// containing either the label for the last backtracking construct in the branch if such a construct
// existed (in which case the doneLabel upon emitting that node will be different from before it)
// or the label for the next branch.
var labelMap = new string[childCount];
string backtrackLabel = ReserveName("AlternationBacktrack");
string? currentBranch = null;
if (canUseLocalsForAllState)
{
// We're not atomic, so we'll have to handle backtracking, but we're not inside of a loop,
// so we can store the current branch in a local rather than pushing it on to the backtracking
// stack (if we were in a loop, such a local couldn't be used as it could be overwritten by
// a subsequent iteration of that outer loop).
currentBranch = ReserveName("alternation_branch");
additionalDeclarations.Add($"int {currentBranch} = 0;");
}
int stackCookie = CreateStackCookie();
for (int i = 0; i < childCount; i++)
{
// If the alternation isn't atomic, backtracking may require our jump table jumping back
// into these branches, so we can't use actual scopes, as that would hide the labels.
using (EmitBlock(writer, $"// Branch {i}", faux: !isAtomic))
{
bool isLastBranch = i == childCount - 1;
string? nextBranch = null;
if (!isLastBranch)
{
// Failure to match any branch other than the last one should result
// in jumping to process the next branch.
nextBranch = ReserveName("AlternationBranch");
doneLabel = nextBranch;
}
else
{
// Failure to match the last branch is equivalent to failing to match
// the whole alternation, which means those failures should jump to
// what "doneLabel" was defined as when starting the alternation.
doneLabel = originalDoneLabel;
}
// Emit the code for each branch.
EmitNode(node.Child(i));
writer.WriteLine();
// Add this branch to the backtracking table. At this point, either the child
// had backtracking constructs, in which case doneLabel points to the last one
// and that's where we'll want to jump to, or it doesn't, in which case doneLabel
// still points to the nextBranch, which similarly is where we'll want to jump to.
if (!isAtomic)
{
// If we're inside of a loop, push the state we need to preserve on to the
// the backtracking stack. If we're not inside of a loop, simply ensure all
// the relevant state is stored in our locals.
if (currentBranch is null)
{
EmitStackPush(stackCookie + i, startingCapturePos is not null ?
[i.ToString(), startingPos, startingCapturePos] :
[i.ToString(), startingPos]);
}
else
{
writer.WriteLine($"{currentBranch} = {i};");
}
}
labelMap[i] = doneLabel;
// If we get here in the generated code, the branch completed successfully.
// Before jumping to the end, we need to zero out sliceStaticPos, so that no
// matter what the value is after the branch, whatever follows the alternate
// will see the same sliceStaticPos.
TransferSliceStaticPosToPos();
if (!isLastBranch || !isAtomic)
{
// If this isn't the last branch, we're about to output a reset section,
// and if this isn't atomic, there will be a backtracking section before
// the end of the method. In both of those cases, we've successfully
// matched and need to skip over that code. If, however, this is the
// last branch and this is an atomic alternation, we can just fall
// through to the successfully matched location.
Goto(matchLabel);
}
// Reset state for next branch and loop around to generate it. This includes
// setting pos back to what it was at the beginning of the alternation,
// updating slice to be the full length it was, and if there's a capture that
// needs to be reset, uncapturing it.
if (!isLastBranch)
{
writer.WriteLine();
MarkLabel(nextBranch!, emitSemicolon: false);
writer.WriteLine($"pos = {startingPos};");
SliceInputSpan();
sliceStaticPos = startingSliceStaticPos;
if (startingCapturePos is not null)
{
EmitUncaptureUntil(startingCapturePos);
}
}
}
writer.WriteLine();
}
// We should never fall through to this location in the generated code. Either
// a branch succeeded in matching and jumped to the end, or a branch failed in
// matching and jumped to the next branch location. We only get to this code
// if backtracking occurs and the code explicitly jumps here based on our setting
// "doneLabel" to the label for this section. Thus, we only need to emit it if
// something can backtrack to us, which can't happen if we're inside of an atomic
// node. Thus, emit the backtracking section only if we're non-atomic.
if (isAtomic)
{
doneLabel = originalDoneLabel;
}
else
{
doneLabel = backtrackLabel;
MarkLabel(backtrackLabel, emitSemicolon: false);
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
string switchClause;
if (currentBranch is null)
{
// We're in a loop, so we use the backtracking stack to persist our state.
// Pop it off and validate the stack position.
EmitStackPop(0, startingCapturePos is not null ?
[startingCapturePos, startingPos] :
[startingPos]);
switchClause = ValidateStackCookieWithAdditionAndReturnPoppedStack(stackCookie);
}
else
{
// We're not in a loop, so our locals already store the state we need.
switchClause = currentBranch;
}
using (EmitBlock(writer, $"switch ({switchClause})"))
{
for (int i = 0; i < labelMap.Length; i++)
{
CaseGoto($"case {i}:", labelMap[i]);
}
}
writer.WriteLine();
}
// Successfully completed the alternate.
MarkLabel(matchLabel);
Debug.Assert(sliceStaticPos == 0);
}
}
// Emits the code to handle a backreference.
void EmitBackreference(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Backreference, $"Unexpected type: {node.Kind}");
int capnum = RegexParser.MapCaptureNumber(node.M, rm.Tree.CaptureNumberSparseMapping);
if (sliceStaticPos > 0)
{
TransferSliceStaticPosToPos();
writer.WriteLine();
}
// If the specified capture hasn't yet captured anything, fail to match... except when using RegexOptions.ECMAScript,
// in which case per ECMA 262 section 21.2.2.9 the backreference should succeed.
if ((node.Options & RegexOptions.ECMAScript) != 0)
{
writer.WriteLine($"// If the {DescribeCapture(node.M, rm)} hasn't matched, the backreference matches with RegexOptions.ECMAScript rules.");
using (EmitBlock(writer, $"if (base.IsMatched({capnum}))"))
{
EmitWhenHasCapture();
}
}
else
{
writer.WriteLine($"// If the {DescribeCapture(node.M, rm)} hasn't matched, the backreference doesn't match.");
using (EmitBlock(writer, $"if (!base.IsMatched({capnum}))"))
{
Goto(doneLabel);
}
writer.WriteLine();
EmitWhenHasCapture();
}
void EmitWhenHasCapture()
{
writer.WriteLine("// Get the captured text. If it doesn't match at the current position, the backreference doesn't match.");
additionalDeclarations.Add("int matchLength = 0;");
writer.WriteLine($"matchLength = base.MatchLength({capnum});");
// Validate that the remaining length of the slice is sufficient
// to possibly match, and then do a SequenceEqual against the matched text.
if ((node.Options & RegexOptions.RightToLeft) == 0)
{
writer.WriteLine($"if ({sliceSpan}.Length < matchLength || ");
using (EmitBlock(writer, $" !inputSpan.Slice(base.MatchIndex({capnum}), matchLength).SequenceEqual({sliceSpan}.Slice(0, matchLength)))"))
{
Goto(doneLabel);
}
writer.WriteLine();
writer.WriteLine($"pos += matchLength;");
}
else
{
writer.WriteLine($"if (pos < matchLength || ");
using (EmitBlock(writer, $" !inputSpan.Slice(base.MatchIndex({capnum}), matchLength).SequenceEqual(inputSpan.Slice(pos - matchLength, matchLength)))"))
{
Goto(doneLabel);
}
writer.WriteLine();
writer.WriteLine($"pos -= matchLength;");
}
SliceInputSpan();
}
}
// Emits the code for an if(backreference)-then-else conditional.
void EmitBackreferenceConditional(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.BackreferenceConditional, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() == 2, $"Expected 2 children, found {node.ChildCount()}");
// We're branching in a complicated fashion. Make sure sliceStaticPos is 0.
TransferSliceStaticPosToPos();
int stackCookie = CreateStackCookie();
// Get the capture number to test.
int capnum = RegexParser.MapCaptureNumber(node.M, rm.Tree.CaptureNumberSparseMapping);
// Get the "yes" branch and the "no" branch. The "no" branch is optional in syntax and is thus
// somewhat likely to be Empty.
RegexNode yesBranch = node.Child(0);
RegexNode? noBranch = node.Child(1) is { Kind: not RegexNodeKind.Empty } childNo ? childNo : null;
string originalDoneLabel = doneLabel;
// If the child branches might backtrack, we can't emit the branches inside constructs that
// require braces, e.g. if/else, even though that would yield more idiomatic output.
// But if we know for certain they won't backtrack, we can output the nicer code.
if (rm.Analysis.IsAtomicByAncestor(node) || (!rm.Analysis.MayBacktrack(yesBranch) && (noBranch is null || !rm.Analysis.MayBacktrack(noBranch))))
{
using (EmitBlock(writer, $"if (base.IsMatched({capnum}))"))
{
writer.WriteLine($"// The {DescribeCapture(node.M, rm)} captured a value. Match the first branch.");
EmitNode(yesBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
}
if (noBranch is not null)
{
using (EmitBlock(writer, $"else"))
{
writer.WriteLine($"// Otherwise, match the second branch.");
EmitNode(noBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
}
}
doneLabel = originalDoneLabel; // atomicity
return;
}
string refNotMatched = ReserveName("ConditionalBackreferenceNotMatched");
string endConditional = ReserveName("ConditionalBackreferenceEnd");
// As with alternations, we have potentially multiple branches, each of which may contain
// backtracking constructs, but the expression after the conditional needs a single target
// to backtrack to. So, we expose a single Backtrack label and track which branch was
// followed in this resumeAt local.
string resumeAt = ReserveName("conditionalbackreference_branch");
bool isInLoop = rm.Analysis.IsInLoop(node);
if (isInLoop)
{
writer.WriteLine($"int {resumeAt};");
}
else
{
additionalDeclarations.Add($"int {resumeAt} = 0;");
}
// While it would be nicely readable to use an if/else block, if the branches contain
// anything that triggers backtracking, labels will end up being defined, and if they're
// inside the scope block for the if or else, that will prevent jumping to them from
// elsewhere. So we implement the if/else with labels and gotos manually.
// Check to see if the specified capture number was captured.
using (EmitBlock(writer, $"if (!base.IsMatched({capnum}))"))
{
Goto(refNotMatched);
}
writer.WriteLine();
// The specified capture was captured. Run the "yes" branch.
// If it successfully matches, jump to the end.
EmitNode(yesBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
string postYesDoneLabel = doneLabel;
if (postYesDoneLabel != originalDoneLabel || isInLoop)
{
writer.WriteLine($"{resumeAt} = 0;");
}
bool needsEndConditional = postYesDoneLabel != originalDoneLabel || noBranch is not null;
if (needsEndConditional)
{
Goto(endConditional);
writer.WriteLine();
}
MarkLabel(refNotMatched);
string postNoDoneLabel = originalDoneLabel;
if (noBranch is not null)
{
// Output the no branch.
doneLabel = originalDoneLabel;
EmitNode(noBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
postNoDoneLabel = doneLabel;
if (postNoDoneLabel != originalDoneLabel || isInLoop)
{
writer.WriteLine($"{resumeAt} = 1;");
}
}
else
{
// There's only a yes branch. If it's going to cause us to output a backtracking
// label but code may not end up taking the yes branch path, we need to emit a resumeAt
// that will cause the backtracking to immediately pass through this node.
if (postYesDoneLabel != originalDoneLabel || isInLoop)
{
writer.WriteLine($"{resumeAt} = 2;");
}
}
// If either the yes branch or the no branch contained backtracking, subsequent expressions
// might try to backtrack to here, so output a backtracking map based on resumeAt.
bool hasBacktracking = postYesDoneLabel != originalDoneLabel || postNoDoneLabel != originalDoneLabel;
if (hasBacktracking)
{
// Skip the backtracking section.
Goto(endConditional);
writer.WriteLine();
// Backtrack section
string backtrack = ReserveName("ConditionalBackreferenceBacktrack");
doneLabel = backtrack;
MarkLabel(backtrack, emitSemicolon: false);
// Pop from the stack the branch that was used and jump back to its backtracking location.
// If we're not in a loop, though, we won't have pushed it on to the stack as nothing will
// have been able to overwrite it in the interim, so we can just trust the value already in
// the local.
if (isInLoop)
{
EmitStackPop(stackCookie, resumeAt);
}
using (EmitBlock(writer, $"switch ({resumeAt})"))
{
if (postYesDoneLabel != originalDoneLabel)
{
CaseGoto("case 0:", postYesDoneLabel);
}
if (postNoDoneLabel != originalDoneLabel)
{
CaseGoto("case 1:", postNoDoneLabel);
}
CaseGoto("default:", originalDoneLabel);
}
}
if (needsEndConditional)
{
MarkLabel(endConditional);
}
if (hasBacktracking && isInLoop)
{
// We're not atomic and at least one of the yes or no branches contained backtracking constructs,
// so finish outputting our backtracking logic, which involves pushing onto the stack which
// branch to backtrack into. If we're not in a loop, though, nothing else can overwrite this local
// in the interim, so we can avoid pushing it.
EmitStackPush(stackCookie, resumeAt);
}
}
// Emits the code for an if(expression)-then-else conditional.
void EmitExpressionConditional(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.ExpressionConditional, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() == 3, $"Expected 3 children, found {node.ChildCount()}");
bool isAtomic = rm.Analysis.IsAtomicByAncestor(node);
// We're branching in a complicated fashion. Make sure sliceStaticPos is 0.
TransferSliceStaticPosToPos();
// The first child node is the condition expression. If this matches, then we branch to the "yes" branch.
// If it doesn't match, then we branch to the optional "no" branch if it exists, or simply skip the "yes"
// branch, otherwise. The condition is treated as a positive lookaround.
RegexNode condition = node.Child(0);
// Get the "yes" branch and the "no" branch. The "no" branch is optional in syntax and is thus
// somewhat likely to be Empty.
RegexNode yesBranch = node.Child(1);
RegexNode? noBranch = node.Child(2) is { Kind: not RegexNodeKind.Empty } childNo ? childNo : null;
string originalDoneLabel = doneLabel;
string expressionNotMatched = ReserveName("ConditionalExpressionNotMatched");
string endConditional = ReserveName("ConditionalExpressionEnd");
// As with alternations, we have potentially multiple branches, each of which may contain
// backtracking constructs, but the expression after the condition needs a single target
// to backtrack to. So, we expose a single Backtrack label and track which branch was
// followed in this resumeAt local.
bool isInLoop = false;
string resumeAt = ReserveName("conditionalexpression_branch");
if (!isAtomic)
{
isInLoop = rm.Analysis.IsInLoop(node);
if (isInLoop)
{
writer.WriteLine($"int {resumeAt} = 0;");
}
else
{
additionalDeclarations.Add($"int {resumeAt} = 0;");
}
}
// If the condition expression has captures, we'll need to uncapture them in the case of no match.
string? startingCapturePos = null;
if (rm.Analysis.MayContainCapture(condition))
{
startingCapturePos = ReserveName("conditionalexpression_starting_capturepos");
writer.WriteLine($"int {startingCapturePos} = base.Crawlpos();");
}
// Emit the condition expression. Route any failures to after the yes branch. This code is almost
// the same as for a positive lookaround; however, a positive lookaround only needs to reset the position
// on a successful match, as a failed match fails the whole expression; here, we need to reset the
// position on completion, regardless of whether the match is successful or not.
doneLabel = expressionNotMatched;
// Save off pos. We'll need to reset this upon successful completion of the lookaround.
string startingPos = ReserveName("conditionalexpression_starting_pos");
writer.WriteLine($"int {startingPos} = pos;");
writer.WriteLine();
int startingSliceStaticPos = sliceStaticPos;
// Emit the condition. The condition expression is a zero-width assertion, which is atomic,
// so prevent backtracking into it.
writer.WriteLine("// Condition:");
if (rm.Analysis.MayBacktrack(condition))
{
// Condition expressions are treated like positive lookarounds and thus are implicitly atomic,
// so we need to emit the node as atomic if it might backtrack.
EmitAtomic(node, null);
}
else
{
EmitNode(condition);
}
writer.WriteLine();
doneLabel = originalDoneLabel;
// After the condition completes successfully, reset the text positions.
// Do not reset captures, which persist beyond the lookaround.
writer.WriteLine("// Condition matched:");
writer.WriteLine($"pos = {startingPos};");
SliceInputSpan();
sliceStaticPos = startingSliceStaticPos;
writer.WriteLine();
// The expression matched. Run the "yes" branch. If it successfully matches, jump to the end.
EmitNode(yesBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
string postYesDoneLabel = doneLabel;
if (!isAtomic && postYesDoneLabel != originalDoneLabel)
{
writer.WriteLine($"{resumeAt} = 0;");
}
Goto(endConditional);
writer.WriteLine();
// After the condition completes unsuccessfully, reset the text positions
// _and_ reset captures, which should not persist when the whole expression failed.
writer.WriteLine("// Condition did not match:");
MarkLabel(expressionNotMatched, emitSemicolon: false);
writer.WriteLine($"pos = {startingPos};");
SliceInputSpan();
sliceStaticPos = startingSliceStaticPos;
if (startingCapturePos is not null)
{
EmitUncaptureUntil(startingCapturePos);
}
writer.WriteLine();
string postNoDoneLabel = originalDoneLabel;
if (noBranch is not null)
{
// Output the no branch.
doneLabel = originalDoneLabel;
EmitNode(noBranch);
writer.WriteLine();
TransferSliceStaticPosToPos(); // make sure sliceStaticPos is 0 after each branch
postNoDoneLabel = doneLabel;
if (!isAtomic && postNoDoneLabel != originalDoneLabel)
{
writer.WriteLine($"{resumeAt} = 1;");
}
}
else
{
// There's only a yes branch. If it's going to cause us to output a backtracking
// label but code may not end up taking the yes branch path, we need to emit a resumeAt
// that will cause the backtracking to immediately pass through this node.
if (!isAtomic && postYesDoneLabel != originalDoneLabel)
{
writer.WriteLine($"{resumeAt} = 2;");
}
}
// If either the yes branch or the no branch contained backtracking, subsequent expressions
// might try to backtrack to here, so output a backtracking map based on resumeAt.
if (isAtomic || (postYesDoneLabel == originalDoneLabel && postNoDoneLabel == originalDoneLabel))
{
doneLabel = originalDoneLabel;
MarkLabel(endConditional);
}
else
{
// Skip the backtracking section.
Goto(endConditional);
writer.WriteLine();
string backtrack = ReserveName("ConditionalExpressionBacktrack");
doneLabel = backtrack;
MarkLabel(backtrack, emitSemicolon: false);
int stackCookie = CreateStackCookie();
if (isInLoop)
{
// If we're not in a loop, the local will maintain its value until backtracking occurs.
// If we are in a loop, multiple iterations need their own value, so we need to use the stack.
EmitStackPop(stackCookie, resumeAt);
}
using (EmitBlock(writer, $"switch ({resumeAt})"))
{
if (postYesDoneLabel != originalDoneLabel)
{
CaseGoto("case 0:", postYesDoneLabel);
}
if (postNoDoneLabel != originalDoneLabel)
{
CaseGoto("case 1:", postNoDoneLabel);
}
CaseGoto("default:", originalDoneLabel);
}
MarkLabel(endConditional, emitSemicolon: !isInLoop);
if (isInLoop)
{
EmitStackPush(stackCookie, resumeAt);
}
}
}
// Emits the code for a Capture node.
void EmitCapture(RegexNode node, RegexNode? subsequent = null)
{
Debug.Assert(node.Kind is RegexNodeKind.Capture, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
int capnum = RegexParser.MapCaptureNumber(node.M, rm.Tree.CaptureNumberSparseMapping);
int uncapnum = RegexParser.MapCaptureNumber(node.N, rm.Tree.CaptureNumberSparseMapping);
bool isAtomic = rm.Analysis.IsAtomicByAncestor(node);
bool isInLoop = rm.Analysis.IsInLoop(node);
TransferSliceStaticPosToPos();
string startingPos = ReserveName("capture_starting_pos");
if (isInLoop)
{
writer.WriteLine($"int {startingPos} = pos;");
}
else
{
additionalDeclarations.Add($"int {startingPos} = 0;");
writer.WriteLine($"{startingPos} = pos;");
}
writer.WriteLine();
RegexNode child = node.Child(0);
if (uncapnum != -1)
{
using (EmitBlock(writer, $"if (!base.IsMatched({uncapnum}))"))
{
Goto(doneLabel);
}
writer.WriteLine();
}
// Emit child node.
string originalDoneLabel = doneLabel;
EmitNode(child, subsequent);
bool childBacktracks = doneLabel != originalDoneLabel;
writer.WriteLine();
TransferSliceStaticPosToPos();
if (uncapnum == -1)
{
writer.WriteLine($"base.Capture({capnum}, {startingPos}, pos);");
}
else
{
writer.WriteLine($"base.TransferCapture({capnum}, {uncapnum}, {startingPos}, pos);");
}
if (isAtomic || !childBacktracks)
{
// If the capture is atomic and nothing can backtrack into it, we're done.
// Similarly, even if the capture isn't atomic, if the captured expression
// doesn't do any backtracking, we're done.
doneLabel = originalDoneLabel;
}
else
{
// We're not atomic and the child node backtracks. When it does, we need
// to ensure that the starting position for the capture is appropriately
// reset to what it was initially (it could have changed as part of being
// in a loop or similar). So, we emit a backtracking section that
// pushes/pops the starting position before falling through.
writer.WriteLine();
int stackCookie = CreateStackCookie();
if (isInLoop)
{
// If we're in a loop, different iterations of the loop need their own
// starting position, so push it on to the stack. If we're not in a loop,
// the local will maintain its value and will suffice.
EmitStackPush(stackCookie, startingPos);
}
// Skip past the backtracking section
string end = ReserveName("CaptureSkipBacktrack");
Goto(end);
writer.WriteLine();
// Emit a backtracking section that restores the capture's state and then jumps to the previous done label
string backtrack = ReserveName($"CaptureBacktrack");
MarkLabel(backtrack, emitSemicolon: false);
if (isInLoop)
{
EmitStackPop(stackCookie, startingPos);
}
Goto(doneLabel);
writer.WriteLine();
doneLabel = backtrack;
MarkLabel(end);
}
}
// Emits the code to handle a positive lookaround assertion. This is a positive lookahead
// for left-to-right and a positive lookbehind for right-to-left.
void EmitPositiveLookaroundAssertion(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.PositiveLookaround, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
if (rm.Analysis.HasRightToLeft)
{
// Lookarounds are the only places in the node tree where we might change direction,
// i.e. where we might go from RegexOptions.None to RegexOptions.RightToLeft, or vice
// versa. This is because lookbehinds are implemented by making the whole subgraph be
// RegexOptions.RightToLeft and reversed. Since we use static position to optimize left-to-right
// and don't use it in support of right-to-left, we need to resync the static position
// to the current position when entering a lookaround, just in case we're changing direction.
TransferSliceStaticPosToPos(forceSliceReload: true);
}
// Save off pos. We'll need to reset this upon successful completion of the lookaround.
string startingPos = ReserveName((node.Options & RegexOptions.RightToLeft) != 0 ? "positivelookbehind_starting_pos" : "positivelookahead_starting_pos");
writer.WriteLine($"int {startingPos} = pos;");
writer.WriteLine();
int startingSliceStaticPos = sliceStaticPos;
// Check for timeout. Lookarounds result in re-processing the same input, so while not
// technically backtracking, it's appropriate to have a timeout check.
EmitTimeoutCheckIfNeeded(writer, rm);
// Emit the child.
RegexNode child = node.Child(0);
if (rm.Analysis.MayBacktrack(child))
{
// Lookarounds are implicitly atomic, so we need to emit the node as atomic if it might backtrack.
EmitAtomic(node, null);
}
else
{
EmitNode(child);
}
// After the child completes successfully, reset the text positions.
// Do not reset captures, which persist beyond the lookaround.
writer.WriteLine();
writer.WriteLine($"pos = {startingPos};");
SliceInputSpan();
sliceStaticPos = startingSliceStaticPos;
}
// Emits the code to handle a negative lookaround assertion. This is a negative lookahead
// for left-to-right and a negative lookbehind for right-to-left.
void EmitNegativeLookaroundAssertion(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.NegativeLookaround, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
if (rm.Analysis.HasRightToLeft)
{
// Lookarounds are the only places in the node tree where we might change direction,
// i.e. where we might go from RegexOptions.None to RegexOptions.RightToLeft, or vice
// versa. This is because lookbehinds are implemented by making the whole subgraph be
// RegexOptions.RightToLeft and reversed. Since we use static position to optimize left-to-right
// and don't use it in support of right-to-left, we need to resync the static position
// to the current position when entering a lookaround, just in case we're changing direction.
TransferSliceStaticPosToPos(forceSliceReload: true);
}
string originalDoneLabel = doneLabel;
// Save off pos. We'll need to reset this upon successful completion of the lookaround.
string variablePrefix = (node.Options & RegexOptions.RightToLeft) != 0 ? "negativelookbehind_" : "negativelookahead_";
string startingPos = ReserveName($"{variablePrefix}_starting_pos");
writer.WriteLine($"int {startingPos} = pos;");
int startingSliceStaticPos = sliceStaticPos;
string negativeLookaroundDoneLabel = ReserveName("NegativeLookaroundMatch");
doneLabel = negativeLookaroundDoneLabel;
// Check for timeout. Lookarounds result in re-processing the same input, so while not
// technically backtracking, it's appropriate to have a timeout check.
EmitTimeoutCheckIfNeeded(writer, rm);
RegexNode child = node.Child(0);
// Ensure we're able to uncapture anything captured by the child.
int stackCookie = CreateStackCookie();
bool isInLoop = false;
string? capturePos = null;
bool hasCaptures = rm.Analysis.MayContainCapture(child);
if (hasCaptures)
{
// If we're inside a loop, push the current crawl position onto the stack,
// so that each iteration tracks its own value. Otherwise, store it into a local.
isInLoop = rm.Analysis.IsInLoop(node);
if (isInLoop)
{
EmitStackPush(stackCookie, "base.Crawlpos()");
}
else
{
capturePos = ReserveName($"{variablePrefix}_capture_pos");
additionalDeclarations.Add($"int {capturePos} = 0;");
writer.WriteLine($"{capturePos} = base.Crawlpos();");
}
}
// Emit the child.
if (rm.Analysis.MayBacktrack(child))
{
// Lookarounds are implicitly atomic, so we need to emit the node as atomic if it might backtrack.
EmitAtomic(node, null);
}
else
{
EmitNode(child);
}
// If the generated code ends up here, it matched the lookaround, which actually
// means failure for a _negative_ lookaround, so we need to jump to the original done.
writer.WriteLine();
if (hasCaptures && isInLoop)
{
// Pop the crawl position from the stack.
writer.WriteLine("stackpos--;");
EmitStackCookieValidate(stackCookie);
}
Goto(originalDoneLabel);
writer.WriteLine();
// Failures (success for a negative lookaround) jump here.
MarkLabel(negativeLookaroundDoneLabel, emitSemicolon: false);
// After the child completes in failure (success for negative lookaround), reset the text positions.
writer.WriteLine($"pos = {startingPos};");
SliceInputSpan();
sliceStaticPos = startingSliceStaticPos;
// And uncapture anything if necessary. Negative lookaround captures don't persist beyond the lookaround.
if (hasCaptures)
{
if (isInLoop)
{
EmitUncaptureUntil(StackPop());
EmitStackCookieValidate(stackCookie);
}
else
{
EmitUncaptureUntil(capturePos!);
}
}
doneLabel = originalDoneLabel;
}
// Emits the code for the node.
void EmitNode(RegexNode node, RegexNode? subsequent = null, bool emitLengthChecksIfRequired = true)
{
// Before we handle general-purpose matching logic for nodes, handle any special-casing.
if (rm.Tree.FindOptimizations.FindMode == FindNextStartingPositionMode.LiteralAfterLoop_LeftToRight &&
rm.Tree.FindOptimizations.LiteralAfterLoop?.LoopNode == node)
{
// This is the set loop that's part of the literal-after-loop optimization: the end of the loop
// is stored in runtrackpos, so we just need to transfer that to pos. The optimization is only
// selected if the shape of the tree is amenable.
Debug.Assert(sliceStaticPos == 0, "This should be the first node and thus static position shouldn't have advanced.");
writer.WriteLine("// Skip loop already matched in TryFindNextPossibleStartingPosition.");
writer.WriteLine("pos = base.runtrackpos;");
SliceInputSpan();
return;
}
if (!StackHelper.TryEnsureSufficientExecutionStack())
{
StackHelper.CallOnEmptyStack(EmitNode, node, subsequent, emitLengthChecksIfRequired);
return;
}
if ((node.Options & RegexOptions.RightToLeft) != 0)
{
// RightToLeft doesn't take advantage of static positions. While RightToLeft won't update static
// positions, a previous operation may have left us with a non-zero one. Make sure it's zero'd out
// such that pos and slice are up-to-date. Note that RightToLeft also shouldn't use the slice span,
// as it's not kept up-to-date; any RightToLeft implementation that wants to use it must first update
// it from pos.
TransferSliceStaticPosToPos();
}
// Separate out several node types that, for conciseness, don't need a header nor scope written into the source.
// Effectively these either evaporate, are completely self-explanatory, or only exist for their children to be rendered.
switch (node.Kind)
{
// Nothing is written for an empty.
case RegexNodeKind.Empty:
return;
// A single-line goto for a failure doesn't need a scope or comment.
case RegexNodeKind.Nothing:
Goto(doneLabel);
return;
// Skip atomic nodes that wrap non-backtracking children; in such a case there's nothing to be made atomic.
case RegexNodeKind.Atomic when !rm.Analysis.MayBacktrack(node.Child(0)):
EmitNode(node.Child(0));
return;
// Concatenate is a simplification in the node tree so that a series of children can be represented as one.
// We don't need its presence visible in the source.
case RegexNodeKind.Concatenate:
EmitConcatenation(node, subsequent, emitLengthChecksIfRequired);
return;
}
// For everything else, output a comment about what the node is.
writer.WriteLine($"// {DescribeNode(node, rm)}");
// Separate out several node types that, for conciseness, don't need a scope written into the source as they're
// always a single statement / block.
switch (node.Kind)
{
case RegexNodeKind.Beginning:
case RegexNodeKind.Start:
case RegexNodeKind.Bol:
case RegexNodeKind.Eol:
case RegexNodeKind.End:
case RegexNodeKind.EndZ:
EmitAnchors(node);
return;
case RegexNodeKind.Boundary:
case RegexNodeKind.NonBoundary:
case RegexNodeKind.ECMABoundary:
case RegexNodeKind.NonECMABoundary:
EmitBoundary(node);
return;
case RegexNodeKind.One:
case RegexNodeKind.Notone:
case RegexNodeKind.Set:
EmitSingleChar(node, emitLengthChecksIfRequired);
return;
case RegexNodeKind.Multi when (node.Options & RegexOptions.RightToLeft) == 0:
EmitMultiChar(node, emitLengthChecksIfRequired);
return;
case RegexNodeKind.UpdateBumpalong:
EmitUpdateBumpalong(node);
return;
}
// For everything else, put the node's code into its own scope, purely for readability. 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 (EmitBlock(writer, null, faux: rm.Analysis.MayBacktrack(node)))
{
switch (node.Kind)
{
case RegexNodeKind.Multi:
EmitMultiChar(node, emitLengthChecksIfRequired);
return;
case RegexNodeKind.Oneloop:
case RegexNodeKind.Notoneloop:
case RegexNodeKind.Setloop:
EmitSingleCharLoop(node, subsequent, emitLengthChecksIfRequired);
return;
case RegexNodeKind.Onelazy:
case RegexNodeKind.Notonelazy:
case RegexNodeKind.Setlazy:
EmitSingleCharLazy(node, subsequent, emitLengthChecksIfRequired);
return;
case RegexNodeKind.Oneloopatomic:
case RegexNodeKind.Notoneloopatomic:
case RegexNodeKind.Setloopatomic:
EmitSingleCharAtomicLoop(node, emitLengthChecksIfRequired);
return;
case RegexNodeKind.Loop:
EmitLoop(node);
return;
case RegexNodeKind.Lazyloop:
EmitLazy(node);
return;
case RegexNodeKind.Alternate:
EmitAlternation(node);
return;
case RegexNodeKind.Backreference:
EmitBackreference(node);
return;
case RegexNodeKind.BackreferenceConditional:
EmitBackreferenceConditional(node);
return;
case RegexNodeKind.ExpressionConditional:
EmitExpressionConditional(node);
return;
case RegexNodeKind.Atomic:
Debug.Assert(rm.Analysis.MayBacktrack(node.Child(0)));
EmitAtomic(node, subsequent);
return;
case RegexNodeKind.Capture:
EmitCapture(node, subsequent);
return;
case RegexNodeKind.PositiveLookaround:
EmitPositiveLookaroundAssertion(node);
return;
case RegexNodeKind.NegativeLookaround:
EmitNegativeLookaroundAssertion(node);
return;
}
}
// All nodes should have been handled.
Debug.Fail($"Unexpected node type: {node.Kind}");
}
// Emits the node for an atomic.
void EmitAtomic(RegexNode node, RegexNode? subsequent)
{
Debug.Assert(node.Kind is RegexNodeKind.Atomic or RegexNodeKind.PositiveLookaround or RegexNodeKind.NegativeLookaround or RegexNodeKind.ExpressionConditional, $"Unexpected type: {node.Kind}");
Debug.Assert(node.Kind is RegexNodeKind.ExpressionConditional ? node.ChildCount() >= 1 : node.ChildCount() == 1, $"Unexpected number of children: {node.ChildCount()}");
Debug.Assert(rm.Analysis.MayBacktrack(node.Child(0)), "Expected child to potentially backtrack");
// Grab the current done label and the current backtracking position. The purpose of the atomic node
// is to ensure that nodes after it that might backtrack skip over the atomic, which means after
// rendering the atomic's child, we need to reset the label so that subsequent backtracking doesn't
// see any label left set by the atomic's child. We also need to reset the backtracking stack position
// so that the state on the stack remains consistent.
string originalDoneLabel = doneLabel;
additionalDeclarations.Add("int stackpos = 0;");
string startingStackpos = ReserveName("atomic_stackpos");
writer.WriteLine($"int {startingStackpos} = stackpos;");
writer.WriteLine();
// Emit the child.
EmitNode(node.Child(0), subsequent);
writer.WriteLine();
// Reset the stack position and done label.
writer.WriteLine($"stackpos = {startingStackpos};");
doneLabel = originalDoneLabel;
}
// Emits the code to handle updating base.runtextpos to pos 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(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.UpdateBumpalong, $"Unexpected type: {node.Kind}");
TransferSliceStaticPosToPos();
using (EmitBlock(writer, "if (base.runtextpos < pos)"))
{
writer.WriteLine("base.runtextpos = pos;");
}
}
// Emits code for a concatenation
void EmitConcatenation(RegexNode node, RegexNode? subsequent, bool emitLengthChecksIfRequired)
{
Debug.Assert(node.Kind is RegexNodeKind.Concatenate, $"Unexpected type: {node.Kind}");
Debug.Assert(node.ChildCount() >= 2, $"Expected at least 2 children, found {node.ChildCount()}");
// Emit the code for each child one after the other.
string? prevDescription = null;
int childCount = node.ChildCount();
for (int i = 0; i < childCount; i++)
{
// If we can find a subsequence of fixed-length children, we can emit a length check once for that sequence
// and then skip the individual length checks for each. We can also discover case-insensitive sequences that
// can be checked efficiently with methods like StartsWith. We also want to minimize the repetition of if blocks,
// and so we try to emit a series of clauses all part of the same if block rather than one if block per child.
if ((node.Options & RegexOptions.RightToLeft) == 0 &&
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 WritePrefix()
{
if (wroteClauses)
{
writer.WriteLine(prevDescription is not null ? $" || // {prevDescription}" : " ||");
writer.Write(" ");
}
else
{
writer.Write("if (");
}
}
RegexNode child = node.Child(i);
if (node.TryGetOrdinalCaseInsensitiveString(i, exclusiveEnd, out int nodesConsumed, out string? caseInsensitiveString))
{
WritePrefix();
string sourceSpan = sliceStaticPos > 0 ? $"{sliceSpan}.Slice({sliceStaticPos})" : sliceSpan;
writer.Write($"!{sourceSpan}.StartsWith({Literal(caseInsensitiveString)}, StringComparison.OrdinalIgnoreCase)");
prevDescription = $"Match the string {Literal(caseInsensitiveString)} (ordinal case-insensitive)";
wroteClauses = true;
sliceStaticPos += caseInsensitiveString.Length;
i += nodesConsumed - 1;
}
else if (child.Kind is RegexNodeKind.Multi)
{
WritePrefix();
EmitMultiCharString(child.Str!, emitLengthCheck: false, clauseOnly: true, rightToLeft: false);
prevDescription = DescribeNode(child, rm);
wroteClauses = true;
}
else if ((child.IsOneFamily || child.IsNotoneFamily || child.IsSetFamily) &&
child.M == child.N &&
child.M <= MaxUnrollSize)
{
int repeatCount = child.Kind is RegexNodeKind.One or RegexNodeKind.Notone or RegexNodeKind.Set ? 1 : child.M;
for (int c = 0; c < repeatCount; c++)
{
WritePrefix();
EmitSingleChar(child, emitLengthCheck: false, clauseOnly: true);
prevDescription = c == 0 ? DescribeNode(child, rm) : null;
wroteClauses = true;
}
}
else break;
}
if (wroteClauses)
{
writer.WriteLine(prevDescription is not null ? $") // {prevDescription}" : ")");
using (EmitBlock(writer, null))
{
Goto(doneLabel);
}
if (i < childCount)
{
writer.WriteLine();
}
wroteClauses = false;
prevDescription = null;
}
if (i < exclusiveEnd)
{
EmitNode(node.Child(i), GetSubsequentOrDefault(i, node, subsequent), emitLengthChecksIfRequired: false);
if (i < childCount - 1)
{
writer.WriteLine();
}
i++;
}
}
i--;
continue;
}
EmitNode(node.Child(i), GetSubsequentOrDefault(i, node, subsequent), emitLengthChecksIfRequired: emitLengthChecksIfRequired);
if (i < childCount - 1)
{
writer.WriteLine();
}
}
// Gets the node to treat as the subsequent one to node.Child(index)
static RegexNode? GetSubsequentOrDefault(int index, RegexNode node, RegexNode? defaultNode)
{
int childCount = node.ChildCount();
for (int i = index + 1; i < childCount; i++)
{
RegexNode next = node.Child(i);
if (next.Kind is not RegexNodeKind.UpdateBumpalong) // skip node types that don't have a semantic impact
{
return next;
}
}
return defaultNode;
}
}
// Emits the code to handle a single-character match.
void EmitSingleChar(RegexNode node, bool emitLengthCheck = true, string? offset = null, bool clauseOnly = false)
{
Debug.Assert(node.IsOneFamily || node.IsNotoneFamily || node.IsSetFamily, $"Unexpected type: {node.Kind}");
bool rtl = (node.Options & RegexOptions.RightToLeft) != 0;
Debug.Assert(!rtl || offset is null);
Debug.Assert(!rtl || !clauseOnly);
string expr = !rtl ?
$"{sliceSpan}[{Sum(sliceStaticPos, offset)}]" :
"inputSpan[pos - 1]";
expr = node.IsSetFamily ?
MatchCharacterClass(expr, node.Str!, negate: true, additionalDeclarations, requiredHelpers) :
$"{expr} {(node.IsOneFamily ? "!=" : "==")} {Literal(node.Ch)}";
if (clauseOnly)
{
writer.Write(expr);
}
else
{
string clause =
!emitLengthCheck ? $"if ({expr})" :
!rtl ? $"if ({SpanLengthCheck(1, offset)} || {expr})" :
$"if ((uint)(pos - 1) >= inputSpan.Length || {expr})";
using (EmitBlock(writer, clause))
{
Goto(doneLabel);
}
}
if (!rtl)
{
sliceStaticPos++;
}
else
{
writer.WriteLine("pos--;");
}
}
// Emits the code to handle a boundary check on a character.
void EmitBoundary(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Boundary or RegexNodeKind.NonBoundary or RegexNodeKind.ECMABoundary or RegexNodeKind.NonECMABoundary, $"Unexpected kind: {node.Kind}");
string call;
if (node.Kind is RegexNodeKind.Boundary or RegexNodeKind.NonBoundary)
{
call = node.Kind is RegexNodeKind.Boundary ?
$"!{HelpersTypeName}.IsBoundary" :
$"{HelpersTypeName}.IsBoundary";
AddIsBoundaryHelper(requiredHelpers, checkOverflow);
}
else
{
call = node.Kind is RegexNodeKind.ECMABoundary ?
$"!{HelpersTypeName}.IsECMABoundary" :
$"{HelpersTypeName}.IsECMABoundary";
AddIsECMABoundaryHelper(requiredHelpers, checkOverflow);
}
using (EmitBlock(writer, $"if ({call}(inputSpan, pos{(sliceStaticPos > 0 ? $" + {sliceStaticPos}" : "")}))"))
{
Goto(doneLabel);
}
}
// Emits the code to handle various anchors.
void EmitAnchors(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Beginning or RegexNodeKind.Start or RegexNodeKind.Bol or RegexNodeKind.End or RegexNodeKind.EndZ or RegexNodeKind.Eol, $"Unexpected type: {node.Kind}");
Debug.Assert((node.Options & RegexOptions.RightToLeft) == 0 || sliceStaticPos == 0);
Debug.Assert(sliceStaticPos >= 0);
switch (node.Kind)
{
case RegexNodeKind.Beginning:
case RegexNodeKind.Start:
if (sliceStaticPos > 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.Kind == RegexNodeKind.Beginning ?
"if (pos != 0)" :
"if (pos != base.runtextstart)"))
{
Goto(doneLabel);
}
}
break;
case RegexNodeKind.Bol:
using (EmitBlock(writer, sliceStaticPos > 0 ?
$"if ({sliceSpan}[{sliceStaticPos - 1}] != '\\n')" :
$"if (pos > 0 && inputSpan[pos - 1] != '\\n')"))
{
Goto(doneLabel);
}
break;
case RegexNodeKind.End:
using (EmitBlock(writer, sliceStaticPos > 0 ?
$"if ({sliceStaticPos} < {sliceSpan}.Length)" :
"if ((uint)pos < (uint)inputSpan.Length)"))
{
Goto(doneLabel);
}
break;
case RegexNodeKind.EndZ:
using (EmitBlock(writer, sliceStaticPos > 0 ?
$"if ({sliceStaticPos + 1} < {sliceSpan}.Length || ({sliceStaticPos} < {sliceSpan}.Length && {sliceSpan}[{sliceStaticPos}] != '\\n'))" :
"if (pos < inputSpan.Length - 1 || ((uint)pos < (uint)inputSpan.Length && inputSpan[pos] != '\\n'))"))
{
Goto(doneLabel);
}
break;
case RegexNodeKind.Eol:
using (EmitBlock(writer, sliceStaticPos > 0 ?
$"if ({sliceStaticPos} < {sliceSpan}.Length && {sliceSpan}[{sliceStaticPos}] != '\\n')" :
"if ((uint)pos < (uint)inputSpan.Length && inputSpan[pos] != '\\n')"))
{
Goto(doneLabel);
}
break;
}
}
// Emits the code to handle a multiple-character match.
void EmitMultiChar(RegexNode node, bool emitLengthCheck)
{
Debug.Assert(node.Kind is RegexNodeKind.Multi, $"Unexpected type: {node.Kind}");
Debug.Assert(node.Str is not null);
EmitMultiCharString(node.Str, emitLengthCheck, clauseOnly: false, (node.Options & RegexOptions.RightToLeft) != 0);
}
void EmitMultiCharString(string str, bool emitLengthCheck, bool clauseOnly, bool rightToLeft)
{
Debug.Assert(str.Length >= 2);
Debug.Assert(!clauseOnly || (!emitLengthCheck && !rightToLeft));
if (rightToLeft)
{
Debug.Assert(emitLengthCheck);
using (EmitBlock(writer, $"if ((uint)(pos - {str.Length}) >= inputSpan.Length)"))
{
Goto(doneLabel);
}
writer.WriteLine();
using (EmitBlock(writer, $"for (int i = 0; i < {str.Length}; i++)"))
{
using (EmitBlock(writer, $"if (inputSpan[--pos] != {Literal(str)}[{str.Length - 1} - i])"))
{
Goto(doneLabel);
}
}
return;
}
string sourceSpan = sliceStaticPos > 0 ? $"{sliceSpan}.Slice({sliceStaticPos})" : sliceSpan;
string clause = $"!{sourceSpan}.StartsWith({Literal(str)})";
if (clauseOnly)
{
writer.Write(clause);
}
else
{
using (EmitBlock(writer, $"if ({clause})"))
{
Goto(doneLabel);
}
}
sliceStaticPos += str.Length;
}
void EmitSingleCharLoop(RegexNode node, RegexNode? subsequent = null, bool emitLengthChecksIfRequired = true)
{
Debug.Assert(node.Kind is RegexNodeKind.Oneloop or RegexNodeKind.Notoneloop or RegexNodeKind.Setloop, $"Unexpected type: {node.Kind}");
// If this is actually atomic based on its parent, emit it as atomic instead; no backtracking necessary.
if (rm.Analysis.IsAtomicByAncestor(node))
{
EmitSingleCharAtomicLoop(node);
return;
}
// If this is actually a repeater, emit that instead; no backtracking necessary.
if (node.M == node.N)
{
EmitSingleCharRepeater(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) and that there's nothing captured by the loop.
Debug.Assert(node.M < node.N);
string backtrackingLabel = ReserveName("CharLoopBacktrack");
string endLoop = ReserveName("CharLoopEnd");
string startingPos = ReserveName("charloop_starting_pos");
string endingPos = ReserveName("charloop_ending_pos");
additionalDeclarations.Add($"int {startingPos} = 0, {endingPos} = 0;");
bool rtl = (node.Options & RegexOptions.RightToLeft) != 0;
bool isInLoop = rm.Analysis.IsInLoop(node);
// We're about to enter a loop, so ensure our text position is 0.
TransferSliceStaticPosToPos();
// 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($"{startingPos} = pos;");
writer.WriteLine();
EmitSingleCharAtomicLoop(node);
writer.WriteLine();
TransferSliceStaticPosToPos();
writer.WriteLine($"{endingPos} = pos;");
EmitAdd(writer, startingPos, !rtl ? node.M : -node.M);
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, emitSemicolon: false);
int stackCookie = CreateStackCookie();
string? capturePos = null;
if (isInLoop)
{
// This loop is inside of another loop, which means we persist state
// on the backtracking stack rather than relying on locals to always
// hold the right state (if we didn't do that, another iteration of the
// outer loop could have resulted in the locals being overwritten).
// Pop the relevant state from the stack.
if (expressionHasCaptures)
{
EmitUncaptureUntil(StackPop());
}
EmitStackPop(stackCookie, endingPos, startingPos);
}
else if (expressionHasCaptures)
{
// Since we're not in a loop, we're using a local to track the crawl position.
// Unwind back to the position we were at prior to running the code after this loop.
capturePos = ReserveName("charloop_capture_pos");
additionalDeclarations.Add($"int {capturePos} = 0;");
EmitUncaptureUntil(capturePos);
}
writer.WriteLine();
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
if (!rtl &&
node.N > 1 && // no point in using IndexOf for small loops, in particular optionals
subsequent?.FindStartingLiteralNode() is RegexNode literalNode &&
TryEmitIndexOf(requiredHelpers, literalNode, useLast: true, negate: false, out int literalLength, out string? indexOfExpr))
{
writer.WriteLine($"if ({startingPos} >= {endingPos} ||");
string setEndingPosCondition = $" ({endingPos} = inputSpan.Slice({startingPos}, ";
setEndingPosCondition = literalLength > 1 ?
$"{setEndingPosCondition}Math.Min(inputSpan.Length, {endingPos} + {literalLength - 1}) - {startingPos})" :
$"{setEndingPosCondition}{endingPos} - {startingPos})";
using (EmitBlock(writer, $"{setEndingPosCondition}.{indexOfExpr}) < 0)"))
{
Goto(doneLabel);
}
writer.WriteLine($"{endingPos} += {startingPos};");
writer.WriteLine($"pos = {endingPos};");
}
else
{
using (EmitBlock(writer, $"if ({startingPos} {(!rtl ? ">=" : "<=")} {endingPos})"))
{
Goto(doneLabel);
}
writer.WriteLine(!rtl ? $"pos = --{endingPos};" : $"pos = ++{endingPos};");
}
if (!rtl)
{
SliceInputSpan();
}
writer.WriteLine();
MarkLabel(endLoop, emitSemicolon: false);
if (isInLoop)
{
// We're in a loop and thus can't rely on locals correctly holding the state we
// need (the locals could be overwritten by a subsequent iteration). Push the state
// on to the backtracking stack.
EmitStackPush(stackCookie, expressionHasCaptures ?
[startingPos, endingPos, "base.Crawlpos()"] :
[startingPos, endingPos]);
}
else if (capturePos is not null)
{
// We're not in a loop and so can trust our locals. Store the current capture position
// into the capture position local; we'll uncapture back to this when backtracking to
// remove any captures from after this loop that we need to throw away.
writer.WriteLine($"{capturePos} = base.Crawlpos();");
}
doneLabel = backtrackingLabel; // leave set to the backtracking label for all subsequent nodes
}
void EmitSingleCharLazy(RegexNode node, RegexNode? subsequent = null, bool emitLengthChecksIfRequired = true)
{
Debug.Assert(node.Kind is RegexNodeKind.Onelazy or RegexNodeKind.Notonelazy or RegexNodeKind.Setlazy, $"Unexpected type: {node.Kind}");
// Emit the min iterations as a repeater. Any failures here don't necessitate backtracking,
// as the lazy itself failed to match, and there's no backtracking possible by the individual
// characters/iterations themselves.
if (node.M > 0)
{
EmitSingleCharRepeater(node, emitLengthChecksIfRequired);
}
// 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 || rm.Analysis.IsAtomicByAncestor(node))
{
return;
}
if (node.M > 0)
{
// We emitted a repeater to handle the required iterations; add a newline after it.
writer.WriteLine();
}
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.
TransferSliceStaticPosToPos();
// 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)
{
maxIterations = $"{node.N - node.M}";
iterationCount = ReserveName("lazyloop_iteration");
additionalDeclarations.Add($"int {iterationCount} = 0;");
writer.WriteLine($"{iterationCount} = 0;");
}
// Track the current crawl position. Upon backtracking, we'll unwind any captures beyond this point.
string? capturePos = null;
if (expressionHasCaptures)
{
capturePos = ReserveName("lazyloop_capturepos");
additionalDeclarations.Add($"int {capturePos} = 0;");
}
// Track the current pos. 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 startingPos = ReserveName("lazyloop_pos");
additionalDeclarations.Add($"int {startingPos} = 0;");
writer.WriteLine($"{startingPos} = pos;");
// 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 = ReserveName("LazyLoopEnd");
Goto(endLoopLabel);
writer.WriteLine();
// Backtracking section. Subsequent failures will jump to here.
string backtrackingLabel = ReserveName("LazyLoopBacktrack");
MarkLabel(backtrackingLabel, emitSemicolon: false);
// 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 (capturePos is not null)
{
EmitUncaptureUntil(capturePos);
}
// 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})"))
{
Goto(doneLabel);
}
writer.WriteLine($"{iterationCount}++;");
}
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
// Now match the next item in the lazy loop. We need to reset the pos 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($"pos = {startingPos};");
SliceInputSpan();
EmitSingleChar(node);
TransferSliceStaticPosToPos();
// Now that we've appropriately advanced by one character and are set for what comes after the loop,
// see if we can skip ahead more iterations by doing a search for a following literal.
if ((node.Options & RegexOptions.RightToLeft) == 0)
{
if (iterationCount is null &&
node.Kind is RegexNodeKind.Notonelazy &&
subsequent?.FindStartingLiteral() is RegexNode.StartingLiteralData literal &&
!literal.Negated && // not negated; can't search for both the node.Ch and a negated subsequent char with an IndexOf* method
(literal.String is not null ||
literal.SetChars is not null ||
literal.Range.LowInclusive == literal.Range.HighInclusive ||
(literal.Range.LowInclusive <= node.Ch && node.Ch <= literal.Range.HighInclusive))) // for ranges, only allow when the range overlaps with the target, since there's no accelerated way to search for the union
{
// e.g. "<[^>]*?>"
// Whether the not'd character matches the subsequent literal. This impacts whether we need to search
// for both or just the literal, as well as what assumptions we can make once a match is found.
bool overlap;
// This lazy loop will consume all characters other than node.Ch until the subsequent literal.
// We can implement it to search for either that char or the literal, whichever comes first.
if (literal.String is not null) // string literal
{
overlap = literal.String[0] == node.Ch;
writer.WriteLine(overlap ?
$"{startingPos} = {sliceSpan}.IndexOf({Literal(node.Ch)});" :
$"{startingPos} = {sliceSpan}.IndexOfAny({Literal(node.Ch)}, {Literal(literal.String[0])});");
}
else if (literal.SetChars is not null) // set literal
{
overlap = literal.SetChars.Contains(node.Ch);
writer.WriteLine((overlap, literal.SetChars.Length) switch
{
(true, 2) => $"{startingPos} = {sliceSpan}.IndexOfAny({Literal(literal.SetChars[0])}, {Literal(literal.SetChars[1])});",
(true, 3) => $"{startingPos} = {sliceSpan}.IndexOfAny({Literal(literal.SetChars[0])}, {Literal(literal.SetChars[1])}, {Literal(literal.SetChars[2])});",
(true, _) => $"{startingPos} = {sliceSpan}.IndexOfAny({EmitSearchValuesOrLiteral(literal.SetChars.AsSpan(), requiredHelpers)});",
(false, 2) => $"{startingPos} = {sliceSpan}.IndexOfAny({Literal(node.Ch)}, {Literal(literal.SetChars[0])}, {Literal(literal.SetChars[1])});",
(false, _) => $"{startingPos} = {sliceSpan}.IndexOfAny({EmitSearchValuesOrLiteral($"{node.Ch}{literal.SetChars}".AsSpan(), requiredHelpers)});",
});
}
else if (literal.Range.LowInclusive == literal.Range.HighInclusive) // single char from a RegexNode.One
{
overlap = literal.Range.LowInclusive == node.Ch;
writer.WriteLine(overlap ?
$"{startingPos} = {sliceSpan}.IndexOf({Literal(node.Ch)});" :
$"{startingPos} = {sliceSpan}.IndexOfAny({Literal(node.Ch)}, {Literal(literal.Range.LowInclusive)});");
}
else // char range
{
overlap = true;
writer.WriteLine($"{startingPos} = {sliceSpan}.IndexOfAnyInRange({Literal(literal.Range.LowInclusive)}, {Literal(literal.Range.HighInclusive)});");
}
// If the search didn't find anything, fail the match. If it did find something, then we need to consider whether
// that something is the loop character. If it's not, we've successfully backtracked to the next lazy location
// where we should evaluate the rest of the pattern. If it does match, then we need to consider whether there's
// overlap between the loop character and the literal. If there is overlap, this is also a place to check. But
// if there's not overlap, and if the found character is the loop character, we also want to fail the match here
// and now, as this means the loop ends before it gets to what needs to come after the loop, and thus the pattern
// can't possibly match here.
using (EmitBlock(writer, overlap ?
$"if ({startingPos} < 0)" :
$"if ((uint){startingPos} >= (uint){sliceSpan}.Length || {sliceSpan}[{startingPos}] == {Literal(node.Ch)})"))
{
Goto(doneLabel);
}
writer.WriteLine($"pos += {startingPos};");
SliceInputSpan();
}
else if (iterationCount is null &&
node.Kind is RegexNodeKind.Setlazy &&
node.Str == RegexCharClass.AnyClass &&
subsequent?.FindStartingLiteralNode() is RegexNode literal2 &&
TryEmitIndexOf(requiredHelpers, literal2, useLast: false, negate: false, out _, out string? indexOfExpr))
{
// e.g. ".*?string" with RegexOptions.Singleline
// This lazy loop will consume all characters until the subsequent literal. If the subsequent literal
// isn't found, the loop fails. We can implement it to just search for that literal.
writer.WriteLine($"{startingPos} = {sliceSpan}.{indexOfExpr};");
using (EmitBlock(writer, $"if ({startingPos} < 0)"))
{
Goto(doneLabel);
}
writer.WriteLine($"pos += {startingPos};");
SliceInputSpan();
}
}
// Store the position we've left off at in case we need to iterate again.
writer.WriteLine($"{startingPos} = pos;");
// 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();
bool isInLoop = rm.Analysis.IsInLoop(node);
MarkLabel(endLoopLabel, emitSemicolon: !(capturePos is not null || isInLoop));
if (capturePos is not null)
{
writer.WriteLine($"{capturePos} = base.Crawlpos();");
}
// If this loop is itself not in another loop, nothing more needs to be done:
// upon backtracking, locals being used by this loop will have retained their
// values and be up-to-date. But if this loop is inside another loop, multiple
// iterations of this loop each need their own state, so we need to use the stack
// to hold it, and we need a dedicated backtracking section to handle restoring
// that state before jumping back into the loop itself.
if (isInLoop)
{
writer.WriteLine();
int stackCookie = CreateStackCookie();
// Store the loop's state.
EmitStackPush(stackCookie,
capturePos is not null && iterationCount is not null ? [startingPos, capturePos, iterationCount] :
capturePos is not null ? [startingPos, capturePos] :
iterationCount is not null ? [startingPos, iterationCount] :
[startingPos]);
// Skip past the backtracking section.
string end = ReserveName("LazyLoopSkipBacktrack");
Goto(end);
writer.WriteLine();
// Emit a backtracking section that restores the loop's state and then jumps to the previous done label.
string backtrack = ReserveName("CharLazyBacktrack");
MarkLabel(backtrack, emitSemicolon: false);
// Restore the loop's state.
EmitStackPop(stackCookie,
capturePos is not null && iterationCount is not null ? [iterationCount, capturePos, startingPos] :
capturePos is not null ? [capturePos, startingPos] :
iterationCount is not null ? [iterationCount, startingPos] :
[startingPos]);
Goto(doneLabel);
writer.WriteLine();
doneLabel = backtrack;
MarkLabel(end);
}
}
void EmitLazy(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Lazyloop, $"Unexpected type: {node.Kind}");
Debug.Assert(node.M < int.MaxValue, $"Unexpected M={node.M}");
Debug.Assert(node.N >= node.M, $"Unexpected M={node.M}, N={node.N}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
RegexNode child = node.Child(0);
int minIterations = node.M;
int maxIterations = node.N;
string originalDoneLabel = doneLabel;
// If this is actually a repeater, reuse the loop implementation, as a loop and a lazy loop
// both need to greedily consume up to their min iteration count and are identical in
// behavior when min == max.
if (minIterations == maxIterations)
{
EmitLoop(node);
return;
}
// We should only be here if the lazy loop isn't atomic due to an ancestor, as the optimizer should
// in such a case have lowered the loop's upper bound to its lower bound, at which point it would
// have been handled by the above delegation to EmitLoop. However, if the optimizer missed doing so,
// this loop could still be considered atomic by ancestor by its parent nodes, in which case we want
// to make sure the code emitted here conforms (e.g. doesn't leave any state erroneously on the stack).
// So, we assert it's not atomic, but still handle that case.
bool isAtomic = rm.Analysis.IsAtomicByAncestor(node);
Debug.Assert(!isAtomic, "An atomic lazy should have had its upper bound lowered to its lower bound.");
// We might loop any number of times. In order to ensure this loop and subsequent code sees sliceStaticPos
// the same regardless, we always need it to contain the same value, and the easiest such value is 0.
// So, we transfer sliceStaticPos to pos, and ensure that any path out of here has sliceStaticPos as 0.
TransferSliceStaticPosToPos();
string body = ReserveName("LazyLoopBody");
string endLoop = ReserveName("LazyLoopEnd");
string iterationCount = ReserveName("lazyloop_iteration");
additionalDeclarations.Add($"int {iterationCount} = 0;");
writer.WriteLine($"{iterationCount} = 0;");
// Loops that match empty iterations need additional checks in place to prevent infinitely matching (since
// you could end up looping an infinite number of times at the same location). We can avoid those
// additional checks if we can prove that the loop can never match empty, which we can do by computing
// the minimum length of the child; only if it's 0 might iterations be empty.
bool iterationMayBeEmpty = child.ComputeMinLength() == 0;
string? startingPos = null, sawEmpty = null;
if (iterationMayBeEmpty)
{
startingPos = ReserveName("lazyloop_starting_pos");
sawEmpty = ReserveName("lazyloop_empty_seen");
writer.WriteLine($"int {startingPos} = pos, {sawEmpty} = 0; // the lazy loop may match empty iterations");
}
// If the min count is 0, start out by jumping right to what's after the loop. Backtracking
// will then bring us back in to do further iterations.
if (minIterations == 0)
{
Goto(endLoop);
}
writer.WriteLine();
// Iteration body
MarkLabel(body, emitSemicolon: isAtomic);
// In case iterations are backtracked through and unwound, we need to store the current position (so that
// matching can resume from that location), the current crawl position if captures are possible (so that
// we can uncapture back to that position), and both the starting position from the iteration we're leaving
// and whether we've seen an empty iteration (if iterations may be empty). Since there can be multiple
// iterations, this state needs to be stored on to the backtracking stack.
if (!isAtomic)
{
int stackCookie = CreateStackCookie();
int entriesPerIteration =
1/*pos*/ +
(iterationMayBeEmpty ? 2/*startingPos+sawEmpty*/ : 0) +
(expressionHasCaptures ? 1/*Crawlpos*/ : 0) +
(stackCookie != 0 ? 1 : 0);
EmitStackPush(stackCookie,
expressionHasCaptures && iterationMayBeEmpty ? ["pos", startingPos!, sawEmpty!, "base.Crawlpos()"] :
iterationMayBeEmpty ? ["pos", startingPos!, sawEmpty!] :
expressionHasCaptures ? ["pos", "base.Crawlpos()"] :
["pos"]);
if (iterationMayBeEmpty)
{
// We need to store the current pos so we can compare it against pos after the iteration, in order to
// determine whether the iteration was empty.
writer.WriteLine($"{startingPos} = pos;");
}
// Proactively increase the number of iterations. We do this prior to the match rather than once
// we know it's successful, because we need to decrement it as part of a failed match when
// backtracking; it's thus simpler to just always decrement it as part of a failed match, even
// when initially greedily matching the loop, which then requires we increment it before trying.
writer.WriteLine($"{iterationCount}++;");
// Last but not least, we need to set the doneLabel that a failed match of the body will jump to.
// Such an iteration match failure may or may not fail the whole operation, depending on whether
// we've already matched the minimum required iterations, so we need to jump to a location that
// will make that determination.
string iterationFailedLabel = ReserveName("LazyLoopIterationNoMatch");
doneLabel = iterationFailedLabel;
// Finally, emit the child.
Debug.Assert(sliceStaticPos == 0);
writer.WriteLine();
EmitNode(child);
writer.WriteLine();
TransferSliceStaticPosToPos(); // ensure sliceStaticPos remains 0
if (doneLabel == iterationFailedLabel)
{
doneLabel = originalDoneLabel;
}
// Loop condition. Continue iterating if we've not yet reached the minimum. We just successfully
// matched an iteration, so the only reason we'd need to forcefully loop around again is if the
// minimum were at least 2.
if (minIterations >= 2)
{
writer.WriteLine($"// The lazy loop requires a minimum of {minIterations} iterations. If that many haven't yet matched, loop now.");
using (EmitBlock(writer, $"if ({CountIsLessThan(iterationCount, minIterations)})"))
{
Goto(body);
}
}
if (iterationMayBeEmpty)
{
// If the last iteration was empty, we need to prevent further iteration from this point
// unless we backtrack out of this iteration.
writer.WriteLine("// If the iteration successfully matched zero-length input, record that an empty iteration was seen.");
using (EmitBlock(writer, $"if (pos == {startingPos})"))
{
writer.WriteLine($"{sawEmpty} = 1; // true");
}
writer.WriteLine();
}
// We matched the next iteration. Jump to the subsequent code.
Goto(endLoop);
writer.WriteLine();
// Now handle what happens when an iteration fails (and since a lazy loop only executes an iteration
// when it's required to satisfy the loop by definition of being lazy, the loop is failing). We need
// to reset state to what it was before just that iteration started. That includes resetting pos and
// clearing out any captures from that iteration.
writer.WriteLine("// The lazy loop iteration failed to match.");
MarkLabel(iterationFailedLabel, emitSemicolon: false);
if (doneLabel != originalDoneLabel || !GotoWillExitMatch(originalDoneLabel)) // we don't need to back anything out if we're about to exit TryMatchAtCurrentPosition anyway.
{
// Fail this loop iteration, including popping state off the backtracking stack that was pushed
// on as part of the failing iteration.
writer.WriteLine($"{iterationCount}--;");
if (expressionHasCaptures)
{
EmitUncaptureUntil(StackPop());
}
EmitStackPop(stackCookie, iterationMayBeEmpty ?
[sawEmpty!, startingPos!, "pos"] :
["pos"]);
SliceInputSpan();
// If the loop's child doesn't backtrack, then this loop has failed.
// If the loop's child does backtrack, we need to backtrack back into the previous iteration if there was one.
if (doneLabel == originalDoneLabel)
{
// Since the only reason we'd end up revisiting previous iterations of the lazy loop is if the child had backtracking constructs
// we'd backtrack into, and the child doesn't, the whole loop is failed and done. If we successfully processed any iterations,
// we thus need to pop all of the state we pushed onto the stack for those iterations, as we're exiting out to the parent who
// will expect the stack to be cleared of any child state.
Debug.Assert(entriesPerIteration >= 1);
writer.WriteLine(entriesPerIteration > 1 ?
$"stackpos -= {iterationCount} * {entriesPerIteration};" :
$"stackpos -= {iterationCount};");
}
else
{
// The child has backtracking constructs. If we have no successful iterations previously processed, just bail.
// If we do have successful iterations previously processed, however, we need to backtrack back into the last one.
using (EmitBlock(writer, $"if ({iterationCount} > 0)"))
{
writer.WriteLine($"// The lazy loop matched at least one iteration; backtrack into the last one.");
if (iterationMayBeEmpty)
{
// If we saw empty, it must have been in the most recent iteration, as we wouldn't have
// allowed additional iterations after one that was empty. Thus, we reset it back to
// false prior to backtracking / undoing that iteration.
writer.WriteLine($"{sawEmpty} = 0; // false");
}
Goto(doneLabel);
}
writer.WriteLine();
}
}
Goto(originalDoneLabel);
writer.WriteLine();
MarkLabel(endLoop, emitSemicolon: false);
// If the lazy loop is not atomic, then subsequent code may backtrack back into this lazy loop, either
// causing it to add additional iterations, or backtracking into existing iterations and potentially
// unwinding them. We need to do a timeout check, and then determine whether to branch back to add more
// iterations (if we haven't hit the loop's maximum iteration count and haven't seen an empty iteration)
// or unwind by branching back to the last backtracking location. Either way, we need a dedicated
// backtracking section that a subsequent construct will see as its backtracking target.
// We need to ensure that some state (e.g. iteration count) is persisted if we're backtracked to.
// We also need to push the current position, so that subsequent iterations pick up at the right
// point (and subsequent expressions are almost certain to have changed the current pos). However,
// if we're not inside of a loop, the other local's used for this construct are sufficient, as nothing
// else will overwrite them between now and when backtracking occurs. If, however, we are inside
// of another loop, then any number of iterations might have such state that needs to be stored,
// and thus it needs to be pushed on to the backtracking stack.
bool isInLoop = rm.Analysis.IsInLoop(node);
stackCookie = CreateStackCookie();
EmitStackPush(stackCookie,
!isInLoop ? (expressionHasCaptures ? ["pos", "base.Crawlpos()"] : ["pos"]) :
iterationMayBeEmpty ? (expressionHasCaptures ? ["pos", iterationCount, startingPos!, sawEmpty!, "base.Crawlpos()"] : ["pos", iterationCount, startingPos!, sawEmpty!]) :
expressionHasCaptures ? ["pos", iterationCount, "base.Crawlpos()"] :
["pos", iterationCount]);
string skipBacktrack = ReserveName("LazyLoopSkipBacktrack");
Goto(skipBacktrack);
writer.WriteLine();
// Emit a backtracking section that checks the timeout, restores the loop's state, and jumps to
// the appropriate label.
string backtrack = ReserveName($"LazyLoopBacktrack");
MarkLabel(backtrack, emitSemicolon: false);
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
if (expressionHasCaptures)
{
EmitUncaptureUntil(StackPop());
}
EmitStackPop(stackCookie,
!isInLoop ? ["pos"] :
iterationMayBeEmpty ? [sawEmpty!, startingPos!, iterationCount, "pos"] :
[iterationCount, "pos"]);
SliceInputSpan();
// Determine where to branch, either back to the lazy loop body to add an additional iteration,
// or to the last backtracking label.
if (maxIterations != int.MaxValue || iterationMayBeEmpty)
{
FinishEmitBlock clause;
writer.WriteLine();
if (maxIterations == int.MaxValue)
{
// If the last iteration matched empty, backtrack.
writer.WriteLine("// If the last iteration matched empty, don't continue lazily iterating. Instead, backtrack.");
clause = EmitBlock(writer, $"if ({sawEmpty} != 0)");
}
else if (iterationMayBeEmpty)
{
// If the last iteration matched empty or if we've reached our upper bound, backtrack.
writer.WriteLine($"// If the upper bound {maxIterations} has already been reached, or if the last");
writer.WriteLine($"// iteration matched empty, don't continue lazily iterating. Instead, backtrack.");
clause = EmitBlock(writer, $"if ({CountIsGreaterThanOrEqualTo(iterationCount, maxIterations)} || {sawEmpty} != 0)");
}
else
{
// If we've reached our upper bound, backtrack.
writer.WriteLine($"// If the upper bound {maxIterations} has already been reached,");
writer.WriteLine($"// don't continue lazily iterating. Instead, backtrack.");
clause = EmitBlock(writer, $"if ({CountIsGreaterThanOrEqualTo(iterationCount, maxIterations)})");
}
using (clause)
{
// We're backtracking, which could either be to something prior to the lazy loop or to something
// inside of the lazy loop. If it's to something inside of the lazy loop, then either the loop
// will eventually succeed or we'll eventually end up unwinding back through the iterations all
// the way back to the loop not matching at all, in which case the state we first pushed on at the
// beginning of the !isAtomic section will get popped off. But if here we're instead going to jump
// to something prior to the lazy loop, then we need to pop off that state here.
if (doneLabel == originalDoneLabel)
{
EmitAdd(writer, "stackpos", -entriesPerIteration);
}
if (iterationMayBeEmpty)
{
// If we saw empty, it must have been in the most recent iteration, as we wouldn't have
// allowed additional iterations after one that was empty. Thus, we reset it back to
// false prior to backtracking / undoing that iteration.
writer.WriteLine($"{sawEmpty} = 0; // false");
}
Goto(doneLabel);
}
}
// Otherwise, try to match another iteration.
Goto(body);
writer.WriteLine();
doneLabel = backtrack;
MarkLabel(skipBacktrack);
}
}
// 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), as this
// might be used to implement the required iterations of other kinds of loops.
void EmitSingleCharRepeater(RegexNode node, bool emitLengthCheck = true)
{
Debug.Assert(node.IsOneFamily || node.IsNotoneFamily || node.IsSetFamily, $"Unexpected type: {node.Kind}");
int iterations = node.M;
bool rtl = (node.Options & RegexOptions.RightToLeft) != 0;
switch (iterations)
{
case 0:
// No iterations, nothing to do.
return;
case 1:
// Just match the individual item
EmitSingleChar(node, emitLengthCheck);
return;
case <= RegexNode.MultiVsRepeaterLimit when node.IsOneFamily:
// This is a repeated case-sensitive character; emit it as a multi in order to get all the optimizations
// afforded to a multi, e.g. unrolling the loop with multi-char reads/comparisons at a time.
EmitMultiCharString(new string(node.Ch, iterations), emitLengthCheck, clauseOnly: false, rtl);
return;
}
if (rtl)
{
TransferSliceStaticPosToPos(); // we don't use static position with rtl
using (EmitBlock(writer, $"for (int i = 0; i < {iterations}; i++)"))
{
EmitSingleChar(node);
}
}
else if (node.IsSetFamily && node.Str == RegexCharClass.AnyClass)
{
// This is a repeater for anything, which means we only care about length and can jump past that length.
if (emitLengthCheck)
{
EmitSpanLengthCheck(iterations);
}
sliceStaticPos += iterations;
}
else if (iterations <= MaxUnrollSize)
{
// if ((uint)(sliceStaticPos + iterations - 1) >= (uint)slice.Length ||
// slice[sliceStaticPos] != c1 ||
// slice[sliceStaticPos + 1] != c2 ||
// ...)
// {
// goto doneLabel;
// }
writer.Write($"if (");
if (emitLengthCheck)
{
writer.WriteLine($"{SpanLengthCheck(iterations)} ||");
writer.Write(" ");
}
EmitSingleChar(node, emitLengthCheck: false, clauseOnly: true);
for (int i = 1; i < iterations; i++)
{
writer.WriteLine(" ||");
writer.Write(" ");
EmitSingleChar(node, emitLengthCheck: false, clauseOnly: true);
}
writer.WriteLine(")");
using (EmitBlock(writer, null))
{
Goto(doneLabel);
}
}
else
{
// if ((uint)(sliceStaticPos + iterations - 1) >= (uint)slice.Length) goto doneLabel;
if (emitLengthCheck)
{
EmitSpanLengthCheck(iterations);
writer.WriteLine();
}
// If we're able to vectorize the search, do so. Otherwise, fall back to a loop.
// For the loop, we're validating that each char matches the target node.
// For IndexOf, we're looking for the first thing that _doesn't_ match the target node,
// and thus similarly validating that everything does.
if (TryEmitIndexOf(requiredHelpers, node, useLast: false, negate: true, out _, out string? indexOfExpr))
{
using (EmitBlock(writer, $"if ({sliceSpan}.Slice({sliceStaticPos}, {iterations}).{indexOfExpr} >= 0)"))
{
Goto(doneLabel);
}
}
else
{
string repeaterSpan = "repeaterSlice"; // As this repeater doesn't wrap arbitrary node emits, this shouldn't conflict with anything
writer.WriteLine($"ReadOnlySpan<char> {repeaterSpan} = {sliceSpan}.Slice({sliceStaticPos}, {iterations});");
using (EmitBlock(writer, $"for (int i = 0; i < {repeaterSpan}.Length; i++)"))
{
string tmpTextSpanLocal = sliceSpan; // we want EmitSingleChar to refer to this temporary
int tmpSliceStaticPos = sliceStaticPos;
sliceSpan = repeaterSpan;
sliceStaticPos = 0;
EmitSingleChar(node, emitLengthCheck: false, offset: "i");
sliceSpan = tmpTextSpanLocal;
sliceStaticPos = tmpSliceStaticPos;
}
}
sliceStaticPos += iterations;
}
}
// Emits the code to handle a non-backtracking, variable-length loop around a single character comparison.
void EmitSingleCharAtomicLoop(RegexNode node, bool emitLengthChecksIfRequired = true)
{
Debug.Assert(node.Kind is RegexNodeKind.Oneloop or RegexNodeKind.Oneloopatomic or RegexNodeKind.Notoneloop or RegexNodeKind.Notoneloopatomic or RegexNodeKind.Setloop or RegexNodeKind.Setloopatomic, $"Unexpected type: {node.Kind}");
// If this is actually a repeater, emit that instead.
if (node.M == node.N)
{
EmitSingleCharRepeater(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;
bool rtl = (node.Options & RegexOptions.RightToLeft) != 0;
string iterationLocal = ReserveName("iteration");
if (rtl)
{
TransferSliceStaticPosToPos(); // we don't use static position for rtl
if (node.IsSetFamily && maxIterations == int.MaxValue && node.Str == RegexCharClass.AnyClass)
{
// If this loop will consume the remainder of the input, just set the iteration variable
// to pos directly rather than looping to get there.
writer.WriteLine($"int {iterationLocal} = pos;");
}
else
{
writer.WriteLine($"int {iterationLocal} = 0;");
string expr = $"inputSpan[pos - {iterationLocal} - 1]";
expr = node.IsSetFamily ?
MatchCharacterClass(expr, node.Str!, negate: false, additionalDeclarations, requiredHelpers) :
$"{expr} {(node.IsOneFamily ? "==" : "!=")} {Literal(node.Ch)}";
string maxClause = maxIterations != int.MaxValue ? $"{CountIsLessThan(iterationLocal, maxIterations)} && " : "";
using (EmitBlock(writer, $"while ({maxClause}pos > {iterationLocal} && {expr})"))
{
writer.WriteLine($"{iterationLocal}++;");
}
writer.WriteLine();
}
}
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.
TransferSliceStaticPosToPos();
writer.WriteLine($"int {iterationLocal} = inputSpan.Length - pos;");
}
else if (TryEmitIndexOf(requiredHelpers, node, useLast: false, negate: true, out _, out string? indexOfExpr))
{
// We can use an IndexOf method to perform the search. If the number of iterations is unbounded, we can just search the whole span.
// If, however, it's bounded, we need to slice the span to the min(remainingSpan.Length, maxIterations) so that we don't
// search more than is necessary.
// If maxIterations is 0, the node should have been optimized away. If it's 1 and min is 0, it should
// have been handled as an optional loop above, and if it's 1 and min is 1, it should have been transformed
// into a single char match. So, we should only be here if maxIterations is greater than 1. And that's relevant,
// because we wouldn't want to invest in an IndexOf call if we're only going to iterate once.
Debug.Assert(maxIterations > 1);
TransferSliceStaticPosToPos();
writer.Write($"int {iterationLocal} = {sliceSpan}");
if (maxIterations != int.MaxValue)
{
writer.Write($".Slice(0, Math.Min({sliceSpan}.Length, {maxIterations}))");
}
writer.WriteLine($".{indexOfExpr};");
using (EmitBlock(writer, $"if ({iterationLocal} < 0)"))
{
writer.WriteLine(maxIterations != int.MaxValue ?
$"{iterationLocal} = Math.Min({sliceSpan}.Length, {maxIterations});" :
$"{iterationLocal} = {sliceSpan}.Length;");
}
writer.WriteLine();
}
else
{
// For everything else, do a normal loop.
string expr = $"{sliceSpan}[{iterationLocal}]";
expr = node.IsSetFamily ?
MatchCharacterClass(expr, node.Str!, negate: false, additionalDeclarations, requiredHelpers) :
$"{expr} {(node.IsOneFamily ? "==" : "!=")} {Literal(node.Ch)}";
if (minIterations != 0 || maxIterations != int.MaxValue)
{
// For any loops other than * loops, transfer text pos to pos in
// order to zero it out to be able to use the single iteration variable
// for both iteration count and indexer.
TransferSliceStaticPosToPos();
}
writer.WriteLine($"int {iterationLocal} = {sliceStaticPos};");
sliceStaticPos = 0;
string maxClause = maxIterations != int.MaxValue ? $"{CountIsLessThan(iterationLocal, maxIterations)} && " : "";
using (EmitBlock(writer, $"while ({maxClause}(uint){iterationLocal} < (uint){sliceSpan}.Length && {expr})"))
{
writer.WriteLine($"{iterationLocal}++;");
}
writer.WriteLine();
}
// Check to ensure we've found at least min iterations.
if (minIterations > 0)
{
using (EmitBlock(writer, $"if ({CountIsLessThan(iterationLocal, minIterations)})"))
{
Goto(doneLabel);
}
writer.WriteLine();
}
// Now that we've completed our optional iterations, advance the text span
// and pos by the number of iterations completed.
if (!rtl)
{
writer.WriteLine($"{sliceSpan} = {sliceSpan}.Slice({iterationLocal});");
writer.WriteLine($"pos += {iterationLocal};");
}
else
{
writer.WriteLine($"pos -= {iterationLocal};");
}
}
// Emits the code to handle a non-backtracking optional zero-or-one loop.
void EmitAtomicSingleCharZeroOrOne(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Oneloop or RegexNodeKind.Oneloopatomic or RegexNodeKind.Notoneloop or RegexNodeKind.Notoneloopatomic or RegexNodeKind.Setloop or RegexNodeKind.Setloopatomic, $"Unexpected type: {node.Kind}");
Debug.Assert(node.M == 0 && node.N == 1);
bool rtl = (node.Options & RegexOptions.RightToLeft) != 0;
if (rtl)
{
TransferSliceStaticPosToPos(); // we don't use static pos for rtl
}
string expr = !rtl ?
$"{sliceSpan}[{sliceStaticPos}]" :
"inputSpan[pos - 1]";
expr = node.IsSetFamily ?
MatchCharacterClass(expr, node.Str!, negate: false, additionalDeclarations, requiredHelpers) :
$"{expr} {(node.IsOneFamily ? "==" : "!=")} {Literal(node.Ch)}";
string spaceAvailable =
rtl ? "pos > 0" :
sliceStaticPos != 0 ? $"(uint){sliceSpan}.Length > (uint){sliceStaticPos}" :
$"!{sliceSpan}.IsEmpty";
using (EmitBlock(writer, $"if ({spaceAvailable} && {expr})"))
{
if (!rtl)
{
writer.WriteLine($"{sliceSpan} = {sliceSpan}.Slice(1);");
writer.WriteLine($"pos++;");
}
else
{
writer.WriteLine($"pos--;");
}
}
}
void EmitNonBacktrackingRepeater(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Loop or RegexNodeKind.Lazyloop, $"Unexpected type: {node.Kind}");
Debug.Assert(node.M < int.MaxValue, $"Unexpected M={node.M}");
Debug.Assert(node.M == node.N, $"Unexpected M={node.M} == N={node.N}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
Debug.Assert(!rm.Analysis.MayBacktrack(node.Child(0)), $"Expected non-backtracking node {node.Kind}");
// Ensure every iteration of the loop sees a consistent value.
TransferSliceStaticPosToPos();
// Loop M==N times to match the child exactly that numbers of times.
string i = ReserveName("loop_iteration");
using (EmitBlock(writer, $"for (int {i} = 0; {i} < {node.M}; {i}++)"))
{
EmitNode(node.Child(0));
TransferSliceStaticPosToPos(); // make sure static the static position remains at 0 for subsequent constructs
}
}
void EmitLoop(RegexNode node)
{
Debug.Assert(node.Kind is RegexNodeKind.Loop or RegexNodeKind.Lazyloop, $"Unexpected type: {node.Kind}");
Debug.Assert(node.M < int.MaxValue, $"Unexpected M={node.M}");
Debug.Assert(node.N >= node.M, $"Unexpected M={node.M}, N={node.N}");
Debug.Assert(node.ChildCount() == 1, $"Expected 1 child, found {node.ChildCount()}");
RegexNode child = node.Child(0);
int minIterations = node.M;
int maxIterations = node.N;
int stackCookie = CreateStackCookie();
// Special-case some repeaters.
if (minIterations == maxIterations)
{
switch (minIterations)
{
case 0:
// No iteration. Nop.
return;
case 1:
// One iteration. Just emit the child without any loop ceremony.
EmitNode(child);
return;
case > 1 when !rm.Analysis.MayBacktrack(child):
// The child doesn't backtrack. Emit it as a non-backtracking repeater.
// (If the child backtracks, we need to fall through to the more general logic
// that supports unwinding iterations.)
EmitNonBacktrackingRepeater(node);
return;
}
}
// We might loop any number of times. In order to ensure this loop and subsequent code sees sliceStaticPos
// the same regardless, we always need it to contain the same value, and the easiest such value is 0.
// So, we transfer sliceStaticPos to pos, and ensure that any path out of here has sliceStaticPos as 0.
TransferSliceStaticPosToPos();
bool isAtomic = rm.Analysis.IsAtomicByAncestor(node);
string? startingStackpos = null;
if (isAtomic || minIterations > 1)
{
// If the loop is atomic, constructs will need to backtrack around it, and as such any backtracking
// state pushed by the loop should be removed prior to exiting the loop. Similarly, if the loop has
// a minimum iteration count greater than 1, we might end up with at least one successful iteration
// only to find we can't iterate further, and will need to clear any pushed state from the backtracking
// stack. For both cases, we need to store the starting stack index so it can be reset to that position.
startingStackpos = ReserveName("startingStackpos");
additionalDeclarations.Add($"int {startingStackpos} = 0;");
writer.WriteLine($"{startingStackpos} = stackpos;");
}
string originalDoneLabel = doneLabel;
string body = ReserveName("LoopBody");
string endLoop = ReserveName("LoopEnd");
string iterationCount = ReserveName("loop_iteration");
// Loops that match empty iterations need additional checks in place to prevent infinitely matching (since
// you could end up looping an infinite number of times at the same location). We can avoid those
// additional checks if we can prove that the loop can never match empty, which we can do by computing
// the minimum length of the child; only if it's 0 might iterations be empty.
bool iterationMayBeEmpty = child.ComputeMinLength() == 0;
string? startingPos = iterationMayBeEmpty ? ReserveName("loop_starting_pos") : null;
if (iterationMayBeEmpty)
{
additionalDeclarations.Add($"int {iterationCount} = 0, {startingPos} = 0;");
writer.WriteLine($"{startingPos} = pos;");
}
else
{
additionalDeclarations.Add($"int {iterationCount} = 0;");
}
writer.WriteLine($"{iterationCount} = 0;");
writer.WriteLine();
// Iteration body
MarkLabel(body, emitSemicolon: false);
// We need to store the starting pos and crawl position so that it may be backtracked through later.
// This needs to be the starting position from the iteration we're leaving, so it's pushed before updating
// it to pos. Note that unlike some other constructs that only need to push state on to the stack if
// they're inside of a loop (because if they're not inside of a loop, nothing would overwrite the locals),
// here we still need the stack, because each iteration of _this_ loop may have its own state, e.g. we
// need to know where each iteration began so when backtracking we can jump back to that location. This is
// true even if the loop is atomic, as we might need to backtrack within the loop in order to match the
// minimum iteration count.
EmitStackPush(stackCookie,
expressionHasCaptures && iterationMayBeEmpty ? ["base.Crawlpos()", startingPos!, "pos"] :
expressionHasCaptures ? ["base.Crawlpos()", "pos"] :
iterationMayBeEmpty ? [startingPos!, "pos"] :
["pos"]);
writer.WriteLine();
// Save off some state. We need to store the current pos so we can compare it against
// pos after the iteration, in order to determine whether the iteration was empty. Empty
// iterations are allowed as part of min matches, but once we've met the min quote, empty matches
// are considered match failures.
if (iterationMayBeEmpty)
{
writer.WriteLine($"{startingPos} = pos;");
}
// Proactively increase the number of iterations. We do this prior to the match rather than once
// we know it's successful, because we need to decrement it as part of a failed match when
// backtracking; it's thus simpler to just always decrement it as part of a failed match, even
// when initially greedily matching the loop, which then requires we increment it before trying.
writer.WriteLine($"{iterationCount}++;");
writer.WriteLine();
// Last but not least, we need to set the doneLabel that a failed match of the body will jump to.
// Such an iteration match failure may or may not fail the whole operation, depending on whether
// we've already matched the minimum required iterations, so we need to jump to a location that
// will make that determination.
string iterationFailedLabel = ReserveName("LoopIterationNoMatch");
doneLabel = iterationFailedLabel;
// Finally, emit the child.
Debug.Assert(sliceStaticPos == 0);
EmitNode(child);
writer.WriteLine();
TransferSliceStaticPosToPos(); // ensure sliceStaticPos remains 0
bool childBacktracks = doneLabel != iterationFailedLabel;
// Loop condition. Continue iterating greedily if we've not yet reached the maximum. We also need to stop
// iterating if the iteration matched empty and we already hit the minimum number of iterations.
writer.WriteLine();
if (maxIterations == int.MaxValue && !iterationMayBeEmpty)
{
// The loop has no upper bound and iterations can't be empty; this is a greedy loop, so regardless of whether
// there's a min iterations required, we need to loop again.
writer.WriteLine("// The loop has no upper bound. Continue iterating greedily.");
Goto(body);
}
else
{
FinishEmitBlock clause;
if (!iterationMayBeEmpty)
{
// Iterations won't be empty, but there is an upper bound. Whether or not there's a min iterations required, we need to keep
// iterating until we're at the maximum, and since the min is never more than the max, we don't need to check the min.
writer.WriteLine($"// The loop has an upper bound of {maxIterations}. Continue iterating greedily if it hasn't yet been reached.");
clause = EmitBlock(writer, $"if ({CountIsLessThan(iterationCount, maxIterations)})");
}
else if (minIterations > 0 && maxIterations == int.MaxValue)
{
// Iterations may be empty, and there's a minimum iteration count required (but no maximum), so loop if either
// the iteration isn't empty or we still need more iterations to meet the minimum.
writer.WriteLine($"// The loop has a lower bound of {minIterations} but no upper bound. Continue iterating greedily");
writer.WriteLine($"// if the last iteration wasn't empty (or if it was, if the lower bound hasn't yet been reached).");
clause = EmitBlock(writer, $"if (pos != {startingPos} || {CountIsLessThan(iterationCount, minIterations)})");
}
else if (minIterations > 0)
{
// Iterations may be empty and there's both a lower and upper bound on the loop.
writer.WriteLine($"// The loop has a lower bound of {minIterations} and an upper bound of {maxIterations}. Continue iterating");
writer.WriteLine($"// greedily if the upper bound hasn't yet been reached and either the last iteration was non-empty or the");
writer.WriteLine($"// lower bound hasn't yet been reached.");
clause = EmitBlock(writer, $"if ((pos != {startingPos} || {CountIsLessThan(iterationCount, minIterations)}) && {CountIsLessThan(iterationCount, maxIterations)})");
}
else if (maxIterations == int.MaxValue)
{
// Iterations may be empty and there's no lower or upper bound.
writer.WriteLine($"// The loop is unbounded. Continue iterating greedily as long as the last iteration wasn't empty.");
clause = EmitBlock(writer, $"if (pos != {startingPos})");
}
else
{
// Iterations may be empty, there's no lower bound, but there is an upper bound.
writer.WriteLine($"// The loop has an upper bound of {maxIterations}. Continue iterating greedily if the upper bound hasn't");
writer.WriteLine($"// yet been reached (as long as the last iteration wasn't empty).");
clause = EmitBlock(writer, $"if (pos != {startingPos} && {CountIsLessThan(iterationCount, maxIterations)})");
}
using (clause)
{
Goto(body);
}
Goto(endLoop);
}
// We've matched as many iterations as we can with this configuration. Jump to what comes after the loop.
writer.WriteLine();
// Now handle what happens when an iteration fails, which could be an initial failure or it
// could be while backtracking. We need to reset state to what it was before just that iteration
// started. That includes resetting pos and clearing out any captures from that iteration.
writer.WriteLine("// The loop iteration failed. Put state back to the way it was before the iteration.");
MarkLabel(iterationFailedLabel, emitSemicolon: false);
using (EmitBlock(writer, $"if (--{iterationCount} < 0)"))
{
// If the loop has a lower bound of 0, then we may try to match what comes after the loop
// having matched 0 iterations. If that fails, it'll then backtrack here, and the iteration
// count will become negative, indicating the loop has exhausted its choices.
writer.WriteLine("// Unable to match the remainder of the expression after exhausting the loop.");
Goto(originalDoneLabel);
}
EmitStackPop(0, iterationMayBeEmpty ? // stack cookie handled is explicitly 0 to handle it below
["pos", startingPos!] :
["pos"]);
if (expressionHasCaptures)
{
EmitUncaptureUntil(StackPop());
}
EmitStackCookieValidate(stackCookie);
SliceInputSpan();
// If there's a required minimum iteration count, validate now that we've processed enough iterations.
if (minIterations > 0)
{
if (childBacktracks)
{
// The child backtracks. If we don't have any iterations, there's nothing to backtrack into,
// and at least one iteration is required, so fail the loop.
using (EmitBlock(writer, $"if ({iterationCount} == 0)"))
{
writer.WriteLine("// No iterations have been matched to backtrack into. Fail the loop.");
Goto(originalDoneLabel);
}
writer.WriteLine();
// We have at least one iteration; if that's insufficient to meet the minimum, backtrack
// into the previous iteration. We only need to do this check if the min iteration requirement
// is more than one, since the above check already handles the case where the min count is 1,
// since the only value that wouldn't meet that is 0.
if (minIterations > 1)
{
using (EmitBlock(writer, $"if ({CountIsLessThan(iterationCount, minIterations)})"))
{
writer.WriteLine($"// All possible iterations have matched, but it's below the required minimum of {minIterations}.");
writer.WriteLine($"// Backtrack into the prior iteration.");
Goto(doneLabel);
}
writer.WriteLine();
}
}
else
{
// The child doesn't backtrack, which means there's no other way the matched iterations could
// match differently, so if we haven't already greedily processed enough iterations, fail the loop.
using (EmitBlock(writer, $"if ({CountIsLessThan(iterationCount, minIterations)})"))
{
writer.WriteLine($"// All possible iterations have matched, but it's below the required minimum of {minIterations}. Fail the loop.");
// If the minimum iterations is 1, then since we're only here if there are fewer, there must be 0
// iterations, in which case there's nothing to reset. If, however, the minimum iteration count is
// greater than 1, we need to check if there was at least one successful iteration, in which case
// any backtracking state still set needs to be reset; otherwise, constructs earlier in the sequence
// trying to pop their own state will erroneously pop this state instead.
if (minIterations > 1)
{
Debug.Assert(startingStackpos is not null);
using (EmitBlock(writer, $"if ({iterationCount} != 0)"))
{
writer.WriteLine($"// Ensure any stale backtracking state is removed.");
writer.WriteLine($"stackpos = {startingStackpos};");
}
}
Goto(originalDoneLabel);
}
writer.WriteLine();
}
}
if (isAtomic)
{
doneLabel = originalDoneLabel;
MarkLabel(endLoop, emitSemicolon: startingStackpos is null);
// The loop is atomic, which means any backtracking will go around this loop. That also means we can't leave
// stack polluted with state from successful iterations, so we need to remove all such state; such state will
// only have been pushed if minIterations > 0.
if (startingStackpos is not null)
{
writer.WriteLine($"stackpos = {startingStackpos}; // Ensure any remaining backtracking state is removed.");
}
}
else
{
if (childBacktracks)
{
Goto(endLoop);
writer.WriteLine();
string backtrack = ReserveName("LoopBacktrack");
MarkLabel(backtrack, emitSemicolon: false);
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
using (EmitBlock(writer, $"if ({iterationCount} == 0)"))
{
writer.WriteLine("// No iterations of the loop remain to backtrack into. Fail the loop.");
Goto(originalDoneLabel);
}
Goto(doneLabel);
doneLabel = backtrack;
}
bool isInLoop = rm.Analysis.IsInLoop(node);
MarkLabel(endLoop, emitSemicolon: !isInLoop);
// If this loop is itself not in another loop, nothing more needs to be done:
// upon backtracking, locals being used by this loop will have retained their
// values and be up-to-date. But if this loop is inside another loop, multiple
// iterations of this loop each need their own state, so we need to use the stack
// to hold it, and we need a dedicated backtracking section to handle restoring
// that state before jumping back into the loop itself.
if (isInLoop)
{
writer.WriteLine();
// Store the loop's state
stackCookie = CreateStackCookie();
EmitStackPush(stackCookie,
startingPos is not null && startingStackpos is not null ? [startingPos, startingStackpos, iterationCount] :
startingPos is not null ? [startingPos, iterationCount] :
startingStackpos is not null ? [startingStackpos, iterationCount] :
[iterationCount]);
// Skip past the backtracking section
string end = ReserveName("LoopSkipBacktrack");
Goto(end);
writer.WriteLine();
// Emit a backtracking section that restores the loop's state and then jumps to the previous done label
string backtrack = ReserveName("LoopBacktrack");
MarkLabel(backtrack, emitSemicolon: false);
EmitStackPop(stackCookie,
startingPos is not null && startingStackpos is not null ? [iterationCount, startingStackpos, startingPos] :
startingPos is not null ? [iterationCount, startingPos] :
startingStackpos is not null ? [iterationCount, startingStackpos] :
[iterationCount]);
// We're backtracking. Check the timeout.
EmitTimeoutCheckIfNeeded(writer, rm);
Goto(doneLabel);
writer.WriteLine();
doneLabel = backtrack;
MarkLabel(end);
}
}
}
// Gets a comparison for whether the iteration count is less than the upper bound.
static string CountIsLessThan(string count, int exclusiveUpper) =>
exclusiveUpper == 1 ? $"{count} == 0" : $"{count} < {exclusiveUpper}";
// Gets a comparison for whether the iteration count is greater than or equal to the upper bound
static string CountIsGreaterThanOrEqualTo(string count, int exclusiveUpper) =>
exclusiveUpper == 1 ? $"{count} != 0" : $"{count} >= {exclusiveUpper}";
// Emits code to unwind the capture stack until the crawl position specified in the provided local.
void EmitUncaptureUntil(string capturepos)
{
const string UncaptureUntil = nameof(UncaptureUntil);
if (!additionalLocalFunctions.ContainsKey(UncaptureUntil))
{
additionalLocalFunctions.Add(UncaptureUntil,
[
$"// <summary>Undo captures until it reaches the specified capture position.</summary>",
$"[MethodImpl(MethodImplOptions.AggressiveInlining)]",
$"void {UncaptureUntil}(int capturePosition)",
$"{{",
$" while (base.Crawlpos() > capturePosition)",
$" {{",
$" base.Uncapture();",
$" }}",
$"}}",
]);
}
writer.WriteLine($"{UncaptureUntil}({capturepos});");
}
/// <summary>Pushes values on to the backtracking stack.</summary>
void EmitStackPush(int stackCookie, params string[] args)
{
Debug.Assert(args.Length is >= 1);
const string MethodName = "StackPush";
string key = $"{MethodName}{args.Length}";
additionalDeclarations.Add("int stackpos = 0;");
if (!requiredHelpers.ContainsKey(key))
{
var lines = new string[24 + args.Length];
lines[0] = $"/// <summary>Pushes {args.Length} value{(args.Length == 1 ? "" : "s")} onto the backtracking stack.</summary>";
lines[1] = $"[MethodImpl(MethodImplOptions.AggressiveInlining)]";
lines[2] = $"internal static void {MethodName}(ref int[] stack, ref int pos{FormatN(", int arg{0}", args.Length)})";
lines[3] = $"{{";
lines[4] = $" // If there's space available for {(args.Length > 1 ? $"all {args.Length} values, store them" : "the value, store it")}.";
lines[5] = $" int[] s = stack;";
lines[6] = $" int p = pos;";
lines[7] = $" if ((uint){(args.Length > 1 ? $"(p + {args.Length - 1})" : "p")} < (uint)s.Length)";
lines[8] = $" {{";
for (int i = 0; i < args.Length; i++)
{
lines[9 + i] = $" s[p{(i == 0 ? "" : $" + {i}")}] = arg{i};";
}
lines[9 + args.Length] = args.Length > 1 ? $" pos += {args.Length};" : " pos++;";
lines[10 + args.Length] = $" return;";
lines[11 + args.Length] = $" }}";
lines[12 + args.Length] = $"";
lines[13 + args.Length] = $" // Otherwise, resize the stack to make room and try again.";
lines[14 + args.Length] = $" WithResize(ref stack, ref pos{FormatN(", arg{0}", args.Length)});";
lines[15 + args.Length] = $"";
lines[16 + args.Length] = $" // <summary>Resize the backtracking stack array and push {args.Length} value{(args.Length == 1 ? "" : "s")} onto the stack.</summary>";
lines[17 + args.Length] = $" [MethodImpl(MethodImplOptions.NoInlining)]";
lines[18 + args.Length] = $" static void WithResize(ref int[] stack, ref int pos{FormatN(", int arg{0}", args.Length)})";
lines[19 + args.Length] = $" {{";
lines[20 + args.Length] = $" Array.Resize(ref stack, (pos + {args.Length - 1}) * 2);";
lines[21 + args.Length] = $" {MethodName}(ref stack, ref pos{FormatN(", arg{0}", args.Length)});";
lines[22 + args.Length] = $" }}";
lines[23 + args.Length] = $"}}";
requiredHelpers.Add(key, lines);
}
if (stackCookie != 0)
{
EmitStackCookie(stackCookie);
}
writer.WriteLine($"{HelpersTypeName}.{MethodName}(ref base.runstack!, ref stackpos, {string.Join(", ", args)});");
}
/// <summary>Pops values from the backtracking stack into the specified locations.</summary>
void EmitStackPop(int stackCookie, params string[] args)
{
Debug.Assert(args.Length is >= 1);
if (args.Length == 1)
{
writer.WriteLine($"{args[0]} = {StackPop()};");
}
else
{
const string MethodName = "StackPop";
string key = $"{MethodName}{args.Length}";
if (!requiredHelpers.ContainsKey(key))
{
var lines = new string[5 + args.Length];
lines[0] = $"/// <summary>Pops {args.Length} value{(args.Length == 1 ? "" : "s")} from the backtracking stack.</summary>";
lines[1] = $"[MethodImpl(MethodImplOptions.AggressiveInlining)]";
lines[2] = $"internal static void {MethodName}(int[] stack, ref int pos{FormatN(", out int arg{0}", args.Length)})";
lines[3] = $"{{";
for (int i = 0; i < args.Length; i++)
{
lines[4 + i] = $" arg{i} = stack[--pos];";
}
lines[4 + args.Length] = $"}}";
requiredHelpers.Add(key, lines);
}
writer.WriteLine($"{HelpersTypeName}.{MethodName}(base.runstack!, ref stackpos, out {string.Join(", out ", args)});");
}
if (stackCookie != 0)
{
EmitStackCookieValidate(stackCookie);
}
}
/// <summary>Initializes a debug stack cookie for a new backtracking stack push.</summary>
int CreateStackCookie() =>
#if DEBUG
#pragma warning disable RS1035 // Random is banned from generators due to non-determinism, but this Random is seeded with a constant and it's only for debug builds
stackCookieGenerator.Next() + 1;
#pragma warning restore RS1035
#else
0;
#endif
/// <summary>Emits a debug stack cookie for a new backtracking stack push.</summary>
void EmitStackCookie(int stackCookie)
{
#if DEBUG
EmitStackPush(0, stackCookie.ToString());
#endif
}
/// <summary>Emits validation for a debug stack cookie.</summary>
void EmitStackCookieValidate(int stackCookie)
{
#if DEBUG
writer.WriteLine($"{StackCookieValidate(stackCookie)};");
#endif
}
/// <summary>
/// Returns an expression that:
/// In debug, pops item 1 from the backtracking stack, pops item 2 and validates it against the cookie, then evaluates to item1.
/// In release, pops and evaluates to an item from the backtracking stack.
/// </summary>
string ValidateStackCookieWithAdditionAndReturnPoppedStack(int stackCookie)
{
#if DEBUG
const string MethodName = "ValidateStackCookieWithAdditionAndReturnPoppedStack";
if (!requiredHelpers.ContainsKey(MethodName))
{
requiredHelpers.Add(MethodName,
[
$"/// <summary>Validates that a stack cookie popped off the backtracking stack holds the expected value. Debug only.</summary>",
$"internal static int {MethodName}(int poppedStack, int expectedCookie, int actualCookie)",
$"{{",
$" expectedCookie += poppedStack;",
$" if (expectedCookie != actualCookie)",
$" {{",
$" throw new Exception($\"Backtracking stack imbalance detected. Expected {{expectedCookie}}. Actual {{actualCookie}}.\");",
$" }}",
$" return poppedStack;",
$"}}",
]);
}
return $"{HelpersTypeName}.{MethodName}({StackPop()}, {stackCookie}, {StackPop()})";
#else
return StackPop();
#endif
}
#if DEBUG
/// <summary>Returns an expression that validates and returns a debug stack cookie.</summary>
string StackCookieValidate(int stackCookie)
{
const string MethodName = "ValidateStackCookie";
if (!requiredHelpers.ContainsKey(MethodName))
{
requiredHelpers.Add(MethodName,
[
$"/// <summary>Validates that a stack cookie popped off the backtracking stack holds the expected value. Debug only.</summary>",
$"internal static int {MethodName}(int expected, int actual)",
$"{{",
$" if (expected != actual)",
$" {{",
$" throw new Exception($\"Backtracking stack imbalance detected. Expected {{expected}}. Actual {{actual}}.\");",
$" }}",
$" return actual;",
$"}}",
]);
}
return $"{HelpersTypeName}.{MethodName}({stackCookie}, {StackPop()})";
}
#endif
/// <summary>Expression for popping the next item from the backtracking stack.</summary>
string StackPop() => "base.runstack![--stackpos]";
/// <summary>Concatenates the strings resulting from formatting the format string with the values [0, count).</summary>
static string FormatN(string format, int count) =>
string.Concat(from i in Enumerable.Range(0, count)
select string.Format(format, i));
}