3 // namespace: System.Text.RegularExpressions
4 // file: interpreter.cs
6 // author: Dan Lewis (dlewis@gmx.co.uk)
10 // Permission is hereby granted, free of charge, to any person obtaining
11 // a copy of this software and associated documentation files (the
12 // "Software"), to deal in the Software without restriction, including
13 // without limitation the rights to use, copy, modify, merge, publish,
14 // distribute, sublicense, and/or sell copies of the Software, and to
15 // permit persons to whom the Software is furnished to do so, subject to
16 // the following conditions:
18 // The above copyright notice and this permission notice shall be
19 // included in all copies or substantial portions of the Software.
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 using System.Collections;
32 using System.Collections.Generic;
33 using System.Diagnostics;
34 using System.Globalization;
36 namespace System.Text.RegularExpressions {
38 partial class Interpreter : BaseMachine {
39 private int ReadProgramCount (int ptr)
41 int ret = program [ptr + 1];
47 public Interpreter (ushort[] program) {
48 this.program = program;
52 Debug.Assert ((OpCode)program[0] == OpCode.Info, "Regex", "Cant' find info block");
53 this.group_count = ReadProgramCount (1) + 1;
54 this.match_min = ReadProgramCount (3);
55 //this.match_max = ReadProgramCount (5);
59 this.program_start = 7;
60 this.groups = new int [group_count];
63 // IMachine implementation
65 public override Match Scan (Regex regex, string text, int start, int end) {
68 this.scan_ptr = start;
70 if (Eval (Mode.Match, ref scan_ptr, program_start))
71 return GenerateMatch (regex);
78 private void Reset () {
83 private class JumpTestEntry {
88 private bool Eval (Mode mode, ref int ref_ptr, int pc,
89 List<JumpTestEntry> JumpTestList = null,
90 List<List<JumpTestEntry>> TriedCombos = null,
91 bool BypassJumpTest = false)
93 if (TriedCombos == null) {
94 TriedCombos = new List<List<JumpTestEntry>> ();
96 if (JumpTestList == null) {
97 JumpTestList = new List<JumpTestEntry> ();
99 return Eval_Real (mode, ref ref_ptr, pc,
100 JumpTestList,TriedCombos,
103 bool OutOfOptions = false;
105 while (!OutOfOptions) {
106 retval = Eval_Real(mode, ref ref_ptr, pc,
107 JumpTestList,TriedCombos,false);
108 if (retval == true) {
109 OutOfOptions = false;
113 if (JumpTestList.Count == 0) {
117 TriedCombos.Add(JumpTestList);
119 List<JumpTestEntry> ();
125 private bool Eval_Real (Mode mode, ref int ref_ptr, int pc, List<JumpTestEntry> JumpTestList, List<List<JumpTestEntry>> TriedCombos,bool BypassJumpTest) {
129 ushort word = program[pc];
130 OpCode op = (OpCode)(word & 0x00ff);
131 OpFlags flags = (OpFlags)(word & 0xff00);
134 case OpCode.Anchor: {
135 int skip = program[pc + 1];
137 int anch_offset = program[pc + 2];
138 bool anch_reverse = (flags & OpFlags.RightToLeft) != 0;
139 int anch_ptr = anch_reverse ? ptr - anch_offset : ptr + anch_offset;
140 int anch_end = text_end - match_min + anch_offset; // maximum anchor position
146 // the general case for an anchoring expression is at the bottom, however we
147 // do some checks for the common cases before to save processing time. the current
148 // optimizer only outputs three types of anchoring expressions: fixed position,
149 // fixed substring, and no anchor.
151 OpCode anch_op = (OpCode)(program[pc + 3] & 0x00ff);
152 if (anch_op == OpCode.Position && skip == 6) { // position anchor
157 switch ((Position)program[pc + 4]) {
158 case Position.StartOfString:
159 if (anch_reverse || anch_offset == 0) {
162 if (TryMatch (ref ptr, pc + skip, JumpTestList ,TriedCombos, BypassJumpTest))
167 case Position.StartOfLine:
170 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
176 while ((anch_reverse && anch_ptr >= 0) || (!anch_reverse && anch_ptr <= anch_end)) {
177 if (anch_ptr == 0 || text[anch_ptr - 1] == '\n') {
179 ptr = anch_ptr == anch_end ? anch_ptr : anch_ptr + anch_offset;
181 ptr = anch_ptr == 0 ? anch_ptr : anch_ptr - anch_offset;
182 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
193 case Position.StartOfScan:
194 if (anch_ptr == scan_ptr) {
195 ptr = anch_reverse ? scan_ptr + anch_offset : scan_ptr - anch_offset;
196 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
206 else if (qs != null ||
207 (anch_op == OpCode.String && skip == 6 + program[pc + 4])) { // substring anchor
212 bool reverse = ((OpFlags)program[pc + 3] & OpFlags.RightToLeft) != 0;
215 bool ignore = ((OpFlags)program[pc + 3] & OpFlags.IgnoreCase) != 0;
216 string substring = GetString (pc + 3);
217 qs = new QuickSearch (substring, ignore, reverse);
219 while ((anch_reverse && anch_ptr >= anch_begin)
220 || (!anch_reverse && anch_ptr <= anch_end)) {
224 anch_ptr = qs.Search (text, anch_ptr, anch_begin);
226 anch_ptr += qs.Length ;
230 anch_ptr = qs.Search (text, anch_ptr, anch_end);
234 ptr = reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
235 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
244 else if (anch_op == OpCode.True) { // no anchor
249 while ((anch_reverse && anch_ptr >= anch_begin)
250 || (!anch_reverse && anch_ptr <= anch_end)) {
253 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
261 else { // general case
266 while ((anch_reverse && anch_ptr >= anch_begin)
267 || (!anch_reverse && anch_ptr <= anch_end)) {
270 if (Eval (Mode.Match, ref ptr, pc + 3, JumpTestList, TriedCombos, BypassJumpTest)) {
271 // anchor expression passed: try real expression at the correct offset
273 ptr = anch_reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
274 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
296 case OpCode.Position: {
297 if (!IsPosition ((Position)program[pc + 1], ptr))
303 case OpCode.String: {
304 bool reverse = (flags & OpFlags.RightToLeft) != 0;
305 bool ignore = (flags & OpFlags.IgnoreCase) != 0;
306 int len = program[pc + 1];
314 if (ptr + len > text_end)
318 for (int i = 0; i < len; ++ i) {
319 char c = text[ptr + i];
321 c = Char.ToLower (c);
323 if (c != (char)program[pc ++])
332 case OpCode.Reference: {
333 bool reverse = (flags & OpFlags.RightToLeft) != 0;
334 bool ignore = (flags & OpFlags.IgnoreCase) != 0;
335 int m = GetLastDefined (program [pc + 1]);
339 int str = marks [m].Index;
340 int len = marks [m].Length;
347 else if (ptr + len > text_end)
352 for (int i = 0; i < len; ++ i) {
353 if (Char.ToLower (text[ptr + i]) != Char.ToLower (text[str + i]))
357 for (int i = 0; i < len; ++ i) {
358 if (text[ptr + i] != text[str + i])
368 case OpCode.Character: case OpCode.Category: case OpCode.NotCategory:
369 case OpCode.Range: case OpCode.Set: {
370 if (!EvalChar (mode, ref ptr, ref pc, false))
376 int target = pc + program[pc + 1];
378 if (!EvalChar (mode, ref ptr, ref pc, true))
386 Open (program[pc + 1], ptr);
392 Close (program[pc + 1], ptr);
397 case OpCode.BalanceStart: {
399 int start = ptr; //point before the balancing group
401 if (!Eval (Mode.Match, ref ptr, pc + 5, JumpTestList, TriedCombos, BypassJumpTest))
406 if(!Balance (program[pc + 1], program[pc + 2], (program[pc + 3] == 1 ? true : false) , start)) {
411 pc += program[pc + 4];
415 case OpCode.Balance: {
419 case OpCode.IfDefined: {
420 int m = GetLastDefined (program [pc + 2]);
422 pc += program[pc + 1];
429 if (!Eval (Mode.Match, ref ptr, pc + 2, JumpTestList, TriedCombos, BypassJumpTest))
432 pc += program[pc + 1];
437 int cp = Checkpoint ();
439 if (Eval (Mode.Match, ref test_ptr, pc + 3, JumpTestList, TriedCombos, true))
440 pc += program[pc + 1];
443 pc += program[pc + 2];
448 case OpCode.Branch: {
451 int cp = Checkpoint ();
452 if (Eval (Mode.Match, ref ptr, pc + 2, JumpTestList, TriedCombos, BypassJumpTest))
457 pc += program[pc + 1];
458 branch_op = (OpCode)(program[pc] & 0xff);
459 } while (branch_op != OpCode.False);
463 case OpCode.JumpTest: {
464 /*This reached when we have a "|" (or)
465 *condition and we don't want to short
466 *circuit every time - i.e. after a
467 *full trip through, if we fail tr
470 if (!BypassJumpTest) {
471 JumpTestEntry jte = new JumpTestEntry();
475 Match = CheckComboMatch (TriedCombos, JumpTestList, pc, ptr);
477 JumpTestList.Add(jte);
478 pc += program[pc + 1];
481 pc += program[pc + 2];//pc+2 before
485 pc += program[pc + 1];
491 pc += program[pc + 1];
495 case OpCode.Repeat: {
496 this.repeat = new RepeatContext (
497 this.repeat, // previous context
498 ReadProgramCount (pc + 2), // minimum
499 ReadProgramCount (pc + 4), // maximum
500 (flags & OpFlags.Lazy) != 0, // lazy
501 pc + 6 // subexpression
504 if (Eval (Mode.Match, ref ptr, pc + program[pc + 1], JumpTestList, TriedCombos, BypassJumpTest))
507 this.repeat = this.repeat.Previous;
513 RepeatContext current = this.repeat;
516 // Can we avoid recursion?
518 // Backtracking can be forced in nested quantifiers from the tail of this quantifier.
519 // Thus, we cannot, in general, use a simple loop on repeat.Expression to handle
522 // If 'deep' was unmolested, that implies that there was no nested quantifiers.
523 // Thus, we can safely avoid recursion.
528 int start = current.Start;
529 int start_count = current.Count;
531 while (!current.IsMinimum) {
535 if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
536 current.Start = start;
537 current.Count = start_count;
540 if (deep != current) // recursive mode
544 if (ptr == current.Start) {
545 // degenerate match ... match tail or fail
546 this.repeat = current.Previous;
548 if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest))
551 this.repeat = current;
555 if (current.IsLazy) {
557 // match tail first ...
558 this.repeat = current.Previous;
560 int cp = Checkpoint ();
561 if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest))
566 // ... then match more
567 this.repeat = current;
568 if (current.IsMaximum)
573 if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
574 current.Start = start;
575 current.Count = start_count;
578 if (deep != current) // recursive mode
580 // Degenerate match: ptr has not moved since the last (failed) tail match.
581 // So, next and subsequent tail matches will fail.
582 if (ptr == current.Start)
586 int stack_size = stack.Count;
588 // match greedily as much as possible
589 while (!current.IsMaximum) {
590 int cp = Checkpoint ();
592 int old_start = current.Start;
597 if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
599 current.Start = old_start;
603 if (deep != current) {
604 // recursive mode: no more backtracking, truncate the stack
605 stack.Count = stack_size;
609 stack.Push (old_ptr);
611 // Degenerate match: no point going on
612 if (ptr == current.Start)
616 // then, match the tail, backtracking as necessary.
617 this.repeat = current.Previous;
620 if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest)) {
621 stack.Count = stack_size;
624 if (stack.Count == stack_size) {
625 this.repeat = current;
631 Backtrack (stack.Pop ());
636 case OpCode.FastRepeat: {
637 this.fast = new RepeatContext (
639 ReadProgramCount (pc + 2), // minimum
640 ReadProgramCount (pc + 4), // maximum
641 (flags & OpFlags.Lazy) != 0, // lazy
642 pc + 6 // subexpression
647 int cp = Checkpoint ();
649 pc += program[pc + 1]; // tail expression
650 ushort tail_word = program[pc];
652 int c1 = -1; // first character of tail operator
653 int c2 = -1; // ... and the same character, in upper case if ignoring case
654 int coff = 0; // 0 or -1 depending on direction
656 OpCode tail_op = (OpCode)(tail_word & 0xff);
657 if (tail_op == OpCode.Character || tail_op == OpCode.String) {
658 OpFlags tail_flags = (OpFlags)(tail_word & 0xff00);
660 if ((tail_flags & OpFlags.Negate) != 0)
663 if (tail_op == OpCode.String)
667 if ((tail_flags & OpFlags.RightToLeft) != 0)
669 offset = program[pc + 1] - 1 ;
672 c1 = program[pc + 2 + offset]; // first char of string
675 c1 = program[pc + 1]; // character
677 if ((tail_flags & OpFlags.IgnoreCase) != 0)
678 c2 = Char.ToUpper ((char)c1); // ignore case
682 if ((tail_flags & OpFlags.RightToLeft) != 0)
683 coff = -1; // reverse
690 if (!fast.IsMinimum && !Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
691 fast = fast.Previous;
697 if (c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) {
699 if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest))
703 if (fast.IsMaximum) {
704 fast = fast.Previous;
709 if (!Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
710 fast = fast.Previous;
714 fast = fast.Previous;
718 if (!Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
719 fast = fast.Previous;
725 width = (ptr - fast.Start) / fast.Count;
731 if (c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) {
733 if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest))
738 if (!fast.IsMinimum) {
739 fast = fast.Previous;
746 fast = fast.Previous;
752 Debug.Assert (false, "Regex", "Info block found in pattern");
766 if (fast.IsMaximum || (fast.IsLazy && fast.IsMinimum))
769 pc = fast.Expression;
780 if (!fast.IsLazy && fast.IsMinimum)
783 ref_ptr = fast.Start;
791 private bool EvalChar (Mode mode, ref int ptr, ref int pc, bool multi) {
792 bool consumed = false;
798 ushort word = program[pc];
799 OpCode op = (OpCode)(word & 0x00ff);
800 OpFlags flags = (OpFlags)(word & 0xff00);
804 ignore = (flags & OpFlags.IgnoreCase) != 0;
806 // consume character: the direction of an In construct is
807 // determined by the direction of its first op
810 if ((flags & OpFlags.RightToLeft) != 0) {
824 c = Char.ToLower (c);
831 negate = (flags & OpFlags.Negate) != 0;
842 case OpCode.Character: {
843 if (c == (char)program[pc ++])
848 case OpCode.Category: {
849 if (CategoryUtils.IsCategory ((Category)program[pc ++], c))
854 case OpCode.NotCategory: {
855 if (!CategoryUtils.IsCategory ((Category)program[pc ++], c))
861 int lo = (char)program[pc ++];
862 int hi = (char)program[pc ++];
863 if (lo <= c && c <= hi)
869 int lo = (char)program[pc ++];
870 int len = (char)program[pc ++];
875 if (i < 0 || i >= len << 4)
879 if ((program[bits + (i >> 4)] & (1 << (i & 0xf))) != 0)
889 private bool CheckComboMatch (List<List<JumpTestEntry>> TriedCombos, List<JumpTestEntry> JumpTestList, int pc, int ptr)
892 if (TriedCombos != null && TriedCombos.Count > 0)
894 for (int i = 0;i < TriedCombos.Count;i++)
896 if ((TriedCombos[i] != null) &&
897 (TriedCombos[i].Count > 0))
899 int j = TriedCombos[i].Count - 1;
900 if ((TriedCombos[i][j].pc == pc) && (TriedCombos[i][j].ptr == ptr))
902 if (CheckSubCmb( TriedCombos, JumpTestList,
915 private bool CheckSubCmb(List<List<JumpTestEntry>> TriedCombos,
916 List<JumpTestEntry> JumpTestList,int i,int j,ref bool Match)
918 if ((JumpTestList.Count <= TriedCombos[i].Count-1))
921 if (TriedCombos[i].Count > 1)
923 for (j = 0;j < JumpTestList.Count;j++)
925 if ((TriedCombos[i][j].pc == JumpTestList[j].pc) &&
926 (TriedCombos[i][j].ptr == JumpTestList[j].ptr))
947 private bool TryMatch (ref int ref_ptr, int pc, List<JumpTestEntry> JumpTestList,List<List<JumpTestEntry>> TriedCombos, bool BypassJumpTest) {
951 marks [groups [0]].Start = ptr;
952 if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest)) {
953 marks [groups [0]].End = ptr;
961 private bool IsPosition (Position pos, int ptr) {
963 case Position.Start: case Position.StartOfString:
966 case Position.StartOfLine:
967 return ptr == 0 || text[ptr - 1] == '\n';
969 case Position.StartOfScan:
970 return ptr == scan_ptr;
973 return ptr == text_end ||
974 (ptr == text_end - 1 && text[ptr] == '\n');
976 case Position.EndOfLine:
977 return ptr == text_end || text[ptr] == '\n';
979 case Position.EndOfString:
980 return ptr == text_end;
982 case Position.Boundary:
987 return IsWordChar (text[ptr]);
988 else if (ptr == text_end)
989 return IsWordChar (text[ptr - 1]);
991 return IsWordChar (text[ptr]) != IsWordChar (text[ptr - 1]);
993 case Position.NonBoundary:
998 return !IsWordChar (text[ptr]);
999 else if (ptr == text_end)
1000 return !IsWordChar (text[ptr - 1]);
1002 return IsWordChar (text[ptr]) == IsWordChar (text[ptr - 1]);
1009 private bool IsWordChar (char c) {
1010 return CategoryUtils.IsCategory (Category.Word, c);
1013 private string GetString (int pc) {
1014 int len = program[pc + 1];
1017 char[] cs = new char[len];
1018 for (int i = 0; i < len; ++ i)
1019 cs[i] = (char)program[str ++];
1021 return new string (cs);
1024 // capture management
1026 private void Open (int gid, int ptr) {
1027 int m = groups [gid];
1028 if (m < mark_start || marks [m].IsDefined) {
1033 marks [m].Start = ptr;
1036 private void Close (int gid, int ptr) {
1037 marks [groups [gid]].End = ptr;
1040 private bool Balance (int gid, int balance_gid, bool capture, int ptr) {
1041 int b = groups [balance_gid];
1043 if(b == -1 || marks[b].Index < 0) {
1044 //Group not previously matched
1047 Debug.Assert (marks [b].IsDefined, "Regex", "Balancng group not closed");
1048 if (gid > 0 && capture){
1049 Open (gid, marks [b].Index + marks [b].Length);
1053 groups [balance_gid] = marks[b].Previous;
1058 private int Checkpoint () {
1059 mark_start = mark_end;
1063 private void Backtrack (int cp) {
1064 Debug.Assert (cp > mark_start, "Regex", "Attempt to backtrack forwards");
1065 for (int i = 0; i < groups.Length; ++ i) {
1068 marks [m].Start = -1;
1069 m = marks [m].Previous;
1077 private void ResetGroups () {
1078 int n = groups.Length;
1080 marks = new Mark [n * 10];
1082 for (int i = 0; i < n; ++ i) {
1085 marks [i].Start = -1;
1087 marks [i].Previous = -1;
1094 private int GetLastDefined (int gid) {
1095 int m = groups [gid];
1096 while (m >= 0 && !marks [m].IsDefined)
1097 m = marks [m].Previous;
1102 private int CreateMark (int previous) {
1103 if (mark_end == marks.Length) {
1104 Mark [] dest = new Mark [marks.Length * 2];
1105 marks.CopyTo (dest, 0);
1109 int m = mark_end ++;
1110 marks [m].Start = marks [m].End = -1;
1111 marks [m].Previous = previous;
1116 private void GetGroupInfo (int gid, out int first_mark_index, out int n_caps)
1118 first_mark_index = -1;
1120 for (int m = groups [gid]; m >= 0; m = marks [m].Previous) {
1121 if (!marks [m].IsDefined)
1123 if (first_mark_index < 0)
1124 first_mark_index = m;
1129 private void PopulateGroup (Group g, int first_mark_index, int n_caps)
1132 for (int m = marks [first_mark_index].Previous; m >= 0; m = marks [m].Previous) {
1133 if (!marks [m].IsDefined)
1135 Capture cap = new Capture (text, marks [m].Index, marks [m].Length);
1136 g.Captures.SetValue (cap, n_caps - 1 - i);
1141 private Match GenerateMatch (Regex regex)
1143 int n_caps, first_mark_index;
1145 GetGroupInfo (0, out first_mark_index, out n_caps);
1147 // Avoid fully populating the Match instance if not needed
1148 if (!needs_groups_or_captures)
1149 return new Match (regex, this, text, text_end, 0, marks [first_mark_index].Index, marks [first_mark_index].Length);
1151 Match retval = new Match (regex, this, text, text_end, groups.Length,
1152 marks [first_mark_index].Index, marks [first_mark_index].Length, n_caps);
1153 PopulateGroup (retval, first_mark_index, n_caps);
1155 for (int gid = 1; gid < groups.Length; ++ gid) {
1156 GetGroupInfo (gid, out first_mark_index, out n_caps);
1157 if (first_mark_index < 0) {
1160 g = new Group (text, marks [first_mark_index].Index, marks [first_mark_index].Length, n_caps);
1161 PopulateGroup (g, first_mark_index, n_caps);
1163 retval.Groups.SetValue (g, gid);
1168 // interpreter attributes
1170 private ushort[] program; // regex program
1171 private int program_start; // first instruction after info block
1172 private string text; // input text
1173 private int text_end; // end of input text (last character + 1)
1174 private int group_count; // number of capturing groups
1175 private int match_min;//, match_max; // match width information
1176 private QuickSearch qs; // fast substring matcher
1180 private int scan_ptr; // start of scan
1182 private RepeatContext repeat; // current repeat context
1183 private RepeatContext fast; // fast repeat context
1185 // Repeat/Until handling
1186 private IntStack stack = new IntStack (); // utility stack
1187 private RepeatContext deep; // points to the most-nested repeat context
1189 private Mark[] marks = null; // mark stack
1190 private int mark_start; // start of current checkpoint
1191 private int mark_end; // end of checkpoint/next free mark
1193 private int[] groups; // current group definitions
1197 private struct IntStack {
1202 return values [--count];
1204 public void Push (int value)
1206 if (values == null) {
1207 values = new int [8];
1208 } else if (count == values.Length) {
1209 int new_size = values.Length;
1210 new_size += new_size >> 1;
1211 int [] new_values = new int [new_size];
1212 for (int i = 0; i < count; ++i)
1213 new_values [i] = values [i];
1214 values = new_values;
1216 values [count++] = value;
1219 get { return values [count - 1]; }
1222 get { return count; }
1225 throw new SystemException ("can only truncate the stack");
1231 private class RepeatContext {
1232 public RepeatContext (RepeatContext previous, int min, int max, bool lazy, int expr_pc) {
1233 this.previous = previous;
1237 this.expr_pc = expr_pc;
1244 get { return count; }
1245 set { count = value; }
1249 get { return start; }
1250 set { start = value; }
1253 public bool IsMinimum {
1254 get { return min <= count; }
1257 public bool IsMaximum {
1258 get { return max <= count; }
1261 public bool IsLazy {
1262 get { return lazy; }
1265 public int Expression {
1266 get { return expr_pc; }
1269 public RepeatContext Previous {
1270 get { return previous; }
1274 private int min, max;
1276 private int expr_pc;
1277 private RepeatContext previous;