mcs/class/System/System.Text.RegularExpressions/interpreter.cs

   1 //
   2 // assembly:    System
   3 // namespace:   System.Text.RegularExpressions
   4 // file:        interpreter.cs
   5 //
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)
   7 //              (c) 2002
   8
   9 //
  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:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  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.
  28 //
  29
  30 using System;
  31 using System.Collections;
  32 using System.Collections.Generic;
  33 using System.Diagnostics;
  34 using System.Globalization;
  35
  36 namespace System.Text.RegularExpressions {
  37
  38         partial class Interpreter : BaseMachine {
  39                 private int ReadProgramCount (int ptr)
  40                 {
  41                         int ret = program [ptr + 1];
  42                         ret <<= 16;
  43                         ret += program [ptr];
  44                         return ret;
  45                 }
  46
  47                 public Interpreter (ushort[] program) {
  48                         this.program = program;
  49                         this.qs = null;
  50
  51                         // process info block
  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);
  56
  57                         // setup
  58
  59                         this.program_start = 7;
  60                         this.groups = new int [group_count];
  61                 }
  62
  63                 // IMachine implementation
  64
  65                 public override Match Scan (Regex regex, string text, int start, int end) {
  66                         this.text = text;
  67                         this.text_end = end;
  68                         this.scan_ptr = start;
  69
  70                         if (Eval (Mode.Match, ref scan_ptr, program_start))
  71                                 return GenerateMatch (regex);
  72
  73                         return Match.Empty;
  74                 }
  75
  76                 // private methods
  77
  78                 private void Reset () {
  79                         ResetGroups ();
  80                         fast = repeat = null;
  81                 }
  82
  83                 private class JumpTestEntry {
  84                         public int pc;
  85                         public int ptr;
  86                 }
  87
  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)
  92                 {
  93                         if (TriedCombos == null) {
  94                                 TriedCombos = new List<List<JumpTestEntry>> ();
  95                         }
  96                         if (JumpTestList == null) {
  97                                 JumpTestList = new List<JumpTestEntry> ();
  98                         } else {
  99                                 return Eval_Real (mode, ref ref_ptr, pc,
 100                                         JumpTestList,TriedCombos,
 101                                         BypassJumpTest);
 102                         }
 103                         bool OutOfOptions = false;
 104                         bool retval = false;
 105                         while (!OutOfOptions) {
 106                                 retval = Eval_Real(mode, ref ref_ptr, pc,
 107                                         JumpTestList,TriedCombos,false);
 108                                 if (retval == true) {
 109                                         OutOfOptions = false;
 110                                         return true;
 111                                 }
 112                                 //else
 113                                 if (JumpTestList.Count == 0) {
 114                                         OutOfOptions = true;
 115                                         return false;
 116                                 } else {
 117                                         TriedCombos.Add(JumpTestList);
 118                                         JumpTestList = new
 119                                                 List<JumpTestEntry> ();
 120                                 }
 121
 122                         }
 123                         return retval;
 124                 }
 125                 private bool Eval_Real (Mode mode, ref int ref_ptr, int pc, List<JumpTestEntry> JumpTestList, List<List<JumpTestEntry>> TriedCombos,bool BypassJumpTest) {
 126                         int ptr = ref_ptr;
 127                 Begin:
 128                         for (;;) {
 129                                 ushort word = program[pc];
 130                                 OpCode op = (OpCode)(word & 0x00ff);
 131                                 OpFlags flags = (OpFlags)(word & 0xff00);
 132
 133                                 switch (op) {
 134                                 case OpCode.Anchor: {
 135                                         int skip = program[pc + 1];
 136
 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
 141
 142
 143                                         int anch_begin =  0;
 144
 145
 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.
 150
 151                                         OpCode anch_op = (OpCode)(program[pc + 3] & 0x00ff);
 152                                         if (anch_op == OpCode.Position && skip == 6) {                          // position anchor
 153                                                 // Anchor
 154                                                 //      Position
 155                                                 //      True
 156
 157                                                 switch ((Position)program[pc + 4]) {
 158                                                 case Position.StartOfString:
 159                                                         if (anch_reverse || anch_offset == 0) {
 160                                                                 if (anch_reverse)
 161                                                                         ptr = anch_offset;
 162                                                                 if (TryMatch (ref ptr, pc + skip, JumpTestList ,TriedCombos, BypassJumpTest))
 163                                                                         goto Pass;
 164                                                         }
 165                                                         break;
 166
 167                                                 case Position.StartOfLine:
 168                                                          if (anch_ptr == 0) {
 169                                                                 ptr = 0;
 170                                                                 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
 171                                                                         goto Pass;
 172
 173                                                                 ++ anch_ptr;
 174                                                         }
 175
 176                                                         while ((anch_reverse && anch_ptr >= 0) || (!anch_reverse && anch_ptr <= anch_end)) {
 177                                                                 if (anch_ptr == 0 || text[anch_ptr - 1] == '\n') {
 178                                                                         if (anch_reverse)
 179                                                                                 ptr = anch_ptr == anch_end ? anch_ptr : anch_ptr + anch_offset;
 180                                                                         else
 181                                                                                 ptr = anch_ptr == 0 ? anch_ptr : anch_ptr - anch_offset;
 182                                                                         if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
 183                                                                                 goto Pass;
 184                                                                 }
 185
 186                                                                 if (anch_reverse)
 187                                                                         -- anch_ptr;
 188                                                                 else
 189                                                                         ++ anch_ptr;
 190                                                         }
 191                                                         break;
 192
 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))
 197                                                                         goto Pass;
 198                                                         }
 199                                                         break;
 200
 201                                                 default:
 202                                                         // FIXME
 203                                                         break;
 204                                                 }
 205                                         }
 206                                         else if (qs != null ||
 207                                                 (anch_op == OpCode.String && skip == 6 + program[pc + 4])) {    // substring anchor
 208                                                 // Anchor
 209                                                 //      String
 210                                                 //      True
 211
 212                                                 bool reverse = ((OpFlags)program[pc + 3] & OpFlags.RightToLeft) != 0;
 213
 214                                                 if (qs == null) {
 215                                                         bool ignore = ((OpFlags)program[pc + 3] & OpFlags.IgnoreCase) != 0;
 216                                                         string substring = GetString (pc + 3);
 217                                                         qs = new QuickSearch (substring, ignore, reverse);
 218                                                 }
 219                                                 while ((anch_reverse && anch_ptr >= anch_begin)
 220                                                        || (!anch_reverse && anch_ptr <= anch_end)) {
 221
 222                                                         if (reverse)
 223                                                         {
 224                                                                 anch_ptr = qs.Search (text, anch_ptr, anch_begin);
 225                                                                 if (anch_ptr != -1)
 226                                                                         anch_ptr += qs.Length ;
 227
 228                                                         }
 229                                                         else
 230                                                                 anch_ptr = qs.Search (text, anch_ptr, anch_end);
 231                                                         if (anch_ptr < 0)
 232                                                                 break;
 233
 234                                                         ptr = reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
 235                                                         if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
 236                                                                 goto Pass;
 237
 238                                                         if (reverse)
 239                                                                 anch_ptr -= 2;
 240                                                         else
 241                                                                 ++ anch_ptr;
 242                                                 }
 243                                         }
 244                                         else if (anch_op == OpCode.True) {                                      // no anchor
 245                                                 // Anchor
 246                                                 //      True
 247
 248
 249                                                 while ((anch_reverse && anch_ptr >= anch_begin)
 250                                                        || (!anch_reverse && anch_ptr <= anch_end)) {
 251
 252                                                         ptr = anch_ptr;
 253                                                         if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
 254                                                                 goto Pass;
 255                                                         if (anch_reverse)
 256                                                                 -- anch_ptr;
 257                                                         else
 258                                                                 ++ anch_ptr;
 259                                                 }
 260                                         }
 261                                         else {                                                                  // general case
 262                                                 // Anchor
 263                                                 //      <expr>
 264                                                 //      True
 265
 266                                                 while ((anch_reverse && anch_ptr >= anch_begin)
 267                                                        || (!anch_reverse && anch_ptr <= anch_end)) {
 268
 269                                                         ptr = anch_ptr;
 270                                                         if (Eval (Mode.Match, ref ptr, pc + 3, JumpTestList, TriedCombos, BypassJumpTest)) {
 271                                                                 // anchor expression passed: try real expression at the correct offset
 272
 273                                                                 ptr = anch_reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
 274                                                                 if (TryMatch (ref ptr, pc + skip, JumpTestList, TriedCombos, BypassJumpTest))
 275                                                                         goto Pass;
 276                                                         }
 277
 278                                                     if (anch_reverse)
 279                                                                 -- anch_ptr;
 280                                                         else
 281                                                                 ++ anch_ptr;
 282                                                 }
 283                                         }
 284
 285                                         goto Fail;
 286                                 }
 287
 288                                 case OpCode.False: {
 289                                         goto Fail;
 290                                 }
 291
 292                                 case OpCode.True: {
 293                                         goto Pass;
 294                                 }
 295
 296                                 case OpCode.Position: {
 297                                         if (!IsPosition ((Position)program[pc + 1], ptr))
 298                                                 goto Fail;
 299                                         pc += 2;
 300                                         break;
 301                                 }
 302
 303                                 case OpCode.String: {
 304                                         bool reverse = (flags & OpFlags.RightToLeft) != 0;
 305                                         bool ignore = (flags & OpFlags.IgnoreCase) != 0;
 306                                         int len = program[pc + 1];
 307
 308                                         if (reverse) {
 309                                                 ptr -= len;
 310                                                 if (ptr < 0)
 311                                                         goto Fail;
 312                                         }
 313                                         else
 314                                         if (ptr + len > text_end)
 315                                                 goto Fail;
 316
 317                                         pc += 2;
 318                                         for (int i = 0; i < len; ++ i) {
 319                                                 char c = text[ptr + i];
 320                                                 if (ignore)
 321                                                         c = Char.ToLower (c);
 322
 323                                                 if (c != (char)program[pc ++])
 324                                                         goto Fail;
 325                                         }
 326
 327                                         if (!reverse)
 328                                                 ptr += len;
 329                                         break;
 330                                 }
 331
 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]);
 336                                         if (m < 0)
 337                                                 goto Fail;
 338
 339                                         int str = marks [m].Index;
 340                                         int len = marks [m].Length;
 341
 342                                         if (reverse) {
 343                                                 ptr -= len;
 344                                                 if (ptr < 0)
 345                                                         goto Fail;
 346                                         }
 347                                         else if (ptr + len > text_end)
 348                                                 goto Fail;
 349
 350                                         pc += 2;
 351                                         if (ignore) {
 352                                                 for (int i = 0; i < len; ++ i) {
 353                                                         if (Char.ToLower (text[ptr + i]) != Char.ToLower (text[str + i]))
 354                                                                 goto Fail;
 355                                                 }
 356                                         } else {
 357                                                 for (int i = 0; i < len; ++ i) {
 358                                                         if (text[ptr + i] != text[str + i])
 359                                                                 goto Fail;
 360                                                 }
 361                                         }
 362
 363                                         if (!reverse)
 364                                                 ptr += len;
 365                                         break;
 366                                 }
 367
 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))
 371                                                 goto Fail;
 372                                         break;
 373                                 }
 374
 375                                 case OpCode.In: {
 376                                         int target = pc + program[pc + 1];
 377                                         pc += 2;
 378                                         if (!EvalChar (mode, ref ptr, ref pc, true))
 379                                                 goto Fail;
 380
 381                                         pc = target;
 382                                         break;
 383                                 }
 384
 385                                 case OpCode.Open: {
 386                                         Open (program[pc + 1], ptr);
 387                                         pc += 2;
 388                                         break;
 389                                 }
 390
 391                                 case OpCode.Close: {
 392                                         Close (program[pc + 1], ptr);
 393                                         pc += 2;
 394                                         break;
 395                                 }
 396
 397                                 case OpCode.BalanceStart: {
 398
 399                                         int start = ptr; //point before the balancing group
 400
 401                                         if (!Eval (Mode.Match, ref ptr, pc + 5, JumpTestList, TriedCombos, BypassJumpTest))
 402                                                 goto Fail;
 403
 404
 405
 406                                         if(!Balance (program[pc + 1], program[pc + 2], (program[pc + 3] == 1 ? true : false) , start)) {
 407                                                 goto Fail;
 408                                         }
 409
 410
 411                                         pc += program[pc + 4];
 412                                         break;
 413                                 }
 414
 415                                 case OpCode.Balance: {
 416                                         goto Pass;
 417                                 }
 418
 419                                 case OpCode.IfDefined: {
 420                                         int m = GetLastDefined (program [pc + 2]);
 421                                         if (m < 0)
 422                                                 pc += program[pc + 1];
 423                                         else
 424                                                 pc += 3;
 425                                         break;
 426                                 }
 427
 428                                 case OpCode.Sub: {
 429                                         if (!Eval (Mode.Match, ref ptr, pc + 2, JumpTestList, TriedCombos, BypassJumpTest))
 430                                                 goto Fail;
 431
 432                                         pc += program[pc + 1];
 433                                         break;
 434                                 }
 435
 436                                 case OpCode.Test: {
 437                                         int cp = Checkpoint ();
 438                                         int test_ptr = ptr;
 439                                         if (Eval (Mode.Match, ref test_ptr, pc + 3, JumpTestList, TriedCombos, true))
 440                                                 pc += program[pc + 1];
 441                                         else {
 442                                                 Backtrack (cp);
 443                                                 pc += program[pc + 2];
 444                                         }
 445                                         break;
 446                                 }
 447
 448                                 case OpCode.Branch: {
 449                                         OpCode branch_op;
 450                                         do {
 451                                                 int cp = Checkpoint ();
 452                                                 if (Eval (Mode.Match, ref ptr, pc + 2, JumpTestList, TriedCombos, BypassJumpTest))
 453                                                         goto Pass;
 454
 455                                                 Backtrack (cp);
 456
 457                                                 pc += program[pc + 1];
 458                                                 branch_op = (OpCode)(program[pc] & 0xff);
 459                                         } while (branch_op != OpCode.False);
 460
 461                                         goto Fail;
 462                                 }
 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
 468                                          *another path  */
 469
 470                                         if (!BypassJumpTest) {
 471                                                 JumpTestEntry jte = new JumpTestEntry();
 472                                                 jte.ptr = ptr;
 473                                                 jte.pc = pc;
 474                                                 bool Match = false;
 475                                                 Match = CheckComboMatch (TriedCombos, JumpTestList, pc, ptr);
 476                                                 if (!Match) {
 477                                                         JumpTestList.Add(jte);
 478                                                         pc += program[pc + 1];
 479                                                 } else {
 480                                                         //else
 481                                                         pc += program[pc + 2];//pc+2 before
 482                                                 }
 483                                                 break;
 484                                         } else {
 485                                                 pc += program[pc + 1];
 486                                                 break;
 487                                         }
 488                                 }
 489
 490                                 case OpCode.Jump: {
 491                                         pc += program[pc + 1];
 492                                         break;
 493                                 }
 494
 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
 502                                         );
 503
 504                                         if (Eval (Mode.Match, ref ptr, pc + program[pc + 1], JumpTestList, TriedCombos, BypassJumpTest))
 505                                                 goto Pass;
 506                                         else {
 507                                                 this.repeat = this.repeat.Previous;
 508                                                 goto Fail;
 509                                         }
 510                                 }
 511
 512                                 case OpCode.Until: {
 513                                         RepeatContext current = this.repeat;
 514
 515                                         //
 516                                         // Can we avoid recursion?
 517                                         //
 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
 520                                         // quantifiers.
 521                                         //
 522                                         // If 'deep' was unmolested, that implies that there was no nested quantifiers.
 523                                         // Thus, we can safely avoid recursion.
 524                                         //
 525                                         if (deep == current)
 526                                                 goto Pass;
 527
 528                                         int start = current.Start;
 529                                         int start_count = current.Count;
 530
 531                                         while (!current.IsMinimum) {
 532                                                 ++ current.Count;
 533                                                 current.Start = ptr;
 534                                                 deep = current;
 535                                                 if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 536                                                         current.Start = start;
 537                                                         current.Count = start_count;
 538                                                         goto Fail;
 539                                                 }
 540                                                 if (deep != current)    // recursive mode
 541                                                         goto Pass;
 542                                         }
 543
 544                                         if (ptr == current.Start) {
 545                                                 // degenerate match ... match tail or fail
 546                                                 this.repeat = current.Previous;
 547                                                 deep = null;
 548                                                 if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest))
 549                                                         goto Pass;
 550
 551                                                 this.repeat = current;
 552                                                 goto Fail;
 553                                         }
 554
 555                                         if (current.IsLazy) {
 556                                                 for (;;) {
 557                                                         // match tail first ...
 558                                                         this.repeat = current.Previous;
 559                                                         deep = null;
 560                                                         int cp = Checkpoint ();
 561                                                         if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest))
 562                                                                 goto Pass;
 563
 564                                                         Backtrack (cp);
 565
 566                                                         // ... then match more
 567                                                         this.repeat = current;
 568                                                         if (current.IsMaximum)
 569                                                                 goto Fail;
 570                                                         ++ current.Count;
 571                                                         current.Start = ptr;
 572                                                         deep = current;
 573                                                         if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 574                                                                 current.Start = start;
 575                                                                 current.Count = start_count;
 576                                                                 goto Fail;
 577                                                         }
 578                                                         if (deep != current)    // recursive mode
 579                                                                 goto Pass;
 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)
 583                                                                 goto Fail;
 584                                                 }
 585                                         } else {
 586                                                 int stack_size = stack.Count;
 587
 588                                                 // match greedily as much as possible
 589                                                 while (!current.IsMaximum) {
 590                                                         int cp = Checkpoint ();
 591                                                         int old_ptr = ptr;
 592                                                         int old_start = current.Start;
 593
 594                                                         ++ current.Count;
 595                                                         current.Start = ptr;
 596                                                         deep = current;
 597                                                         if (!Eval (Mode.Match, ref ptr, current.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 598                                                                 -- current.Count;
 599                                                                 current.Start = old_start;
 600                                                                 Backtrack (cp);
 601                                                                 break;
 602                                                         }
 603                                                         if (deep != current) {
 604                                                                 // recursive mode: no more backtracking, truncate the stack
 605                                                                 stack.Count = stack_size;
 606                                                                 goto Pass;
 607                                                         }
 608                                                         stack.Push (cp);
 609                                                         stack.Push (old_ptr);
 610
 611                                                         // Degenerate match: no point going on
 612                                                         if (ptr == current.Start)
 613                                                                 break;
 614                                                 }
 615
 616                                                 // then, match the tail, backtracking as necessary.
 617                                                 this.repeat = current.Previous;
 618                                                 for (;;) {
 619                                                         deep = null;
 620                                                         if (Eval (Mode.Match, ref ptr, pc + 1, JumpTestList, TriedCombos, BypassJumpTest)) {
 621                                                                 stack.Count = stack_size;
 622                                                                 goto Pass;
 623                                                         }
 624                                                         if (stack.Count == stack_size) {
 625                                                                 this.repeat = current;
 626                                                                 goto Fail;
 627                                                         }
 628
 629                                                         --current.Count;
 630                                                         ptr = stack.Pop ();
 631                                                         Backtrack (stack.Pop ());
 632                                                 }
 633                                         }
 634                                 }
 635
 636                                 case OpCode.FastRepeat: {
 637                                         this.fast = new RepeatContext (
 638                                                 fast,
 639                                                 ReadProgramCount (pc + 2),              // minimum
 640                                                 ReadProgramCount (pc + 4),              // maximum
 641                                                 (flags & OpFlags.Lazy) != 0,    // lazy
 642                                                 pc + 6                          // subexpression
 643                                         );
 644
 645                                         fast.Start = ptr;
 646
 647                                         int cp = Checkpoint ();
 648
 649                                         pc += program[pc + 1];          // tail expression
 650                                         ushort tail_word = program[pc];
 651
 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
 655
 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);
 659
 660                                                 if ((tail_flags & OpFlags.Negate) != 0)
 661                                                         goto skip;
 662
 663                                                 if (tail_op == OpCode.String)
 664                                                 {
 665                                                         int offset = 0;
 666
 667                                                         if ((tail_flags & OpFlags.RightToLeft) != 0)
 668                                                         {
 669                                                                 offset = program[pc + 1] - 1 ;
 670                                                         }
 671
 672                                                         c1 = program[pc + 2 + offset];                          // first char of string
 673                                                 }
 674                                                 else
 675                                                         c1 = program[pc + 1];                           // character
 676
 677                                                 if ((tail_flags & OpFlags.IgnoreCase) != 0)
 678                                                         c2 = Char.ToUpper ((char)c1);                   // ignore case
 679                                                 else
 680                                                         c2 = c1;
 681
 682                                                 if ((tail_flags & OpFlags.RightToLeft) != 0)
 683                                                         coff = -1;                                      // reverse
 684                                                 else
 685                                                         coff = 0;
 686                                         }
 687
 688                                 skip:
 689                                         if (fast.IsLazy) {
 690                                                 if (!fast.IsMinimum && !Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 691                                                         fast = fast.Previous;
 692                                                         goto Fail;
 693                                                 }
 694
 695                                                 while (true) {
 696                                                         int p = ptr + coff;
 697                                                         if (c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) {
 698                                                                 deep = null;
 699                                                                 if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest))
 700                                                                         break;
 701                                                         }
 702
 703                                                         if (fast.IsMaximum) {
 704                                                                 fast = fast.Previous;
 705                                                                 goto Fail;
 706                                                         }
 707
 708                                                         Backtrack (cp);
 709                                                         if (!Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 710                                                                 fast = fast.Previous;
 711                                                                 goto Fail;
 712                                                         }
 713                                                 }
 714                                                 fast = fast.Previous;
 715                                                 goto Pass;
 716                                         }
 717                                         else {
 718                                                 if (!Eval (Mode.Count, ref ptr, fast.Expression, JumpTestList, TriedCombos, BypassJumpTest)) {
 719                                                         fast = fast.Previous;
 720                                                         goto Fail;
 721                                                 }
 722
 723                                                 int width;
 724                                                 if (fast.Count > 0)
 725                                                         width = (ptr - fast.Start) / fast.Count;
 726                                                 else
 727                                                         width = 0;
 728
 729                                                 while (true) {
 730                                                         int p = ptr + coff;
 731                                                         if (c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) {
 732                                                                 deep = null;
 733                                                                 if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest))
 734                                                                         break;
 735                                                         }
 736
 737                                                         -- fast.Count;
 738                                                         if (!fast.IsMinimum) {
 739                                                                 fast = fast.Previous;
 740                                                                 goto Fail;
 741                                                         }
 742
 743                                                         ptr -= width;
 744                                                         Backtrack (cp);
 745                                                 }
 746                                                 fast = fast.Previous;
 747                                                 goto Pass;
 748                                         }
 749                                 }
 750
 751                                 case OpCode.Info: {
 752                                         Debug.Assert (false, "Regex", "Info block found in pattern");
 753                                         goto Fail;
 754                                 }
 755                                 }
 756                         }
 757                 Pass:
 758                         ref_ptr = ptr;
 759
 760                         switch (mode) {
 761                         case Mode.Match:
 762                                 return true;
 763
 764                         case Mode.Count: {
 765                                 ++ fast.Count;
 766                                 if (fast.IsMaximum || (fast.IsLazy && fast.IsMinimum))
 767                                         return true;
 768
 769                                 pc = fast.Expression;
 770                                 goto Begin;
 771                         }
 772                         }
 773
 774                 Fail:
 775                         switch (mode) {
 776                         case Mode.Match:
 777                                 return false;
 778
 779                         case Mode.Count: {
 780                                 if (!fast.IsLazy && fast.IsMinimum)
 781                                         return true;
 782
 783                                 ref_ptr = fast.Start;
 784                                 return false;
 785                         }
 786                         }
 787
 788                         return false;
 789                 }
 790
 791                 private bool EvalChar (Mode mode, ref int ptr, ref int pc, bool multi) {
 792                         bool consumed = false;
 793                         char c = '\0';
 794                         bool negate;
 795                         bool ignore;
 796
 797                         do {
 798                                 ushort word = program[pc];
 799                                 OpCode op = (OpCode)(word & 0x00ff);
 800                                 OpFlags flags = (OpFlags)(word & 0xff00);
 801
 802                                 ++ pc;
 803
 804                                 ignore = (flags & OpFlags.IgnoreCase) != 0;
 805
 806                                 // consume character: the direction of an In construct is
 807                                 // determined by the direction of its first op
 808
 809                                 if (!consumed) {
 810                                         if ((flags & OpFlags.RightToLeft) != 0) {
 811                                                 if (ptr <= 0)
 812                                                         return false;
 813
 814                                                 c = text[-- ptr];
 815                                         }
 816                                         else {
 817                                                 if (ptr >= text_end)
 818                                                         return false;
 819
 820                                                 c = text[ptr ++];
 821                                         }
 822
 823                                         if (ignore)
 824                                                 c = Char.ToLower (c);
 825
 826                                         consumed = true;
 827                                 }
 828
 829                                 // negate flag
 830
 831                                 negate = (flags & OpFlags.Negate) != 0;
 832
 833                                 // execute op
 834
 835                                 switch (op) {
 836                                 case OpCode.True:
 837                                         return true;
 838
 839                                 case OpCode.False:
 840                                         return false;
 841
 842                                 case OpCode.Character: {
 843                                         if (c == (char)program[pc ++])
 844                                                 return !negate;
 845                                         break;
 846                                 }
 847
 848                                 case OpCode.Category: {
 849                                         if (CategoryUtils.IsCategory ((Category)program[pc ++], c))
 850                                                 return !negate;
 851                                         break;
 852                                 }
 853
 854                                 case OpCode.NotCategory: {
 855                                         if (!CategoryUtils.IsCategory ((Category)program[pc ++], c))
 856                                                 return !negate;
 857                                         break;
 858                                 }
 859
 860                                 case OpCode.Range: {
 861                                         int lo = (char)program[pc ++];
 862                                         int hi = (char)program[pc ++];
 863                                         if (lo <= c && c <= hi)
 864                                                 return !negate;
 865                                         break;
 866                                 }
 867
 868                                 case OpCode.Set: {
 869                                         int lo = (char)program[pc ++];
 870                                         int len = (char)program[pc ++];
 871                                         int bits = pc;
 872                                         pc += len;
 873
 874                                         int i = (int)c - lo;
 875                                         if (i < 0 || i >= len << 4)
 876                                                 break;
 877
 878
 879                                         if ((program[bits + (i >> 4)] & (1 << (i & 0xf))) != 0)
 880                                                 return !negate;
 881                                         break;
 882                                 }
 883                                 }
 884                         } while (multi);
 885
 886                         return negate;
 887                 }
 888
 889                 private bool CheckComboMatch (List<List<JumpTestEntry>> TriedCombos, List<JumpTestEntry> JumpTestList, int pc, int ptr)
 890                 {
 891                         bool Match = false;
 892                         if (TriedCombos != null && TriedCombos.Count > 0)
 893                         {
 894                                 for (int i = 0;i < TriedCombos.Count;i++)
 895                                 {
 896                                         if ((TriedCombos[i] != null) &&
 897                                             (TriedCombos[i].Count > 0))
 898                                         {
 899                                                 int j = TriedCombos[i].Count - 1;
 900                                                 if ((TriedCombos[i][j].pc == pc) && (TriedCombos[i][j].ptr == ptr))
 901                                                 {
 902                                                         if (CheckSubCmb( TriedCombos, JumpTestList,
 903                                                               i,j,ref Match))
 904                                                         {
 905                                                                 return true;
 906                                                         }
 907                                                 }
 908                                         }
 909                                 }
 910                         }
 911                         return Match;
 912                 }
 913
 914
 915                 private bool CheckSubCmb(List<List<JumpTestEntry>> TriedCombos,
 916                     List<JumpTestEntry> JumpTestList,int i,int j,ref bool Match)
 917                 {
 918                         if ((JumpTestList.Count <= TriedCombos[i].Count-1))
 919                         {
 920                                 Match=false;
 921                                 if (TriedCombos[i].Count > 1)
 922                                 {
 923                                         for (j = 0;j < JumpTestList.Count;j++)
 924                                         {
 925                                                 if ((TriedCombos[i][j].pc == JumpTestList[j].pc) &&
 926                                                    (TriedCombos[i][j].ptr == JumpTestList[j].ptr))
 927                                                 {
 928                                                         Match = true;
 929                                                 }else{
 930                                                         Match = false;
 931                                                         break;
 932                                                 }
 933                                         }
 934                                         if (Match == true) {
 935                                                 //must shortcircuit
 936                                                 return Match;
 937
 938                                         }
 939                                 } else {
 940                                         Match = true;
 941                                         //must shortcircuit
 942                                         return Match;
 943                                 }
 944                         }
 945                         return Match;
 946                 }
 947                 private bool TryMatch (ref int ref_ptr, int pc, List<JumpTestEntry> JumpTestList,List<List<JumpTestEntry>> TriedCombos, bool BypassJumpTest) {
 948                         Reset ();
 949
 950                         int ptr = ref_ptr;
 951                         marks [groups [0]].Start = ptr;
 952                         if (Eval (Mode.Match, ref ptr, pc, JumpTestList, TriedCombos, BypassJumpTest)) {
 953                                 marks [groups [0]].End = ptr;
 954                                 ref_ptr = ptr;
 955                                 return true;
 956                         }
 957
 958                         return false;
 959                 }
 960
 961                 private bool IsPosition (Position pos, int ptr) {
 962                         switch (pos) {
 963                         case Position.Start: case Position.StartOfString:
 964                                 return ptr == 0;
 965
 966                         case Position.StartOfLine:
 967                                 return ptr == 0 || text[ptr - 1] == '\n';
 968
 969                         case Position.StartOfScan:
 970                                 return ptr == scan_ptr;
 971
 972                         case Position.End:
 973                                 return ptr == text_end ||
 974                                         (ptr == text_end - 1 && text[ptr] == '\n');
 975
 976                         case Position.EndOfLine:
 977                                 return ptr == text_end || text[ptr] == '\n';
 978
 979                         case Position.EndOfString:
 980                                 return ptr == text_end;
 981
 982                         case Position.Boundary:
 983                                 if (text_end == 0)
 984                                         return false;
 985
 986                                 if (ptr == 0)
 987                                         return IsWordChar (text[ptr]);
 988                                 else if (ptr == text_end)
 989                                         return IsWordChar (text[ptr - 1]);
 990                                 else
 991                                         return IsWordChar (text[ptr]) != IsWordChar (text[ptr - 1]);
 992
 993                         case Position.NonBoundary:
 994                                 if (text_end == 0)
 995                                         return false;
 996
 997                                 if (ptr == 0)
 998                                         return !IsWordChar (text[ptr]);
 999                                 else if (ptr == text_end)
1000                                         return !IsWordChar (text[ptr - 1]);
1001                                 else
1002                                         return IsWordChar (text[ptr]) == IsWordChar (text[ptr - 1]);
1003
1004                         default:
1005                                 return false;
1006                         }
1007                 }
1008
1009                 private bool IsWordChar (char c) {
1010                         return CategoryUtils.IsCategory (Category.Word, c);
1011                 }
1012
1013                 private string GetString (int pc) {
1014                         int len = program[pc + 1];
1015                         int str = pc + 2;
1016
1017                         char[] cs = new char[len];
1018                         for (int i = 0; i < len; ++ i)
1019                                 cs[i] = (char)program[str ++];
1020
1021                         return new string (cs);
1022                 }
1023
1024                 // capture management
1025
1026                 private void Open (int gid, int ptr) {
1027                         int m = groups [gid];
1028                         if (m < mark_start || marks [m].IsDefined) {
1029                                 m = CreateMark (m);
1030                                 groups [gid] = m;
1031                         }
1032
1033                         marks [m].Start = ptr;
1034                 }
1035
1036                 private void Close (int gid, int ptr) {
1037                         marks [groups [gid]].End = ptr;
1038                 }
1039
1040                 private bool Balance (int gid, int balance_gid, bool capture, int ptr) {
1041                         int b = groups [balance_gid];
1042
1043                         if(b == -1 || marks[b].Index < 0) {
1044                                 //Group not previously matched
1045                                 return false;
1046                         }
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);
1050                                 Close (gid, ptr);
1051                         }
1052
1053                         groups [balance_gid] = marks[b].Previous;
1054
1055                         return true;
1056                 }
1057
1058                 private int Checkpoint () {
1059                         mark_start = mark_end;
1060                         return mark_start;
1061                 }
1062
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) {
1066                                 int m = groups [i];
1067                                 while (cp <= m) {
1068                                         marks [m].Start = -1;
1069                                         m = marks [m].Previous;
1070                                 }
1071
1072                                 groups [i] = m;
1073                         }
1074                         mark_start = cp;
1075                 }
1076
1077                 private void ResetGroups () {
1078                         int n = groups.Length;
1079                         if (marks == null)
1080                                 marks = new Mark [n * 10];
1081
1082                         for (int i = 0; i < n; ++ i) {
1083                                 groups [i] = i;
1084
1085                                 marks [i].Start = -1;
1086                                 marks [i].End = -1;
1087                                 marks [i].Previous = -1;
1088                         }
1089
1090                         mark_start = 0;
1091                         mark_end = n;
1092                 }
1093
1094                 private int GetLastDefined (int gid) {
1095                         int m = groups [gid];
1096                         while (m >= 0 && !marks [m].IsDefined)
1097                                 m = marks [m].Previous;
1098
1099                         return m;
1100                 }
1101
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);
1106                                 marks = dest;
1107                         }
1108
1109                         int m = mark_end ++;
1110                         marks [m].Start = marks [m].End = -1;
1111                         marks [m].Previous = previous;
1112
1113                         return m;
1114                 }
1115
1116                 private void GetGroupInfo (int gid, out int first_mark_index, out int n_caps)
1117                 {
1118                         first_mark_index = -1;
1119                         n_caps = 0;
1120                         for (int m = groups [gid]; m >= 0; m = marks [m].Previous) {
1121                                 if (!marks [m].IsDefined)
1122                                         continue;
1123                                 if (first_mark_index < 0)
1124                                         first_mark_index = m;
1125                                 ++n_caps;
1126                         }
1127                 }
1128
1129                 private void PopulateGroup (Group g, int first_mark_index, int n_caps)
1130                 {
1131                         int i = 1;
1132                         for (int m = marks [first_mark_index].Previous; m >= 0; m = marks [m].Previous) {
1133                                 if (!marks [m].IsDefined)
1134                                         continue;
1135                                 Capture cap = new Capture (text, marks [m].Index, marks [m].Length);
1136                                 g.Captures.SetValue (cap, n_caps - 1 - i);
1137                                 ++i;
1138                         }
1139                 }
1140
1141                 private Match GenerateMatch (Regex regex)
1142                 {
1143                         int n_caps, first_mark_index;
1144                         Group g;
1145                         GetGroupInfo (0, out first_mark_index, out n_caps);
1146
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);
1150
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);
1154
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) {
1158                                         g = Group.Fail;
1159                                 } else {
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);
1162                                 }
1163                                 retval.Groups.SetValue (g, gid);
1164                         }
1165                         return retval;
1166                 }
1167
1168                 // interpreter attributes
1169
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
1177
1178                 // match state
1179
1180                 private int scan_ptr;                   // start of scan
1181
1182                 private RepeatContext repeat;           // current repeat context
1183                 private RepeatContext fast;             // fast repeat context
1184
1185                 // Repeat/Until handling
1186                 private IntStack stack = new IntStack (); // utility stack
1187                 private RepeatContext deep;             // points to the most-nested repeat context
1188
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
1192
1193                 private int[] groups;                   // current group definitions
1194
1195                 // private classes
1196
1197                 private struct IntStack {
1198                         int [] values;
1199                         int count;
1200                         public int Pop ()
1201                         {
1202                                 return values [--count];
1203                         }
1204                         public void Push (int value)
1205                         {
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;
1215                                 }
1216                                 values [count++] = value;
1217                         }
1218                         public int Top {
1219                                 get { return values [count - 1]; }
1220                         }
1221                         public int Count {
1222                                 get { return count; }
1223                                 set {
1224                                         if (value > count)
1225                                                 throw new SystemException ("can only truncate the stack");
1226                                         count = value;
1227                                 }
1228                         }
1229                 }
1230
1231                 private class RepeatContext {
1232                         public RepeatContext (RepeatContext previous, int min, int max, bool lazy, int expr_pc) {
1233                                 this.previous = previous;
1234                                 this.min = min;
1235                                 this.max = max;
1236                                 this.lazy = lazy;
1237                                 this.expr_pc = expr_pc;
1238
1239                                 this.start = -1;
1240                                 this.count = 0;
1241                         }
1242
1243                         public int Count {
1244                                 get { return count; }
1245                                 set { count = value; }
1246                         }
1247
1248                         public int Start {
1249                                 get { return start; }
1250                                 set { start = value; }
1251                         }
1252
1253                         public bool IsMinimum {
1254                                 get { return min <= count; }
1255                         }
1256
1257                         public bool IsMaximum {
1258                                 get { return max <= count; }
1259                         }
1260
1261                         public bool IsLazy {
1262                                 get { return lazy; }
1263                         }
1264
1265                         public int Expression {
1266                                 get { return expr_pc; }
1267                         }
1268
1269                         public RepeatContext Previous {
1270                                 get { return previous; }
1271                         }
1272
1273                         private int start;
1274                         private int min, max;
1275                         private bool lazy;
1276                         private int expr_pc;
1277                         private RepeatContext previous;
1278
1279                         private int count;
1280                 }
1281
1282                 private enum Mode {
1283                         Search,
1284                         Match,
1285                         Count
1286                 }
1287         }
1288 }