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