95new RegexNode(Kind, Options, Str!) : 96new RegexNode(Kind, Options, Ch); 121return new RegexNode(RegexNodeKind.One, options & ~RegexOptions.IgnoreCase, ch); 127return new RegexNode(RegexNodeKind.Set, options & ~RegexOptions.IgnoreCase, stringSet); 131return new RegexNode(RegexNodeKind.One, options, ch); 388parent.InsertChild(1, new RegexNode(RegexNodeKind.UpdateBumpalong, node.Options)); 456var atomic = new RegexNode(RegexNodeKind.Atomic, existingChild.Options); 5630 => new RegexNode(Kind == RegexNodeKind.Alternate ? RegexNodeKind.Nothing : RegexNodeKind.Empty, Options), 654return new RegexNode(RegexNodeKind.Empty, child.Options); 837return new RegexNode(RegexNodeKind.Nothing, Options); 930return new RegexNode(RegexNodeKind.Nothing, Options); 1139var newAlternate = new RegexNode(RegexNodeKind.Alternate, alternation.Options); 1149var atomic = new RegexNode(RegexNodeKind.Atomic, alternation.Options); 1156var newConcat = new RegexNode(RegexNodeKind.Concatenate, alternation.Options); 1309var newAlternate = new RegexNode(RegexNodeKind.Alternate, startingNodeOptions); 1353var atomic = new RegexNode(RegexNodeKind.Atomic, startingNodeOptions); 1358var newConcat = new RegexNode(RegexNodeKind.Concatenate, startingNodeOptions); 1506return new RegexNode(RegexNodeKind.Empty, Options); 2003AddChild(new RegexNode(RegexNodeKind.Empty, Options)); 2021AddChild(new RegexNode(RegexNodeKind.Empty, Options)); 2679return new RegexNode(RegexNodeKind.Empty, Options); 2707var result = new RegexNode(lazy ? RegexNodeKind.Lazyloop : RegexNodeKind.Loop, Options, min, max);

277StartGroup(new RegexNode(RegexNodeKind.Capture, (_options & ~RegexOptions.IgnoreCase), 0, -1)); 347_unit = new RegexNode(RegexNodeKind.Set, _options & ~RegexOptions.IgnoreCase, setString); 394_unit = new RegexNode((_options & RegexOptions.Multiline) != 0 ? RegexNodeKind.Bol : RegexNodeKind.Beginning, _options); 398_unit = new RegexNode((_options & RegexOptions.Multiline) != 0 ? RegexNodeKind.Eol : RegexNodeKind.EndZ, _options); 403new RegexNode(RegexNodeKind.Set, _options & ~RegexOptions.IgnoreCase, RegexCharClass.AnyClass) : 404new RegexNode(RegexNodeKind.Notone, _options & ~RegexOptions.IgnoreCase, '\n'); 521_concatenation = new RegexNode(RegexNodeKind.Concatenate, _options); 759return new RegexNode(RegexNodeKind.Group, _options); 763return new RegexNode(RegexNodeKind.Capture, _options, _autocap++, -1); 937return new RegexNode(RegexNodeKind.Capture, _options, capnum, uncapnum); 959return new RegexNode(RegexNodeKind.BackreferenceConditional, _options, capnum); 973return new RegexNode(RegexNodeKind.BackreferenceConditional, _options, tmpCapnum); 1026return new RegexNode(nodeType, _options); 1091new RegexNode(TypeFromCode(ch), _options); 1096new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.ECMAWordClass : RegexCharClass.WordClass); 1101new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.NotECMAWordClass : RegexCharClass.NotWordClass); 1106new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.ECMASpaceClass : RegexCharClass.SpaceClass); 1111new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.NotECMASpaceClass : RegexCharClass.NotSpaceClass); 1116new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.ECMADigitClass : RegexCharClass.DigitClass); 1121new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), (_options & RegexOptions.ECMAScript) != 0 ? RegexCharClass.NotECMADigitClass : RegexCharClass.NotDigitClass); 1138return new RegexNode(RegexNodeKind.Set, (_options & ~RegexOptions.IgnoreCase), cc.ToStringClass()); 1203IsCaptureSlot(capnum) ? new RegexNode(RegexNodeKind.Backreference, _options, capnum) : 1235return scanOnly ? null : new RegexNode(RegexNodeKind.Backreference, _options, capnum); 1249return new RegexNode(RegexNodeKind.Backreference, _options, capnum); 1269_capnames?[capname] is int tmpCapnum ? new RegexNode(RegexNodeKind.Backreference, _options, tmpCapnum) : 1345return new RegexNode(RegexNodeKind.Backreference, _options, capnum); 1355return new RegexNode(RegexNodeKind.Backreference, _options, capnum); 1367return new RegexNode(RegexNodeKind.Backreference, _options, tmpCapnum); 1405return new RegexNode(RegexNodeKind.Backreference, _options, capnum); 2022_concatenation!.AddChild(new RegexNode(RegexNodeKind.Multi, _options & ~RegexOptions.IgnoreCase, _pattern.Substring(pos, cch))); 2068_alternation = new RegexNode(RegexNodeKind.Alternate, _options); 2069_concatenation = new RegexNode(RegexNodeKind.Concatenate, _options); 2086_concatenation = new RegexNode(RegexNodeKind.Concatenate, _options);

1244(RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal) target = _regexTree.FindOptimizations.LiteralAfterLoop.Value;

17public RegexFindOptimizations(RegexNode root, RegexOptions options) 180(RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal)? literalAfterLoop = RegexPrefixAnalyzer.FindLiteralFollowingLeadingLoop(root); 294public (RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal)? LiteralAfterLoop { get; } 761(RegexNode loopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) literal) = LiteralAfterLoop.GetValueOrDefault();

19/// <remarks>null if no children, a <see cref="RegexNode"/> if one child, or a <see cref="List{RegexNode}"/> if multiple children.</remarks> 49public RegexNode? Parent; 87public RegexNode CloneCharLoopWithOneLessIteration() 94RegexNode newNode = IsSetFamily ? 110public static RegexNode CreateOneWithCaseConversion(char ch, RegexOptions options, CultureInfo? culture, ref RegexCaseBehavior caseBehavior) 135public RegexNode ReverseConcatenationIfRightToLeft() 141((List<RegexNode>)Children!).Reverse(); 205var toExamine = new Stack<RegexNode>(); 209RegexNode node = toExamine.Pop(); 215RegexNode child = node.Child(i); 329internal RegexNode FinalOptimize() 331RegexNode rootNode = this; 369RegexNode node = rootNode.Child(0); // skip implicit root capture node 423RegexNode node = this; 452RegexNode existingChild = node.Child(node.ChildCount() - 1); 456var atomic = new RegexNode(RegexNodeKind.Atomic, existingChild.Options); 505RegexNode? loopDescendent = node.FindLastExpressionInLoopForAutoAtomic(); 522internal RegexNode Reduce() 558private RegexNode ReplaceNodeIfUnnecessary() 575private RegexNode ReduceGroup() 579RegexNode u = this; 596private RegexNode ReduceAtomic() 608RegexNode atomic = this; 609RegexNode child = Child(0); 646List<RegexNode>? branches = child.Children as List<RegexNode>; 687RegexNode startNode = branches[start]; 723RegexNode nextChild = branches[next]; 765private RegexNode ReduceLoops() 769RegexNode u = this; 777RegexNode child = u.Child(0); 846RegexNode child = u.Child(0); 873private RegexNode ReduceSet() 923private RegexNode ReduceAlternation() 937RegexNode node = ReplaceNodeIfUnnecessary(); 966RegexNode at; 967RegexNode prev; 969List<RegexNode> children = (List<RegexNode>)Children!; 981if (at.Children is List<RegexNode> atChildren) 991RegexNode atChild = (RegexNode)at.Children!; 1075static RegexNode ExtractCommonPrefixOneNotoneSet(RegexNode alternation) 1078Debug.Assert(alternation.Children is List<RegexNode> { Count: >= 2 }); 1079var children = (List<RegexNode>)alternation.Children; 1088foreach (RegexNode child in children) 1098Debug.Assert(children[startingIndex].Children is List<RegexNode> { Count: >= 2 }); 1104RegexNode required = children[startingIndex].Child(0); 1120RegexNode other = children[endingIndex].Child(0); 1139var newAlternate = new RegexNode(RegexNodeKind.Alternate, alternation.Options); 1142((List<RegexNode>)children[i].Children!).RemoveAt(0); 1147if (alternation.Parent is RegexNode { Kind: RegexNodeKind.Atomic }) 1149var atomic = new RegexNode(RegexNodeKind.Atomic, alternation.Options); 1156var newConcat = new RegexNode(RegexNodeKind.Concatenate, alternation.Options); 1170static RegexNode RemoveRedundantEmptiesAndNothings(RegexNode node) 1174var children = (List<RegexNode>)node.Children!; 1180RegexNode child = children[i]; 1213static RegexNode ExtractCommonPrefixText(RegexNode alternation) 1216Debug.Assert(alternation.Children is List<RegexNode> { Count: >= 2 }); 1217var children = (List<RegexNode>)alternation.Children; 1234RegexNode? startingNode = children[startingIndex].FindBranchOneOrMultiStart(); 1309var newAlternate = new RegexNode(RegexNodeKind.Alternate, startingNodeOptions); 1312RegexNode branch = children[i]; 1319static void ProcessOneOrMulti(RegexNode node, ReadOnlySpan<char> startingSpan) 1351if (alternation.Parent is RegexNode parent && parent.Kind == RegexNodeKind.Atomic) 1353var atomic = new RegexNode(RegexNodeKind.Atomic, startingNodeOptions); 1358var newConcat = new RegexNode(RegexNodeKind.Concatenate, startingNodeOptions); 1376public RegexNode? FindBranchOneOrMultiStart() 1378RegexNode branch = Kind == RegexNodeKind.Concatenate ? Child(0) : this; 1391public RegexNode? FindStartingLiteralNode(bool allowZeroWidth = true) 1393RegexNode? node = this; 1431if (FindStartingLiteralNode() is RegexNode node) 1498private RegexNode ReduceConcatenation() 1515RegexNode child = Child(i); 1543Debug.Assert(Children is List<RegexNode>); 1549List<RegexNode> children = (List<RegexNode>)Children!; 1552RegexNode at = children[i]; 1562if (at.Children is List<RegexNode> atChildren) 1572RegexNode atChild = (RegexNode)at.Children!; 1590RegexNode prev = children[--j]; 1626Debug.Assert(Children is List<RegexNode>); 1628var children = (List<RegexNode>)Children!; 1633RegexNode currentNode = children[current]; 1634RegexNode nextNode = children[next]; 1827Debug.Assert(Children is List<RegexNode>); 1828var children = (List<RegexNode>)Children; 1833static void ProcessNode(RegexNode node, RegexNode subsequent) 1857RegexNode? loopDescendent = node.FindLastExpressionInLoopForAutoAtomic(); 1928private RegexNode? FindLastExpressionInLoopForAutoAtomic() 1930RegexNode node = this; 1952RegexNode lastConcatChild = node.Child(concatCount - 1); 1964private RegexNode ReduceLookaround() 1992private RegexNode ReduceBackreferenceConditional() 2010private RegexNode ReduceExpressionConditional() 2029RegexNode condition = Child(0); 2048private static bool CanBeMadeAtomic(RegexNode node, RegexNode subsequent, bool iterateNullableSubsequent, bool allowLazy) 2205RegexNode? parent = subsequent.Parent; 2215var peers = (List<RegexNode>)parent.Children!; 2524RegexNode child = Child(i); 2631static bool CanJoinLengthCheck(RegexNode node) => node.Kind switch 2642RegexNode child = Child(childIndex); 2670public RegexNode MakeQuantifier(bool lazy, int min, int max) 2707var result = new RegexNode(lazy ? RegexNodeKind.Lazyloop : RegexNodeKind.Loop, Options, min, max); 2713public void AddChild(RegexNode newChild) 2723else if (Children is RegexNode currentChild) 2725Children = new List<RegexNode>() { currentChild, newChild }; 2729((List<RegexNode>)Children).Add(newChild); 2733public void InsertChild(int index, RegexNode newChild) 2735Debug.Assert(Children is List<RegexNode>); 2741((List<RegexNode>)Children).Insert(index, newChild); 2744public void ReplaceChild(int index, RegexNode newChild) 2753if (Children is RegexNode) 2759((List<RegexNode>)Children)[index] = newChild; 2763public RegexNode Child(int i) => Children is RegexNode child ? child : ((List<RegexNode>)Children!)[i]; 2772if (Children is List<RegexNode> children) 2777Debug.Assert(Children is RegexNode); 2808static bool ExceedsMaxDepthAllowedDepth(RegexNode node, int allowedDepth) 2842RegexNode? curNode = this;

6/// <summary>Specifies the kind of a <see cref="RegexNode"/>.</summary> 16/// <remarks>The character is specified in <see cref="RegexNode.Ch"/>.</remarks> 19/// <remarks>The character is specified in <see cref="RegexNode.Ch"/>.</remarks> 22/// <remarks>The <see cref="RegexCharClass"/> set string is specified in <see cref="RegexNode.Str"/>.</remarks> 26/// <remarks>The characters are specified in <see cref="RegexNode.Str"/>. This is purely a representational optimization, equivalent to multiple <see cref="One"/> nodes concatenated together.</remarks> 31/// The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>. 36/// <remarks>The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>.</remarks> 40/// <remarks>The <see cref="RegexCharClass"/> set string is specified in <see cref="RegexNode.Str"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>.</remarks> 45/// <remarks>The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>.</remarks> 49/// <remarks>The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>.</remarks> 53/// <remarks>The <see cref="RegexCharClass"/> set string is specified in <see cref="RegexNode.Str"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>.</remarks> 59/// The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>. 65/// The character is specified in <see cref="RegexNode.Ch"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>. 71/// The <see cref="RegexCharClass"/> set string is specified in <see cref="RegexNode.Str"/>, the minimum number of iterations in <see cref="RegexNode.M"/>, and the maximum number of iterations in <see cref="RegexNode.N"/>. 77/// <remarks>The capture group number referenced is stored in <see cref="RegexNode.M"/>.</remarks> 126/// <summary>A loop around an arbitrary <see cref="RegexNode"/>, e.g. `(ab|cd)*`.</summary> 128/// One and only one child, the expression in the loop. The minimum number of iterations is in <see cref="RegexNode.M"/>, 129/// and the maximum number of iterations is in <see cref="RegexNode.N"/>. 132/// <summary>A lazy loop around an arbitrary <see cref="RegexNode"/>, e.g. `(ab|cd)*?`.</summary> 134/// One and only one child, the expression in the loop. The minimum number of iterations is in <see cref="RegexNode.M"/>, 135/// and the maximum number of iterations is in <see cref="RegexNode.N"/>. 141/// One and only one child, the expression in the capture. <see cref="RegexNode.M"/> is the number of the capture, and if a balancing 142/// group, <see cref="RegexNode.N"/> is the uncapture. 169/// The referenced capture group number is stored in <see cref="RegexNode.M"/>.

24private RegexNode? _stack; 25private RegexNode? _group; 26private RegexNode? _alternation; 27private RegexNode? _concatenation; 28private RegexNode? _unit; 109RegexNode root = parser.ScanRegex(); 144RegexNode root = parser.ScanReplacement(); 270private RegexNode ScanRegex() 332_unit = RegexNode.CreateOneWithCaseConversion(_pattern[endpos - 1], _options, _culture, ref _caseBehavior); 353if (ScanGroupOpen() is RegexNode grouper) 519private RegexNode ScanReplacement() 748private RegexNode? ScanGroupOpen() 1076private RegexNode? ScanBackslash(bool scanOnly) 1141RegexNode? result = ScanBasicBackslash(scanOnly); 1151private RegexNode? ScanBasicBackslash(bool scanOnly) 1280RegexNode.CreateOneWithCaseConversion(ch, _options, _culture, ref _caseBehavior) : 1285private RegexNode ScanDollar() 1289return RegexNode.CreateOneWithCaseConversion('$', _options, _culture, ref _caseBehavior); 1379return RegexNode.CreateOneWithCaseConversion('$', _options, _culture, ref _caseBehavior); 1412return RegexNode.CreateOneWithCaseConversion('$', _options, _culture, ref _caseBehavior); 2018_concatenation!.AddChild(RegexNode.CreateOneWithCaseConversion(_pattern[pos], isReplacement ? _options & ~RegexOptions.IgnoreCase : _options, _culture, ref _caseBehavior)); 2028_concatenation!.AddChild(RegexNode.CreateOneWithCaseConversion(c, _options, _culture, ref _caseBehavior)); 2065private void StartGroup(RegexNode openGroup)

21public static string[]? FindPrefixes(RegexNode node, bool ignoreCase) 57static bool FindPrefixesCore(RegexNode node, List<StringBuilder> results, bool ignoreCase) 340public static string FindPrefix(RegexNode node) 348static bool Process(RegexNode node, ref ValueStringBuilder vsb) 483public static string? FindPrefixOrdinalCaseInsensitive(RegexNode node) 511public static List<RegexFindOptimizations.FixedDistanceSet>? FindFixedDistanceSets(RegexNode root, bool thorough) 586static bool TryFindRawFixedSets(RegexNode node, List<RegexFindOptimizations.FixedDistanceSet> results, ref int distance, bool thorough) 904public static string? FindFirstCharClass(RegexNode root) 933static bool? TryFindFirstCharClass(RegexNode node, ref RegexCharClass? cc) 1103public static (RegexNode LoopNode, (char Char, string? String, StringComparison StringComparison, char[]? Chars) Literal)? FindLiteralFollowingLeadingLoop(RegexNode node) 1130RegexNode firstChild = node.Child(0); 1142RegexNode nextChild = node.Child(1); 1232public static RegexNodeKind FindLeadingAnchor(RegexNode node) => 1236public static RegexNodeKind FindTrailingAnchor(RegexNode node) => 1240private static RegexNodeKind FindLeadingOrTrailingAnchor(RegexNode node, bool leading) 1276RegexNode? child = null;

37public RegexReplacement(string rep, RegexNode concat, Hashtable _caps) 49RegexNode child = concat.Child(i);

11/// Provides the core data describing a parsed <see cref="RegexNode"/> tree, along with necessary 18/// <summary>The root node of the parsed <see cref="RegexNode"/> tree.</summary> 19public readonly RegexNode Root; 43internal RegexTree(RegexNode root, int captureCount, string[]? captureNames, Hashtable? captureNameToNumberMapping, Hashtable? captureNumberSparseMapping, RegexOptions options, CultureInfo? culture)

9/// <summary>Analyzes a <see cref="RegexTree"/> of <see cref="RegexNode"/>s to produce data on the tree structure, in particular in support of code generation.</summary> 19static bool TryAnalyze(RegexNode node, AnalysisResults results, bool isAtomicByAncestor, bool isInLoop) 33(results._inLoops ??= new HashSet<RegexNode>()).Add(node); 52(results._mayBacktrack ??= new HashSet<RegexNode>()).Add(node); 85RegexNode child = node.Child(i); 135(results._mayBacktrack ??= new HashSet<RegexNode>()).Add(node); 158internal readonly HashSet<RegexNode> _isAtomicByAncestor = new(); // since the root is implicitly atomic, every tree will contain atomic-by-ancestor nodes 160internal readonly HashSet<RegexNode> _containsCapture = new(); // the root is a capture, so this will always contain at least the root node 162internal HashSet<RegexNode>? _mayBacktrack; 164internal HashSet<RegexNode>? _inLoops; 183public bool IsAtomicByAncestor(RegexNode node) => _isAtomicByAncestor.Contains(node); 191public bool MayContainCapture(RegexNode node) => !_complete || _containsCapture.Contains(node); 204public bool MayBacktrack(RegexNode node) => !_complete || (_mayBacktrack?.Contains(node) ?? false); 224public bool IsInLoop(RegexNode node) => !_complete || (_inLoops?.Contains(node) ?? false);

78RegexNode curNode = _tree.Root; 201private void EmitFragment(RegexNodeKind nodeType, RegexNode node, int curIndex)

14/// <see cref="AddLast(DoublyLinkedList{T})"/> operation is made use of in the <see cref="RegexNodeConverter.ConvertToSymbolicRegexNode(RegexNode)"/> method 15/// where it maintains linear construction time in terms of the overall number of AST nodes in a given <see cref="RegexNode"/> input.

13/// <summary>Provides functionality to convert <see cref="RegexNode"/>s to corresponding <see cref="SymbolicRegexNode{S}"/>s.</summary> 26/// <summary>Converts the root <see cref="RegexNode"/> into its corresponding <see cref="SymbolicRegexNode{S}"/>.</summary> 29internal SymbolicRegexNode<BDD> ConvertToSymbolicRegexNode(RegexNode root) 37Stack<(RegexNode Node, DoublyLinkedList<SymbolicRegexNode<BDD>> Result, DoublyLinkedList<SymbolicRegexNode<BDD>>[]? ChildResults)> stack = new(); 42while (stack.TryPop(out (RegexNode Node, DoublyLinkedList<SymbolicRegexNode<BDD>> Result, DoublyLinkedList<SymbolicRegexNode<BDD>>[]? ChildResults) popped)) 44RegexNode node = popped.Node; 191static string UnexpectedNodeType(RegexNode node) 310SymbolicRegexNode<BDD> ConvertSet(RegexNode node)