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

   1 //\r
   2 // assembly:    System\r
   3 // namespace:   System.Text.RegularExpressions\r
   4 // file:        interpreter.cs\r
   5 //\r
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)\r
   7 //              (c) 2002\r
   8 \r
   9 using System;\r
  10 using System.Collections;\r
  11 using System.Diagnostics;\r
  12 using System.Globalization;\r
  13 \r
  14 namespace System.Text.RegularExpressions {\r
  15 \r
  16         class Interpreter : IMachine {\r
  17                 public Interpreter (ushort[] program) {\r
  18                         this.program = program;\r
  19                         this.qs = null;\r
  20 \r
  21                         // process info block\r
  22 \r
  23                         Debug.Assert ((OpCode)program[0] == OpCode.Info, "Regex", "Cant' find info block");\r
  24 \r
  25                         this.group_count = program[1] + 1;\r
  26                         this.match_min = program[2];\r
  27                         this.match_max = program[3];\r
  28 \r
  29                         // setup\r
  30 \r
  31                         this.program_start = 4;\r
  32                         this.groups = new int [group_count];\r
  33                 }\r
  34 \r
  35                 // IMachine implementation\r
  36 \r
  37                 public Match Scan (Regex regex, string text, int start, int end) {\r
  38                         this.text = text;\r
  39                         this.text_end = end;\r
  40                         this.scan_ptr = start;\r
  41 \r
  42                         if (Eval (Mode.Match, ref scan_ptr, program_start))\r
  43                                 return GenerateMatch (regex);\r
  44 \r
  45                         return Match.Empty;\r
  46                 }\r
  47 \r
  48                 // private methods\r
  49 \r
  50                 private void Reset () {\r
  51                         ResetGroups ();\r
  52                         fast = repeat = null;\r
  53                 }\r
  54 \r
  55                 private bool Eval (Mode mode, ref int ref_ptr, int pc) {\r
  56                         int ptr = ref_ptr;\r
  57                 Begin:\r
  58                         for (;;) {\r
  59                                 ushort word = program[pc];\r
  60                                 OpCode op = (OpCode)(word & 0x00ff);\r
  61                                 OpFlags flags = (OpFlags)(word & 0xff00);\r
  62 \r
  63                                 switch (op) {\r
  64                                 case OpCode.Anchor: {\r
  65                                         int skip = program[pc + 1];\r
  66                                         \r
  67                                         int anch_offset = program[pc + 2];\r
  68                                         bool anch_reverse = (flags & OpFlags.RightToLeft) != 0; \r
  69                                         int anch_ptr = anch_reverse ?  ptr - anch_offset  : ptr + anch_offset;\r
  70                                         int anch_end = text_end - match_min + anch_offset;      // maximum anchor position  \r
  71                                         \r
  72                                         \r
  73                                         int anch_begin =  0;\r
  74 \r
  75 \r
  76                                         // the general case for an anchoring expression is at the bottom, however we\r
  77                                         // do some checks for the common cases before to save processing time. the current\r
  78                                         // optimizer only outputs three types of anchoring expressions: fixed position,\r
  79                                         // fixed substring, and no anchor.\r
  80 \r
  81                                         OpCode anch_op = (OpCode)(program[pc + 3] & 0x00ff);                                    \r
  82                                         if (anch_op == OpCode.Position && skip == 6) {                          // position anchor\r
  83                                                 // Anchor\r
  84                                                 //      Position\r
  85                                                 //      True\r
  86 \r
  87                                                 switch ((Position)program[pc + 4]) {\r
  88                                                 case Position.StartOfString:                                                    \r
  89                                                         if (anch_reverse || anch_offset == 0) {\r
  90                                                                 ptr = anch_offset;\r
  91                                                                 if (TryMatch (ref ptr, pc + skip))\r
  92                                                                         goto Pass;\r
  93                                                         }\r
  94                                                         break;\r
  95                                                 \r
  96                                                 case Position.StartOfLine:\r
  97                                                                                                         \r
  98                                                          if (anch_ptr == 0) {\r
  99                                                                 ptr = 0;\r
 100                                                                 if (TryMatch (ref ptr, pc + skip))\r
 101                                                                         goto Pass;\r
 102                                                                 \r
 103                                                                 ++ anch_ptr;\r
 104                                                         }\r
 105 \r
 106                                                         while ((anch_reverse && anch_ptr >= 0) || (!anch_reverse && anch_ptr <= anch_end)) {  \r
 107                                                                 if (anch_ptr == 0 || text[anch_ptr - 1] == '\n') {\r
 108                                                                         if (anch_reverse)\r
 109                                                                                 ptr = anch_ptr == anch_end ? anch_ptr : anch_ptr + anch_offset;\r
 110                                                                         else\r
 111                                                                                 ptr = anch_ptr == 0 ? anch_ptr : anch_ptr - anch_offset;\r
 112                                                                         if (TryMatch (ref ptr, pc + skip))\r
 113                                                                                 goto Pass;\r
 114                                                                 }\r
 115                                                         \r
 116                                                                 if (anch_reverse)\r
 117                                                                         -- anch_ptr;\r
 118                                                                 else\r
 119                                                                         ++ anch_ptr;\r
 120                                                         }\r
 121                                                         break;\r
 122                                                 \r
 123                                                 case Position.StartOfScan:\r
 124                                                         if (anch_ptr == scan_ptr) {                                                     \r
 125                                                                 ptr = anch_reverse ? scan_ptr + anch_offset : scan_ptr - anch_offset;\r
 126                                                                 if (TryMatch (ref ptr, pc + skip))\r
 127                                                                         goto Pass;\r
 128                                                         }\r
 129                                                         break;\r
 130 \r
 131                                                 default:\r
 132                                                         // FIXME\r
 133                                                         break;\r
 134                                                 }\r
 135                                         }\r
 136                                         else if (qs != null ||\r
 137                                                 (anch_op == OpCode.String && skip == 6 + program[pc + 4])) {    // substring anchor\r
 138                                                 // Anchor\r
 139                                                 //      String\r
 140                                                 //      True\r
 141                                  \r
 142                                                 bool reverse = ((OpFlags)program[pc + 3] & OpFlags.RightToLeft) != 0;\r
 143                                                 string substring = GetString (pc + 3);\r
 144 \r
 145                                                 if (qs == null) {\r
 146                                                         bool ignore = ((OpFlags)program[pc + 3] & OpFlags.IgnoreCase) != 0;\r
 147 \r
 148                                                         qs = new QuickSearch (substring, ignore, reverse);\r
 149                                                 }\r
 150                                                 while ((anch_reverse && anch_ptr >= anch_begin) \r
 151                                                        || (!anch_reverse && anch_ptr <= anch_end)) {\r
 152 \r
 153                                                         if (reverse)    \r
 154                                                         {\r
 155                                                                 anch_ptr = qs.Search (text, anch_ptr, anch_begin);\r
 156                                                                 if (anch_ptr != -1)\r
 157                                                                         anch_ptr += substring.Length ;\r
 158                                                                 \r
 159                                                         }\r
 160                                                         else\r
 161                                                                 anch_ptr = qs.Search (text, anch_ptr, anch_end);\r
 162                                                         if (anch_ptr < 0)\r
 163                                                                 break;\r
 164 \r
 165                                                         ptr = reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;\r
 166                                                         if (TryMatch (ref ptr, pc + skip))\r
 167                                                                 goto Pass;\r
 168 \r
 169                                                         if (reverse)\r
 170                                                                 anch_ptr -= 2;\r
 171                                                         else \r
 172                                                                 ++ anch_ptr;\r
 173                                                 }\r
 174                                         }\r
 175                                         else if (anch_op == OpCode.True) {                                      // no anchor\r
 176                                                 // Anchor\r
 177                                                 //      True\r
 178 \r
 179                                         \r
 180                                                 while ((anch_reverse && anch_ptr >= anch_begin) \r
 181                                                        || (!anch_reverse && anch_ptr <= anch_end)) {\r
 182 \r
 183                                                         ptr = anch_ptr;\r
 184                                                         if (TryMatch (ref ptr, pc + skip))\r
 185                                                                 goto Pass;\r
 186                                                         if (anch_reverse)\r
 187                                                                 -- anch_ptr;\r
 188                                                         else \r
 189                                                                 ++ anch_ptr;\r
 190                                                 }\r
 191                                         }\r
 192                                         else {                                                                  // general case\r
 193                                                 // Anchor\r
 194                                                 //      <expr>\r
 195                                                 //      True\r
 196 \r
 197                                                 while ((anch_reverse && anch_ptr >= anch_begin) \r
 198                                                        || (!anch_reverse && anch_ptr <= anch_end)) {\r
 199 \r
 200                                                         ptr = anch_ptr;\r
 201                                                         if (Eval (Mode.Match, ref ptr, pc + 3)) {\r
 202                                                                 // anchor expression passed: try real expression at the correct offset\r
 203 \r
 204                                                                 ptr = anch_reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;\r
 205                                                                 if (TryMatch (ref ptr, pc + skip))\r
 206                                                                         goto Pass;\r
 207                                                         }\r
 208 \r
 209                                                     if (anch_reverse)\r
 210                                                                 -- anch_ptr;\r
 211                                                         else \r
 212                                                                 ++ anch_ptr;\r
 213                                                 }\r
 214                                         }\r
 215 \r
 216                                         goto Fail;\r
 217                                 }\r
 218                                 \r
 219                                 case OpCode.False: {\r
 220                                         goto Fail;\r
 221                                 }\r
 222 \r
 223                                 case OpCode.True: {\r
 224                                         goto Pass;\r
 225                                 }\r
 226 \r
 227                                 case OpCode.Position: {\r
 228                                         if (!IsPosition ((Position)program[pc + 1], ptr))\r
 229                                                 goto Fail;\r
 230                                         pc += 2;\r
 231                                         break;\r
 232                                 }\r
 233 \r
 234                                 case OpCode.String: {\r
 235                                         bool reverse = (flags & OpFlags.RightToLeft) != 0;\r
 236                                         bool ignore = (flags & OpFlags.IgnoreCase) != 0;\r
 237                                         int len = program[pc + 1];\r
 238 \r
 239                                         if (reverse) {\r
 240                                                 ptr -= len;\r
 241                                                 if (ptr < 0)\r
 242                                                         goto Fail;\r
 243                                         }\r
 244                                         else \r
 245                                         if (ptr + len > text_end)\r
 246                                                 goto Fail;\r
 247 \r
 248                                         pc += 2;\r
 249                                         for (int i = 0; i < len; ++ i) {\r
 250                                                 char c = text[ptr + i];\r
 251                                                 if (ignore)\r
 252                                                         c = Char.ToLower (c);\r
 253 \r
 254                                                 if (c != (char)program[pc ++])\r
 255                                                         goto Fail;\r
 256                                         }\r
 257 \r
 258                                         if (!reverse)\r
 259                                                 ptr += len;\r
 260                                         break;\r
 261                                 }\r
 262 \r
 263                                 case OpCode.Reference: {\r
 264                                         bool reverse = (flags & OpFlags.RightToLeft) != 0;\r
 265                                         bool ignore = (flags & OpFlags.IgnoreCase) != 0;\r
 266                                         int m = GetLastDefined (program [pc + 1]);\r
 267                                         if (m < 0)\r
 268                                                 goto Fail;\r
 269 \r
 270                                         int str = marks [m].Index;\r
 271                                         int len = marks [m].Length;\r
 272 \r
 273                                         if (reverse) {\r
 274                                                 ptr -= len;\r
 275                                                 if (ptr < 0)\r
 276                                                         goto Fail;\r
 277                                         }\r
 278                                         else if (ptr + len > text_end)\r
 279                                                 goto Fail;\r
 280 \r
 281                                         pc += 2;\r
 282                                         for (int i = 0; i < len; ++ i) {\r
 283                                                 if (ignore) {\r
 284                                                         if (Char.ToLower (text[ptr + i]) != Char.ToLower (text[str + i]))\r
 285                                                                 goto Fail;\r
 286                                                 }\r
 287                                                 else {\r
 288                                                         if (text[ptr + i] != text[str + i])\r
 289                                                                 goto Fail;\r
 290                                                 }\r
 291                                         }\r
 292 \r
 293                                         if (!reverse)\r
 294                                                 ptr += len;\r
 295                                         break;\r
 296                                 }\r
 297 \r
 298                                 case OpCode.Character: case OpCode.Category:\r
 299                                 case OpCode.Range: case OpCode.Set: {\r
 300                                         if (!EvalChar (mode, ref ptr, ref pc, false))\r
 301                                                 goto Fail;\r
 302                                         break;\r
 303                                 }\r
 304 \r
 305                                 case OpCode.In: {\r
 306                                         int target = pc + program[pc + 1];\r
 307                                         pc += 2;\r
 308                                         if (!EvalChar (mode, ref ptr, ref pc, true))\r
 309                                                 goto Fail;\r
 310 \r
 311                                         pc = target;\r
 312                                         break;\r
 313                                 }\r
 314 \r
 315                                 case OpCode.Open: {\r
 316                                         Open (program[pc + 1], ptr);\r
 317                                         pc += 2;\r
 318                                         break;\r
 319                                 }\r
 320 \r
 321                                 case OpCode.Close: {\r
 322                                         Close (program[pc + 1], ptr);\r
 323                                         pc += 2;\r
 324                                         break;\r
 325                                 }\r
 326 \r
 327                                 case OpCode.Balance: {\r
 328                                         Balance (program[pc + 1], program[pc + 2], ptr);\r
 329                                         break;\r
 330                                 }\r
 331 \r
 332                                 case OpCode.IfDefined: {\r
 333                                         int m = GetLastDefined (program [pc + 2]);\r
 334                                         if (m < 0)\r
 335                                                 pc += program[pc + 1];\r
 336                                         else\r
 337                                                 pc += 3;\r
 338                                         break;\r
 339                                 }\r
 340 \r
 341                                 case OpCode.Sub: {\r
 342                                         if (!Eval (Mode.Match, ref ptr, pc + 2))\r
 343                                                 goto Fail;\r
 344 \r
 345                                         pc += program[pc + 1];\r
 346                                         break;\r
 347                                 }\r
 348 \r
 349                                 case OpCode.Test: {\r
 350                                         int cp = Checkpoint ();\r
 351                                         int test_ptr = ptr;\r
 352                                         if (Eval (Mode.Match, ref test_ptr, pc + 3))\r
 353                                                 pc += program[pc + 1];\r
 354                                         else {\r
 355                                                 Backtrack (cp);\r
 356                                                 pc += program[pc + 2];\r
 357                                         }\r
 358                                         break;\r
 359                                 }\r
 360 \r
 361                                 case OpCode.Branch: {\r
 362                                         OpCode branch_op;\r
 363                                         do {\r
 364                                                 int cp = Checkpoint ();\r
 365                                                 if (Eval (Mode.Match, ref ptr, pc + 2))\r
 366                                                         goto Pass;\r
 367                                                 \r
 368                                                 Backtrack (cp);\r
 369                                                 \r
 370                                                 pc += program[pc + 1];\r
 371                                                 branch_op = (OpCode)(program[pc] & 0xff);\r
 372                                         } while (branch_op != OpCode.False);\r
 373 \r
 374                                         goto Fail;\r
 375                                 }\r
 376 \r
 377                                 case OpCode.Jump: {\r
 378                                         pc += program[pc + 1];\r
 379                                         break;\r
 380                                 }\r
 381 \r
 382                                 case OpCode.Repeat: {\r
 383                                         this.repeat = new RepeatContext (\r
 384                                                 this.repeat,                    // previous context\r
 385                                                 program[pc + 2],                // minimum\r
 386                                                 program[pc + 3],                // maximum\r
 387                                                 (flags & OpFlags.Lazy) != 0,    // lazy\r
 388                                                 pc + 4                          // subexpression\r
 389                                         );\r
 390 \r
 391                                         if (Eval (Mode.Match, ref ptr, pc + program[pc + 1]))\r
 392                                                 goto Pass;\r
 393                                         else {\r
 394                                                 this.repeat = this.repeat.Previous;\r
 395                                                 goto Fail;\r
 396                                         }\r
 397                                 }\r
 398 \r
 399                                 case OpCode.Until: {\r
 400                                         RepeatContext current = this.repeat;\r
 401                                         int start = current.Start;\r
 402 \r
 403                                         if (!current.IsMinimum) {\r
 404                                                 ++ current.Count;\r
 405                                                 current.Start = ptr;\r
 406                                                 if (Eval (Mode.Match, ref ptr, repeat.Expression))\r
 407                                                         goto Pass;\r
 408 \r
 409                                                 current.Start = start;\r
 410                                                 -- current.Count;\r
 411                                                 goto Fail;\r
 412                                         }\r
 413 \r
 414                                         if (ptr == current.Start) {\r
 415                                                 // degenerate match ... match tail or fail\r
 416 \r
 417                                                 this.repeat = current.Previous;\r
 418                                                 if (Eval (Mode.Match, ref ptr, pc + 1))\r
 419                                                         goto Pass;\r
 420                                         \r
 421                                                 this.repeat = current;\r
 422                                                 goto Fail;\r
 423                                         }\r
 424 \r
 425                                         if (current.IsLazy) {\r
 426                                                 // match tail first ...\r
 427 \r
 428                                                 this.repeat = current.Previous;\r
 429                                                 int cp = Checkpoint ();\r
 430                                                 if (Eval (Mode.Match, ref ptr, pc + 1))\r
 431                                                         goto Pass;\r
 432 \r
 433                                                 Backtrack (cp);\r
 434 \r
 435                                                 // ... then match more\r
 436 \r
 437                                                 this.repeat = current;\r
 438                                                 if (!current.IsMaximum) {\r
 439                                                         ++ current.Count;\r
 440                                                         current.Start = ptr;\r
 441                                                         if (Eval (Mode.Match, ref ptr, current.Expression))\r
 442                                                                 goto Pass;\r
 443 \r
 444                                                         current.Start = start;\r
 445                                                         -- current.Count;\r
 446                                                         goto Fail;\r
 447                                                 }\r
 448 \r
 449                                                 return false;\r
 450                                         }\r
 451                                         else {\r
 452                                                 // match more first ...\r
 453 \r
 454                                                 if (!current.IsMaximum) {\r
 455                                                         int cp = Checkpoint ();\r
 456                                                         ++ current.Count;\r
 457                                                         current.Start = ptr;\r
 458                                                         if (Eval (Mode.Match, ref ptr, current.Expression))\r
 459                                                                 goto Pass;\r
 460 \r
 461                                                         current.Start = start;\r
 462                                                         -- current.Count;\r
 463                                                         Backtrack (cp);\r
 464                                                 }\r
 465 \r
 466                                                 // ... then match tail\r
 467 \r
 468                                                 this.repeat = current.Previous;\r
 469                                                 if (Eval (Mode.Match, ref ptr, pc + 1))\r
 470                                                         goto Pass;\r
 471 \r
 472                                                 this.repeat = current;\r
 473                                                 goto Fail;\r
 474                                         }\r
 475                                 }\r
 476 \r
 477                                 case OpCode.FastRepeat: {\r
 478                                         this.fast = new RepeatContext (\r
 479                                                 fast,\r
 480                                                 program[pc + 2],                // minimum\r
 481                                                 program[pc + 3],                // maximum\r
 482                                                 (flags & OpFlags.Lazy) != 0,    // lazy\r
 483                                                 pc + 4                          // subexpression\r
 484                                         );\r
 485                                         fast.Start = ptr;\r
 486 \r
 487                                         int cp = Checkpoint ();\r
 488 \r
 489                                         pc += program[pc + 1];          // tail expression\r
 490                                         ushort tail_word = program[pc];\r
 491 \r
 492                                         int c1, c2;                     // first character of tail operator\r
 493                                         int coff;                       // 0 or -1 depending on direction\r
 494 \r
 495                                         OpCode tail_op = (OpCode)(tail_word & 0xff);\r
 496                                         if (tail_op == OpCode.Character || tail_op == OpCode.String) {\r
 497                                                 OpFlags tail_flags = (OpFlags)(tail_word & 0xff00);\r
 498 \r
 499                                                 if (tail_op == OpCode.String)\r
 500                                                 {\r
 501                                                         int offset = 0;\r
 502                                                 \r
 503                                                         if ((tail_flags & OpFlags.RightToLeft) != 0)\r
 504                                                         {\r
 505                                                                 offset = program[pc + 1] - 1 ;\r
 506                                                         }\r
 507                                                           \r
 508                                                         c1 = program[pc + 2 + offset];                          // first char of string\r
 509                                                 }\r
 510                                                 else\r
 511                                                         c1 = program[pc + 1];                           // character\r
 512                                                 \r
 513                                                 if ((tail_flags & OpFlags.IgnoreCase) != 0)\r
 514                                                         c2 = Char.ToUpper ((char)c1);                   // ignore case\r
 515                                                 else\r
 516                                                         c2 = c1;\r
 517 \r
 518                                                 if ((tail_flags & OpFlags.RightToLeft) != 0)\r
 519                                                         coff = -1;                                      // reverse\r
 520                                                 else\r
 521                                                         coff = 0;\r
 522                                         }\r
 523                                         else {\r
 524                                                 c1 = c2 = -1;\r
 525                                                 coff = 0;\r
 526                                         }\r
 527 \r
 528                                         if (fast.IsLazy) {\r
 529                                                 if (!fast.IsMinimum && !Eval (Mode.Count, ref ptr, fast.Expression)) {\r
 530                                                         //Console.WriteLine ("lazy fast: failed mininum.");\r
 531                                                         fast = fast.Previous;\r
 532                                                         goto Fail;\r
 533                                                 }\r
 534                                                 \r
 535                                                 while (true) {\r
 536                                                         int p = ptr + coff;\r
 537                                                         if ((c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) &&\r
 538                                                             Eval (Mode.Match, ref ptr, pc))\r
 539                                                                 break;\r
 540 \r
 541                                                         if (fast.IsMaximum) {\r
 542                                                                 //Console.WriteLine ("lazy fast: failed with maximum.");\r
 543                                                                 fast = fast.Previous;\r
 544                                                                 goto Fail;\r
 545                                                         }\r
 546 \r
 547                                                         Backtrack (cp);\r
 548                                                         if (!Eval (Mode.Count, ref ptr, fast.Expression)) {\r
 549                                                                 //Console.WriteLine ("lazy fast: no more.");\r
 550                                                                 fast = fast.Previous;\r
 551                                                                 goto Fail;\r
 552                                                         }\r
 553                                                 }\r
 554                                                 fast = fast.Previous;\r
 555                                                 goto Pass;\r
 556                                         }\r
 557                                         else {\r
 558                                                 if (!Eval (Mode.Count, ref ptr, fast.Expression)) {\r
 559                                                         fast = fast.Previous;\r
 560                                                         goto Fail;\r
 561                                                 }\r
 562                                         \r
 563                                                 int width;\r
 564                                                 if (fast.Count > 0)\r
 565                                                         width = (ptr - fast.Start) / fast.Count;\r
 566                                                 else\r
 567                                                         width = 0;\r
 568 \r
 569                                                 while (true) {\r
 570                                                         int p = ptr + coff;\r
 571                                                         if ((c1 < 0 || (p >= 0 && p < text_end && (c1 == text[p] || c2 == text[p]))) &&\r
 572                                                             Eval (Mode.Match, ref ptr, pc))\r
 573                                                                 break;\r
 574 \r
 575                                                         -- fast.Count;\r
 576                                                         if (!fast.IsMinimum) {\r
 577                                                                 fast = fast.Previous;\r
 578                                                                 goto Fail;\r
 579                                                         }\r
 580 \r
 581                                                         ptr -= width;\r
 582                                                         Backtrack (cp);\r
 583                                                 }\r
 584                                                 fast = fast.Previous;\r
 585                                                 goto Pass;\r
 586                                         }\r
 587                                 }\r
 588 \r
 589                                 case OpCode.Info: {\r
 590                                         Debug.Assert (false, "Regex", "Info block found in pattern");\r
 591                                         goto Fail;\r
 592                                 }\r
 593                                 }\r
 594                         }\r
 595                 Pass:\r
 596                         ref_ptr = ptr;\r
 597 \r
 598                         switch (mode) {\r
 599                         case Mode.Match:\r
 600                                 return true;\r
 601 \r
 602                         case Mode.Count: {\r
 603                                 ++ fast.Count;\r
 604                                 if (fast.IsMaximum || (fast.IsLazy && fast.IsMinimum))\r
 605                                         return true;\r
 606 \r
 607                                 pc = fast.Expression;\r
 608                                 goto Begin;\r
 609                         }\r
 610                         }\r
 611 \r
 612                 Fail:\r
 613                         switch (mode) {\r
 614                         case Mode.Match:\r
 615                                 return false;\r
 616 \r
 617                         case Mode.Count: {\r
 618                                 if (!fast.IsLazy && fast.IsMinimum)\r
 619                                         return true;\r
 620 \r
 621                                 ref_ptr = fast.Start;\r
 622                                 return false;\r
 623                         }\r
 624                         }\r
 625 \r
 626                         return false;\r
 627                 }\r
 628 \r
 629                 private bool EvalChar (Mode mode, ref int ptr, ref int pc, bool multi) {\r
 630                         bool consumed = false;\r
 631                         char c = '\0';\r
 632                         bool negate;\r
 633                         bool ignore;\r
 634                 \r
 635                         do {\r
 636                                 ushort word = program[pc];\r
 637                                 OpCode op = (OpCode)(word & 0x00ff);\r
 638                                 OpFlags flags = (OpFlags)(word & 0xff00);\r
 639 \r
 640                                 ++ pc;\r
 641 \r
 642                                 ignore = (flags & OpFlags.IgnoreCase) != 0;\r
 643                                 \r
 644                                 // consume character: the direction of an In construct is\r
 645                                 // determined by the direction of its first op\r
 646 \r
 647                                 if (!consumed) {\r
 648                                         if ((flags & OpFlags.RightToLeft) != 0) {\r
 649                                                 if (ptr <= 0)\r
 650                                                         return false;\r
 651 \r
 652                                                 c = text[-- ptr];\r
 653                                         }\r
 654                                         else {\r
 655                                                 if (ptr >= text_end)\r
 656                                                         return false;\r
 657 \r
 658                                                 c = text[ptr ++];\r
 659                                         }\r
 660 \r
 661                                         if (ignore)\r
 662                                                 c = Char.ToLower (c);\r
 663 \r
 664                                         consumed = true;\r
 665                                 }\r
 666 \r
 667                                 // negate flag\r
 668 \r
 669                                 negate = (flags & OpFlags.Negate) != 0;\r
 670 \r
 671                                 // execute op\r
 672                                 \r
 673                                 switch (op) {\r
 674                                 case OpCode.True:\r
 675                                         return true;\r
 676 \r
 677                                 case OpCode.False:\r
 678                                         return false;\r
 679                                 \r
 680                                 case OpCode.Character: {\r
 681                                         if (c == (char)program[pc ++])\r
 682                                                 return !negate;\r
 683                                         break;\r
 684                                 }\r
 685 \r
 686                                 case OpCode.Category: {\r
 687                                         if (CategoryUtils.IsCategory ((Category)program[pc ++], c))\r
 688                                                 return !negate;\r
 689 \r
 690                                         break;\r
 691                                 }\r
 692                                 \r
 693                                 case OpCode.Range: {\r
 694                                         int lo = (char)program[pc ++];\r
 695                                         int hi = (char)program[pc ++];\r
 696                                         if (lo <= c && c <= hi)\r
 697                                                 return !negate;\r
 698                                         break;\r
 699                                 }\r
 700 \r
 701                                 case OpCode.Set: {\r
 702                                         int lo = (char)program[pc ++];\r
 703                                         int len = (char)program[pc ++];\r
 704                                         int bits = pc;\r
 705                                         pc += len;\r
 706 \r
 707                                         int i = (int)c - lo;\r
 708                                         if (i < 0 || i >= len << 4)\r
 709                                                 break;\r
 710                                                 \r
 711 \r
 712                                         if ((program[bits + (i >> 4)] & (1 << (i & 0xf))) != 0)\r
 713                                                 return !negate;\r
 714                                         break;\r
 715                                 }\r
 716                                 }\r
 717                         } while (multi);\r
 718 \r
 719                         return negate;\r
 720                 }\r
 721 \r
 722                 private bool TryMatch (ref int ref_ptr, int pc) {\r
 723                         Reset ();\r
 724                         \r
 725                         int ptr = ref_ptr;\r
 726                         marks [groups [0]].Start = ptr;\r
 727                         if (Eval (Mode.Match, ref ptr, pc)) {\r
 728                                 marks [groups [0]].End = ptr;\r
 729                                 ref_ptr = ptr;\r
 730                                 return true;\r
 731                         }\r
 732 \r
 733                         return false;\r
 734                 }\r
 735                 \r
 736                 private bool IsPosition (Position pos, int ptr) {\r
 737                         switch (pos) {\r
 738                         case Position.Start: case Position.StartOfString:\r
 739                                 return ptr == 0;\r
 740 \r
 741                         case Position.StartOfLine:\r
 742                                 return ptr == 0 || text[ptr - 1] == '\n';\r
 743                                 \r
 744                         case Position.StartOfScan:\r
 745                                 return ptr == scan_ptr;\r
 746                         \r
 747                         case Position.End:\r
 748                                 return ptr == text_end ||\r
 749                                         (ptr == text_end - 1 && text[ptr] == '\n');\r
 750 \r
 751                         case Position.EndOfLine:\r
 752                                 return ptr == text_end || text[ptr] == '\n';\r
 753                                 \r
 754                         case Position.EndOfString:\r
 755                                 return ptr == text_end;\r
 756                                 \r
 757                         case Position.Boundary:\r
 758                                 if (text_end == 0)\r
 759                                         return false;\r
 760 \r
 761                                 if (ptr == 0)\r
 762                                         return IsWordChar (text[ptr]);\r
 763                                 else if (ptr == text_end)\r
 764                                         return IsWordChar (text[ptr - 1]);\r
 765                                 else\r
 766                                         return IsWordChar (text[ptr]) != IsWordChar (text[ptr - 1]);\r
 767 \r
 768                         case Position.NonBoundary:\r
 769                                 if (text_end == 0)\r
 770                                         return false;\r
 771 \r
 772                                 if (ptr == 0)\r
 773                                         return !IsWordChar (text[ptr]);\r
 774                                 else if (ptr == text_end)\r
 775                                         return !IsWordChar (text[ptr - 1]);\r
 776                                 else\r
 777                                         return IsWordChar (text[ptr]) == IsWordChar (text[ptr - 1]);\r
 778                         \r
 779                         default:\r
 780                                 return false;\r
 781                         }\r
 782                 }\r
 783 \r
 784                 private bool IsWordChar (char c) {\r
 785                         return CategoryUtils.IsCategory (Category.Word, c);\r
 786                 }\r
 787 \r
 788                 private string GetString (int pc) {\r
 789                         int len = program[pc + 1];\r
 790                         int str = pc + 2;\r
 791 \r
 792                         char[] cs = new char[len];\r
 793                         for (int i = 0; i < len; ++ i)\r
 794                                 cs[i] = (char)program[str ++];\r
 795 \r
 796                         return new string (cs);\r
 797                 }\r
 798 \r
 799                 // capture management\r
 800 \r
 801                 private void Open (int gid, int ptr) {\r
 802                         int m = groups [gid];\r
 803                         if (m < mark_start || marks [m].IsDefined) {\r
 804                                 m = CreateMark (m);\r
 805                                 groups [gid] = m;\r
 806                         }\r
 807 \r
 808                         marks [m].Start = ptr;\r
 809                 }\r
 810 \r
 811                 private void Close (int gid, int ptr) {\r
 812                         marks [groups [gid]].End = ptr;\r
 813                 }\r
 814 \r
 815                 private void Balance (int gid, int balance_gid, int ptr) {\r
 816                         int b = groups [balance_gid];\r
 817                         Debug.Assert (marks [b].IsDefined, "Regex", "Balancing group not closed");\r
 818 \r
 819                         if (gid > 0) {\r
 820                                 Open (gid, marks [b].Index + marks [b].Length);\r
 821                                 Close (gid, ptr);\r
 822                         }\r
 823 \r
 824                         groups [balance_gid] = marks [b].Previous;\r
 825                 }\r
 826 \r
 827                 private int Checkpoint () {\r
 828                         mark_start = mark_end;\r
 829                         return mark_start;\r
 830                 }\r
 831 \r
 832                 private void Backtrack (int cp) {\r
 833                         Debug.Assert (cp > mark_start, "Regex", "Attempt to backtrack forwards");\r
 834 \r
 835                         for (int i = 0; i < groups.Length; ++ i) {\r
 836                                 int m = groups [i];\r
 837                                 while (cp <= m)\r
 838                                         m = marks [m].Previous;\r
 839 \r
 840                                 groups [i] = m;\r
 841                         }\r
 842                 }\r
 843 \r
 844                 private void ResetGroups () {\r
 845                         int n = groups.Length;\r
 846                         if (marks == null)\r
 847                                 marks = new Mark [n * 10];\r
 848 \r
 849                         for (int i = 0; i < n; ++ i) {\r
 850                                 groups [i] = i;\r
 851 \r
 852                                 marks [i].Start = -1;\r
 853                                 marks [i].End = -1;\r
 854                                 marks [i].Previous = -1;\r
 855                         }\r
 856                         \r
 857                         mark_start = 0;\r
 858                         mark_end = n;\r
 859                 }\r
 860 \r
 861                 private int GetLastDefined (int gid) {\r
 862                         int m = groups [gid];\r
 863                         while (m >= 0 && !marks [m].IsDefined)\r
 864                                 m = marks [m].Previous;\r
 865 \r
 866                         return m;\r
 867                 }\r
 868 \r
 869                 private int CreateMark (int previous) {\r
 870                         if (mark_end == marks.Length) {\r
 871                                 Mark [] dest = new Mark [marks.Length * 2];\r
 872                                 marks.CopyTo (dest, 0);\r
 873                                 marks = dest;\r
 874                         }\r
 875 \r
 876                         int m = mark_end ++;\r
 877                         marks [m].Start = marks [m].End = -1;\r
 878                         marks [m].Previous = previous;\r
 879 \r
 880                         return m;\r
 881                 }\r
 882 \r
 883                 private Match GenerateMatch (Regex regex) {\r
 884                         int[][] grps = new int[groups.Length][];\r
 885                         ArrayList caps = new ArrayList ();\r
 886 \r
 887                         for (int gid = 0; gid < groups.Length; ++ gid) {\r
 888                                 caps.Clear ();\r
 889                                 for (int m = groups[gid]; m >= 0; m = marks[m].Previous) {\r
 890                                         if (!marks[m].IsDefined)\r
 891                                                 continue;\r
 892                                         \r
 893                                         caps.Add (marks[m].Index);\r
 894                                         caps.Add (marks[m].Length);\r
 895                                 }\r
 896 \r
 897                                 grps[gid] = (int[])caps.ToArray (typeof (int));\r
 898                         }\r
 899 \r
 900                         return new Match (regex, this, text, text_end, grps);\r
 901                 }\r
 902 \r
 903                 // interpreter attributes\r
 904 \r
 905                 private ushort[] program;               // regex program\r
 906                 private int program_start;              // first instruction after info block\r
 907                 private string text;                    // input text\r
 908                 private int text_end;                   // end of input text (last character + 1)\r
 909                 private int group_count;                // number of capturing groups\r
 910                 private int match_min, match_max;       // match width information\r
 911                 private QuickSearch qs;                 // fast substring matcher\r
 912 \r
 913                 // match state\r
 914                 \r
 915                 private int scan_ptr;                   // start of scan\r
 916 \r
 917                 private RepeatContext repeat;           // current repeat context\r
 918                 private RepeatContext fast;             // fast repeat context\r
 919 \r
 920                 private Mark[] marks = null;            // mark stack\r
 921                 private int mark_start;                 // start of current checkpoint\r
 922                 private int mark_end;                   // end of checkpoint/next free mark\r
 923 \r
 924                 private int[] groups;                   // current group definitions\r
 925 \r
 926                 // private classes\r
 927 /*\r
 928                 private struct Mark {\r
 929                         public int Start, End;\r
 930                         public int Previous;\r
 931 \r
 932                         public bool IsDefined {\r
 933                                 get { return Start >= 0 && End >= 0; }\r
 934                         }\r
 935 \r
 936                         public int Index {\r
 937                                 get { return Start < End ? Start : End; }\r
 938                         }\r
 939 \r
 940                         public int Length {\r
 941                                 get { return Start < End ? End - Start : Start - End; }\r
 942                         }\r
 943                 }\r
 944 */\r
 945                 private class RepeatContext {\r
 946                         public RepeatContext (RepeatContext previous, int min, int max, bool lazy, int expr_pc) {\r
 947                                 this.previous = previous;\r
 948                                 this.min = min;\r
 949                                 this.max = max;\r
 950                                 this.lazy = lazy;\r
 951                                 this.expr_pc = expr_pc;\r
 952                                 \r
 953                                 this.start = -1;\r
 954                                 this.count = 0;\r
 955                         }\r
 956 \r
 957                         public int Count {\r
 958                                 get { return count; }\r
 959                                 set { count = value; }\r
 960                         }\r
 961 \r
 962                         public int Start {\r
 963                                 get { return start; }\r
 964                                 set { start = value; }\r
 965                         }\r
 966 \r
 967                         public bool IsMinimum {\r
 968                                 get { return min <= count; }\r
 969                         }\r
 970 \r
 971                         public bool IsMaximum {\r
 972                                 get { return max <= count; }\r
 973                         }\r
 974 \r
 975                         public bool IsLazy {\r
 976                                 get { return lazy; }\r
 977                         }\r
 978 \r
 979                         public int Expression {\r
 980                                 get { return expr_pc; }\r
 981                         }\r
 982 \r
 983                         public RepeatContext Previous {\r
 984                                 get { return previous; }\r
 985                         }\r
 986                 \r
 987                         private int start;\r
 988                         private int min, max;\r
 989                         private bool lazy;\r
 990                         private int expr_pc;\r
 991                         private RepeatContext previous;\r
 992 \r
 993                         private int count;\r
 994                 }\r
 995 \r
 996                 private enum Mode {\r
 997                         Search,\r
 998                         Match,\r
 999                         Count\r
1000                 }\r
1001         }\r
1002 }\r