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

   1
   2 using System;
   3 using System.Collections;
   4 using System.Globalization;
   5
   6 namespace System.Text.RegularExpressions {
   7
   8         internal delegate bool EvalDelegate (RxInterpreter interp, int strpos, ref int strpos_result);
   9
  10         sealed class RxInterpreter: BaseMachine {
  11                 byte[] program;
  12                 string str;
  13                 int string_start;
  14                 int string_end;
  15                 int group_count;
  16 //              int match_start;
  17                 int[] groups;
  18                 EvalDelegate eval_del; // optimized EvalByteCode method created by the CILCompiler
  19
  20                 Mark[] marks = null; // mark stack
  21                 int mark_start; // start of current checkpoint
  22                 int mark_end; // end of checkpoint/next free mark
  23
  24                 static readonly bool trace_rx = Environment.GetEnvironmentVariable ("RXD") != null;
  25
  26                 static int ReadInt (byte[] code, int pc)
  27                 {
  28                         int val = code [pc];
  29                         val |= code [pc + 1] << 8;
  30                         val |= code [pc + 2] << 16;
  31                         val |= code [pc + 3] << 24;
  32                         return val;
  33                 }
  34
  35                 public RxInterpreter (byte[] program, EvalDelegate eval_del)
  36                 {
  37                         this.program = program;
  38                         this.eval_del = eval_del;
  39                         group_count = 1 + (program [1] | (program [2] << 8));
  40                         groups = new int [group_count];
  41
  42                         ResetGroups ();
  43                 }
  44
  45                 public override Match Scan (Regex regex, string text, int start, int end) {
  46                         str = text;
  47                         string_start = start;
  48                         string_end = end;
  49                         int res = 0;
  50
  51                         bool match;
  52                         if (eval_del != null) {
  53                                 match = eval_del (this, start, ref res);
  54                         } else {
  55                                 match = EvalByteCode (11, start, ref res);
  56                         }
  57                         marks [groups [0]].End = res;
  58                         if (match) {
  59                                 return GenerateMatch (regex);
  60                                 //Match m = new Match (regex, this, text, end, 0, match_start, res - match_start);
  61                                 //return m;
  62                         }
  63                         return Match.Empty;
  64                 }
  65
  66                 // capture management
  67                 private void Open (int gid, int ptr) {
  68                         int m = groups [gid];
  69                         if (m < mark_start || marks [m].IsDefined) {
  70                                 m = CreateMark (m);
  71                                 groups [gid] = m;
  72                         }
  73
  74                         marks [m].Start = ptr;
  75                 }
  76
  77                 private void Close (int gid, int ptr) {
  78                         marks [groups [gid]].End = ptr;
  79                 }
  80 /*
  81                 private bool Balance (int gid, int balance_gid, bool capture, int ptr) {
  82                         int b = groups [balance_gid];
  83
  84                         if (b == -1 || marks [b].Index < 0) {
  85                                 //Group not previously matched
  86                                 return false;
  87                         }
  88                         if (gid > 0 && capture){
  89                                 Open (gid, marks [b].Index + marks [b].Length);
  90                                 Close (gid, ptr);
  91                         }
  92
  93                         groups [balance_gid] = marks[b].Previous;
  94                         return true;
  95                 }
  96 */
  97                 private int Checkpoint () {
  98                         mark_start = mark_end;
  99                         return mark_start;
 100                 }
 101
 102                 private void Backtrack (int cp) {
 103                         for (int i = 0; i < groups.Length; ++ i) {
 104                                 int m = groups [i];
 105                                 while (cp <= m)
 106                                         m = marks [m].Previous;
 107                                 groups [i] = m;
 108                         }
 109                 }
 110
 111                 private void ResetGroups () {
 112                         int n = groups.Length;
 113                         if (marks == null)
 114                                 marks = new Mark [n * 10];
 115
 116                         for (int i = 0; i < n; ++ i) {
 117                                 groups [i] = i;
 118
 119                                 marks [i].Start = -1;
 120                                 marks [i].End = -1;
 121                                 marks [i].Previous = -1;
 122                         }
 123                         mark_start = 0;
 124                         mark_end = n;
 125                 }
 126
 127                 private int GetLastDefined (int gid) {
 128                         int m = groups [gid];
 129                         while (m >= 0 && !marks [m].IsDefined)
 130                                 m = marks [m].Previous;
 131
 132                         return m;
 133                 }
 134
 135                 private int CreateMark (int previous) {
 136                         if (mark_end == marks.Length) {
 137                                 Mark [] dest = new Mark [marks.Length * 2];
 138                                 marks.CopyTo (dest, 0);
 139                                 marks = dest;
 140                         }
 141
 142                         int m = mark_end ++;
 143                         marks [m].Start = marks [m].End = -1;
 144                         marks [m].Previous = previous;
 145
 146                         return m;
 147                 }
 148
 149                 private void GetGroupInfo (int gid, out int first_mark_index, out int n_caps)
 150                 {
 151                         first_mark_index = -1;
 152                         n_caps = 0;
 153                         for (int m = groups [gid]; m >= 0; m = marks [m].Previous) {
 154                                 if (!marks [m].IsDefined)
 155                                         continue;
 156                                 if (first_mark_index < 0)
 157                                         first_mark_index = m;
 158                                 ++n_caps;
 159                         }
 160                 }
 161
 162                 private void PopulateGroup (Group g, int first_mark_index, int n_caps)
 163                 {
 164                         int i = 1;
 165                         for (int m = marks [first_mark_index].Previous; m >= 0; m = marks [m].Previous) {
 166                                 if (!marks [m].IsDefined)
 167                                         continue;
 168                                 Capture cap = new Capture (str, marks [m].Index, marks [m].Length);
 169                                 g.Captures.SetValue (cap, n_caps - 1 - i);
 170                                 ++i;
 171                         }
 172                 }
 173
 174                 private Match GenerateMatch (Regex regex)
 175                 {
 176                         int n_caps, first_mark_index;
 177                         Group g;
 178                         GetGroupInfo (0, out first_mark_index, out n_caps);
 179
 180                         // Avoid fully populating the Match instance if not needed
 181                         if (!needs_groups_or_captures)
 182                                 return new Match (regex, this, str, string_end, 0, marks [first_mark_index].Index, marks [first_mark_index].Length);
 183
 184                         Match retval = new Match (regex, this, str, string_end, groups.Length,
 185                                                   marks [first_mark_index].Index, marks [first_mark_index].Length, n_caps);
 186                         PopulateGroup (retval, first_mark_index, n_caps);
 187
 188                         for (int gid = 1; gid < groups.Length; ++ gid) {
 189                                 GetGroupInfo (gid, out first_mark_index, out n_caps);
 190                                 if (first_mark_index < 0) {
 191                                         g = Group.Fail;
 192                                 } else {
 193                                         g = new Group (str, marks [first_mark_index].Index, marks [first_mark_index].Length, n_caps);
 194                                         PopulateGroup (g, first_mark_index, n_caps);
 195                                 }
 196                                 retval.Groups.SetValue (g, gid);
 197                         }
 198                         return retval;
 199                 }
 200
 201                 // used by the IL backend
 202                 void SetStartOfMatch (int pos)
 203                 {
 204                         marks [groups [0]].Start = pos;
 205                 }
 206
 207                 static bool IsWordChar (char c)
 208                 {
 209                         return Char.IsLetterOrDigit (c) || Char.GetUnicodeCategory (c) == UnicodeCategory.ConnectorPunctuation;
 210                 }
 211
 212                 bool EvalByteCode (int pc, int strpos, ref int strpos_result)
 213                 {
 214                         // luckily the IL engine can deal with char_group_end at compile time
 215                         // this code offset needs to be checked only in opcodes that handle
 216                         // a single char and that are included in a TestCharGroup expression:
 217                         // the engine is supposed to jump to this offset as soons as the
 218                         // first opcode in the expression matches
 219                         // The code pattern becomes:
 220                         // on successfull match: check if char_group_end is nonzero and jump to
 221                         // test_char_group_passed after adjusting strpos
 222                         // on failure: try the next expression by simply advancing pc
 223                         int char_group_end = 0;
 224                         int length, start, end;
 225                         while (true) {
 226                                 if (trace_rx)
 227                                         Console.WriteLine ("evaluating: {0} at pc: {1}, strpos: {2}, cge: {3}", (RxOp)program [pc], pc, strpos, char_group_end);
 228                                 switch ((RxOp)program [pc]) {
 229                                 case RxOp.True:
 230                                         if (char_group_end != 0) {
 231                                                 pc = char_group_end;
 232                                                 char_group_end = 0;
 233                                                 continue;
 234                                         }
 235                                         strpos_result = strpos;
 236                                         return true;
 237                                 case RxOp.False:
 238                                         return false;
 239                                 case RxOp.AnyPosition:
 240                                         pc++;
 241                                         continue;
 242                                 case RxOp.StartOfString:
 243                                         if (strpos != 0)
 244                                                 return false;
 245                                         pc++;
 246                                         continue;
 247                                 case RxOp.StartOfLine:
 248                                         if (strpos == 0 || str [strpos - 1] == '\n') {
 249                                                 pc++;
 250                                                 continue;
 251                                         }
 252                                         return false;
 253                                 case RxOp.StartOfScan:
 254                                         if (strpos != string_start)
 255                                                 return false;
 256                                         pc++;
 257                                         continue;
 258                                 case RxOp.End:
 259                                         if (strpos == string_end || (strpos == string_end - 1 && str [strpos] == '\n')) {
 260                                                 pc++;
 261                                                 continue;
 262                                         }
 263                                         return false;
 264                                 case RxOp.EndOfString:
 265                                         if (strpos != string_end)
 266                                                 return false;
 267                                         pc++;
 268                                         continue;
 269                                 case RxOp.EndOfLine:
 270                                         if (strpos == string_end || str [strpos] == '\n') {
 271                                                 pc++;
 272                                                 continue;
 273                                         }
 274                                         return false;
 275                                 case RxOp.WordBoundary:
 276                                         if (string_end == 0)
 277                                                 return false;
 278                                         if (strpos == 0) {
 279                                                 if (IsWordChar (str [strpos])) {
 280                                                         pc++;
 281                                                         continue;
 282                                                 }
 283                                         } else if (strpos == string_end) {
 284                                                 if (IsWordChar (str [strpos - 1])) {
 285                                                         pc++;
 286                                                         continue;
 287                                                 }
 288                                         } else {
 289                                                 if (IsWordChar (str [strpos]) != IsWordChar (str [strpos - 1])) {
 290                                                         pc++;
 291                                                         continue;
 292                                                 }
 293                                         }
 294                                         return false;
 295                                 case RxOp.NoWordBoundary:
 296                                         if (string_end == 0)
 297                                                 return false;
 298                                         if (strpos == 0) {
 299                                                 if (!IsWordChar (str [strpos])) {
 300                                                         pc++;
 301                                                         continue;
 302                                                 }
 303                                         } else if (strpos == string_end) {
 304                                                 if (!IsWordChar (str [strpos - 1])) {
 305                                                         pc++;
 306                                                         continue;
 307                                                 }
 308                                         } else {
 309                                                 if (IsWordChar (str [strpos]) == IsWordChar (str [strpos - 1])) {
 310                                                         pc++;
 311                                                         continue;
 312                                                 }
 313                                         }
 314                                         return false;
 315                                 case RxOp.Anchor:
 316                                         // FIXME: test anchor
 317                                         length = program [pc + 3] | (program [pc + 4] << 8);
 318                                         pc += program [pc + 1] | (program [pc + 2] << 8);
 319                                         // it's important to test also the end of the string
 320                                         // position for things like: "" =~ /$/
 321                                         end = string_end + 1;
 322                                         while (strpos < end) {
 323                                                 int res = strpos;
 324                                                 if (groups.Length > 1) {
 325                                                         ResetGroups ();
 326                                                         marks [groups [0]].Start = strpos;
 327                                                 }
 328                                                 if (EvalByteCode (pc, strpos, ref res)) {
 329 //                                                      match_start = strpos;
 330                                                         marks [groups [0]].Start = strpos;
 331                                                         if (groups.Length > 1)
 332                                                                 marks [groups [0]].End = res;
 333                                                         strpos_result = res;
 334                                                         return true;
 335                                                 }
 336                                                 strpos++;
 337                                         }
 338                                         return false;
 339                                 case RxOp.Reference:
 340                                         length = GetLastDefined (program [pc + 1] | (program [pc + 2] << 8));
 341                                         if (length < 0)
 342                                                 return false;
 343                                         start = marks [length].Index;
 344                                         length = marks [length].Length;
 345                                         if (strpos + length > string_end)
 346                                                 return false;
 347                                         for (end = start + length; start < end; ++start) {
 348                                                 if (str [strpos] != str [start])
 349                                                         return false;
 350                                                 strpos++;
 351                                         }
 352                                         pc += 3;
 353                                         continue;
 354                                 case RxOp.ReferenceIgnoreCase:
 355                                         length = GetLastDefined (program [pc + 1] | (program [pc + 2] << 8));
 356                                         if (length < 0)
 357                                                 return false;
 358                                         start = marks [length].Index;
 359                                         length = marks [length].Length;
 360                                         if (strpos + length > string_end)
 361                                                 return false;
 362                                         for (end = start + length; start < end; ++start) {
 363                                                 if (str [strpos] != str [start] && Char.ToLower (str [strpos]) != Char.ToLower (str [start]))
 364                                                         return false;
 365                                                 strpos++;
 366                                         }
 367                                         pc += 3;
 368                                         continue;
 369                                 case RxOp.IfDefined:
 370                                         if (GetLastDefined (program [pc + 3] | (program [pc + 4] << 8)) < 0)
 371                                                 pc += 5;
 372                                         else
 373                                                 pc += program [pc + 1] | (program [pc + 2] << 8);
 374                                         continue;
 375                                 case RxOp.SubExpression: {
 376                                         int res = 0;
 377                                         if (EvalByteCode (pc + 3, strpos, ref res)) {
 378                                                 pc += program [pc + 1] | (program [pc + 2] << 8);
 379                                                 continue;
 380                                         }
 381                                         return false;
 382                                 }
 383                                 case RxOp.Test: {
 384                                         int res = 0;
 385                                         // FIXME: checkpoint
 386                                         if (EvalByteCode (pc + 5, strpos, ref res)) {
 387                                                 pc += program [pc + 1] | (program [pc + 2] << 8);
 388                                         } else {
 389                                                 pc += program [pc + 3] | (program [pc + 4] << 8);
 390                                         }
 391                                         continue;
 392                                 }
 393                                 case RxOp.OpenGroup:
 394                                         Open (program [pc + 1] | (program [pc + 2] << 8), strpos);
 395                                         pc += 3;
 396                                         continue;
 397                                 case RxOp.CloseGroup:
 398                                         Close (program [pc + 1] | (program [pc + 2] << 8), strpos);
 399                                         pc += 3;
 400                                         continue;
 401                                 case RxOp.Jump:
 402                                         pc += program [pc + 1] | (program [pc + 2] << 8);
 403                                         continue;
 404                                 case RxOp.TestCharGroup:
 405                                         char_group_end = pc + program [pc + 1] | (program [pc + 2] << 8);
 406                                         pc += 3;
 407                                         continue;
 408                                 case RxOp.String:
 409                                         start = pc + 2;
 410                                         length = program [pc + 1];
 411                                         if (strpos + length > string_end)
 412                                                 return false;
 413                                         end = start + length;
 414                                         for (; start < end; ++start) {
 415                                                 if (str [strpos] != program [start])
 416                                                         return false;
 417                                                 strpos++;
 418                                         }
 419                                         pc = end;
 420                                         continue;
 421                                 case RxOp.StringIgnoreCase:
 422                                         start = pc + 2;
 423                                         length = program [pc + 1];
 424                                         if (strpos + length > string_end)
 425                                                 return false;
 426                                         end = start + length;
 427                                         for (; start < end; ++start) {
 428                                                 if (str [strpos] != program [start] && Char.ToLower (str [strpos]) != program [start])
 429                                                         return false;
 430                                                 strpos++;
 431                                         }
 432                                         pc = end;
 433                                         continue;
 434                                 case RxOp.UnicodeString:
 435                                         start = pc + 3;
 436                                         length = program [pc + 1] | (program [pc + 2] << 8);
 437                                         if (strpos + length > string_end)
 438                                                 return false;
 439                                         end = start + length * 2;
 440                                         for (; start < end; start += 2) {
 441                                                 int c = program [start] | (program [start + 1] << 8);
 442                                                 if (str [strpos] != c)
 443                                                         return false;
 444                                                 strpos++;
 445                                         }
 446                                         pc = end;
 447                                         continue;
 448                                 case RxOp.UnicodeStringIgnoreCase:
 449                                         start = pc + 3;
 450                                         length = program [pc + 1] | (program [pc + 2] << 8);
 451                                         if (strpos + length > string_end)
 452                                                 return false;
 453                                         end = start + length * 2;
 454                                         for (; start < end; start += 2) {
 455                                                 int c = program [start] | (program [start + 1] << 8);
 456                                                 if (str [strpos] != c && Char.ToLower (str [strpos]) != c)
 457                                                         return false;
 458                                                 strpos++;
 459                                         }
 460                                         pc = end;
 461                                         continue;
 462                                 case RxOp.Char:
 463                                         if (strpos < string_end && (str [strpos] == program [pc + 1])) {
 464                                                 strpos++;
 465                                                 if (char_group_end != 0)
 466                                                         goto test_char_group_passed;
 467                                                 pc += 2;
 468                                                 continue;
 469                                         }
 470                                         if (char_group_end == 0)
 471                                                 return false;
 472                                         pc += 2;
 473                                         continue;
 474                                 case RxOp.NoChar:
 475                                         if (strpos < string_end && (str [strpos] != program [pc + 1])) {
 476                                                 strpos++;
 477                                                 if (char_group_end != 0)
 478                                                         goto test_char_group_passed;
 479                                                 pc += 2;
 480                                                 continue;
 481                                         }
 482                                         if (char_group_end == 0)
 483                                                 return false;
 484                                         pc += 2;
 485                                         continue;
 486                                 case RxOp.CharIgnoreCase:
 487                                         if (strpos < string_end && (Char.ToLower (str [strpos]) == program [pc + 1])) {
 488                                                 strpos++;
 489                                                 if (char_group_end != 0)
 490                                                         goto test_char_group_passed;
 491                                                 pc += 2;
 492                                                 continue;
 493                                         }
 494                                         if (char_group_end == 0)
 495                                                 return false;
 496                                         pc += 2;
 497                                         continue;
 498                                 case RxOp.NoCharIgnoreCase:
 499                                         if (strpos < string_end && (Char.ToLower (str [strpos]) != program [pc + 1])) {
 500                                                 strpos++;
 501                                                 if (char_group_end != 0)
 502                                                         goto test_char_group_passed;
 503                                                 pc += 2;
 504                                                 continue;
 505                                         }
 506                                         if (char_group_end == 0)
 507                                                 return false;
 508                                         pc += 2;
 509                                         continue;
 510                                 case RxOp.Range:
 511                                         if (strpos < string_end) {
 512                                                 int c = str [strpos];
 513                                                 if (c >= program [pc + 1] && c <= program [pc + 2]) {
 514                                                         strpos++;
 515                                                         if (char_group_end != 0)
 516                                                                 goto test_char_group_passed;
 517                                                         pc += 3;
 518                                                         continue;
 519                                                 }
 520                                         }
 521                                         if (char_group_end == 0)
 522                                                 return false;
 523                                         pc += 3;
 524                                         continue;
 525                                 case RxOp.NoRange:
 526                                         if (strpos < string_end) {
 527                                                 int c = str [strpos];
 528                                                 if (c >= program [pc + 1] && c <= program [pc + 2]) {
 529                                                         if (char_group_end == 0)
 530                                                                 return false;
 531                                                         pc += 3;
 532                                                         continue;
 533                                                 }
 534                                                 strpos++;
 535                                                 if (char_group_end != 0)
 536                                                         goto test_char_group_passed;
 537                                                 pc += 3;
 538                                                 continue;
 539                                         }
 540                                         if (char_group_end == 0)
 541                                                 return false;
 542                                         pc += 3;
 543                                         continue;
 544                                 case RxOp.RangeIgnoreCase:
 545                                         if (strpos < string_end) {
 546                                                 int c = Char.ToLower (str [strpos]);
 547                                                 if (c >= program [pc + 1] && c <= program [pc + 2]) {
 548                                                         strpos++;
 549                                                         if (char_group_end != 0)
 550                                                                 goto test_char_group_passed;
 551                                                         pc += 3;
 552                                                         continue;
 553                                                 }
 554                                         }
 555                                         if (char_group_end == 0)
 556                                                 return false;
 557                                         pc += 3;
 558                                         continue;
 559                                 case RxOp.NoRangeIgnoreCase:
 560                                         if (strpos < string_end) {
 561                                                 int c = Char.ToLower (str [strpos]);
 562                                                 if (c >= program [pc + 1] && c <= program [pc + 2]) {
 563                                                         if (char_group_end == 0)
 564                                                                 return false;
 565                                                         pc += 3;
 566                                                         continue;
 567                                                 }
 568                                                 strpos++;
 569                                                 if (char_group_end != 0)
 570                                                         goto test_char_group_passed;
 571                                                 pc += 3;
 572                                                 continue;
 573                                         }
 574                                         if (char_group_end == 0)
 575                                                 return false;
 576                                         pc += 3;
 577                                         continue;
 578                                 case RxOp.Bitmap:
 579                                         if (strpos < string_end) {
 580                                                 int c = str [strpos];
 581                                                 c -= program [pc + 1];
 582                                                 length = program [pc + 2];
 583                                                 if (c < 0 || c >= (length << 3)) {
 584                                                         if (char_group_end == 0)
 585                                                                 return false;
 586                                                         pc += length + 3;
 587                                                         continue;
 588                                                 }
 589                                                 pc += 3;
 590                                                 if ((program [pc + (c >> 3)] & (1 << (c & 0x7))) != 0) {
 591                                                         strpos++;
 592                                                         if (char_group_end != 0)
 593                                                                 goto test_char_group_passed;
 594                                                         pc += length;
 595                                                         continue;
 596                                                 }
 597                                                 if (char_group_end == 0)
 598                                                         return false;
 599                                                 pc += length;
 600                                                 continue;
 601                                         }
 602                                         if (char_group_end == 0)
 603                                                 return false;
 604                                         pc += 3 + program [pc + 2];
 605                                         continue;
 606                                 case RxOp.NoBitmap:
 607                                         if (strpos < string_end) {
 608                                                 int c = str [strpos];
 609                                                 c -= program [pc + 1];
 610                                                 length = program [pc + 2];
 611                                                 if (c < 0 || c >= (length << 3)) {
 612                                                         strpos++;
 613                                                         if (char_group_end != 0)
 614                                                                 goto test_char_group_passed;
 615                                                         pc += 3 + length;
 616                                                         continue;
 617                                                 }
 618                                                 pc += 3;
 619                                                 if ((program [pc + (c >> 3)] & (1 << (c & 0x7))) != 0) {
 620                                                         if (char_group_end == 0)
 621                                                                 return false;
 622                                                         pc += length;
 623                                                         continue;
 624                                                 } else {
 625                                                         strpos++;
 626                                                         if (char_group_end != 0)
 627                                                                 goto test_char_group_passed;
 628                                                         pc += length;
 629                                                         continue;
 630                                                 }
 631                                         }
 632                                         if (char_group_end == 0)
 633                                                 return false;
 634                                         pc += 3 + program [pc + 2];
 635                                         continue;
 636                                 case RxOp.BitmapIgnoreCase:
 637                                         if (strpos < string_end) {
 638                                                 int c = Char.ToLower (str [strpos]);
 639                                                 c -= program [pc + 1];
 640                                                 length = program [pc + 2];
 641                                                 if (c < 0 || c >= (length << 3)) {
 642                                                         if (char_group_end == 0)
 643                                                                 return false;
 644                                                         pc += length + 3;
 645                                                         continue;
 646                                                 }
 647                                                 pc += 3;
 648                                                 if ((program [pc + (c >> 3)] & (1 << (c & 0x7))) != 0) {
 649                                                         strpos++;
 650                                                         if (char_group_end != 0)
 651                                                                 goto test_char_group_passed;
 652                                                         pc += length;
 653                                                         continue;
 654                                                 }
 655                                                 if (char_group_end == 0)
 656                                                         return false;
 657                                                 pc += length;
 658                                                 continue;
 659                                         }
 660                                         if (char_group_end == 0)
 661                                                 return false;
 662                                         pc += 3 + program [pc + 2];
 663                                         continue;
 664                                 case RxOp.NoBitmapIgnoreCase:
 665                                         if (strpos < string_end) {
 666                                                 int c = str [strpos];
 667                                                 c -= program [pc + 1];
 668                                                 length =  program [pc + 2];
 669                                                 pc += 3;
 670                                                 if (c < 0 || c >= (length << 3)) {
 671                                                         strpos++;
 672                                                         if (char_group_end != 0)
 673                                                                 goto test_char_group_passed;
 674                                                         pc += length;
 675                                                         continue;
 676                                                 }
 677                                                 if ((program [pc + (c >> 3)] & (1 << (c & 0x7))) != 0) {
 678                                                         if (char_group_end == 0)
 679                                                                 return false;
 680                                                         pc += length;
 681                                                         continue;
 682                                                 } else {
 683                                                         strpos++;
 684                                                         if (char_group_end != 0)
 685                                                                 goto test_char_group_passed;
 686                                                         pc += length;
 687                                                         continue;
 688                                                 }
 689                                         }
 690                                         if (char_group_end == 0)
 691                                                 return false;
 692                                         pc += 3 + program [pc + 2];
 693                                         continue;
 694                                 case RxOp.UnicodeChar:
 695                                         if (strpos < string_end && (str [strpos] == (program [pc + 1] | (program [pc + 2] << 8)))) {
 696                                                 strpos++;
 697                                                 if (char_group_end != 0)
 698                                                         goto test_char_group_passed;
 699                                                 pc += 3;
 700                                                 continue;
 701                                         }
 702                                         if (char_group_end == 0)
 703                                                 return false;
 704                                         pc += 3;
 705                                         continue;
 706                                 case RxOp.NoUnicodeChar:
 707                                         if (strpos < string_end && (str [strpos] != (program [pc + 1] | (program [pc + 2] << 8)))) {
 708                                                 strpos++;
 709                                                 if (char_group_end != 0)
 710                                                         goto test_char_group_passed;
 711                                                 pc += 3;
 712                                                 continue;
 713                                         }
 714                                         if (char_group_end == 0)
 715                                                 return false;
 716                                         pc += 3;
 717                                         continue;
 718                                 case RxOp.UnicodeCharIgnoreCase:
 719                                         if (strpos < string_end && (Char.ToLower (str [strpos]) == (program [pc + 1] | (program [pc + 2] << 8)))) {
 720                                                 strpos++;
 721                                                 if (char_group_end != 0)
 722                                                         goto test_char_group_passed;
 723                                                 pc += 3;
 724                                                 continue;
 725                                         }
 726                                         if (char_group_end == 0)
 727                                                 return false;
 728                                         pc += 3;
 729                                         continue;
 730                                 case RxOp.NoUnicodeCharIgnoreCase:
 731                                         if (strpos < string_end && (Char.ToLower (str [strpos]) != (program [pc + 1] | (program [pc + 2] << 8)))) {
 732                                                 strpos++;
 733                                                 if (char_group_end != 0)
 734                                                         goto test_char_group_passed;
 735                                                 pc += 3;
 736                                                 continue;
 737                                         }
 738                                         if (char_group_end == 0)
 739                                                 return false;
 740                                         pc += 3;
 741                                         continue;
 742                                 case RxOp.CategoryAny:
 743                                         if (strpos < string_end && str [strpos] != '\n') {
 744                                                 strpos++;
 745                                                 if (char_group_end != 0)
 746                                                         goto test_char_group_passed;
 747                                                 pc++;
 748                                                 continue;
 749                                         }
 750                                         if (char_group_end == 0)
 751                                                 return false;
 752                                         pc++;
 753                                         continue;
 754                                 case RxOp.CategoryWord:
 755                                         if (strpos < string_end) {
 756                                                 char c = str [strpos];
 757                                                 if (Char.IsLetterOrDigit (c) || Char.GetUnicodeCategory (c) == UnicodeCategory.ConnectorPunctuation) {
 758                                                         strpos++;
 759                                                         if (char_group_end != 0)
 760                                                                 goto test_char_group_passed;
 761                                                         pc++;
 762                                                         continue;
 763                                                 }
 764                                         }
 765                                         if (char_group_end == 0)
 766                                                 return false;
 767                                         pc++;
 768                                         continue;
 769                                 case RxOp.NoCategoryWord:
 770                                         if (strpos < string_end) {
 771                                                 char c = str [strpos];
 772                                                 if (!Char.IsLetterOrDigit (c) && Char.GetUnicodeCategory (c) != UnicodeCategory.ConnectorPunctuation) {
 773                                                         strpos++;
 774                                                         if (char_group_end != 0)
 775                                                                 goto test_char_group_passed;
 776                                                         pc++;
 777                                                         continue;
 778                                                 }
 779                                         }
 780                                         if (char_group_end == 0)
 781                                                 return false;
 782                                         pc++;
 783                                         continue;
 784                                 case RxOp.CategoryDigit:
 785                                         if (strpos < string_end && Char.IsDigit (str [strpos])) {
 786                                                 strpos++;
 787                                                 if (char_group_end != 0)
 788                                                         goto test_char_group_passed;
 789                                                 pc++;
 790                                                 continue;
 791                                         }
 792                                         if (char_group_end == 0)
 793                                                 return false;
 794                                         pc++;
 795                                         continue;
 796                                 case RxOp.NoCategoryDigit:
 797                                         if (strpos < string_end && !Char.IsDigit (str [strpos])) {
 798                                                 strpos++;
 799                                                 if (char_group_end != 0)
 800                                                         goto test_char_group_passed;
 801                                                 pc++;
 802                                                 continue;
 803                                         }
 804                                         if (char_group_end == 0)
 805                                                 return false;
 806                                         pc++;
 807                                         continue;
 808                                 case RxOp.CategoryWhiteSpace:
 809                                         if (strpos < string_end && Char.IsWhiteSpace (str [strpos])) {
 810                                                 strpos++;
 811                                                 if (char_group_end != 0)
 812                                                         goto test_char_group_passed;
 813                                                 pc++;
 814                                                 continue;
 815                                         }
 816                                         if (char_group_end == 0)
 817                                                 return false;
 818                                         pc++;
 819                                         continue;
 820                                 case RxOp.NoCategoryWhiteSpace:
 821                                         if (strpos < string_end && !Char.IsWhiteSpace (str [strpos])) {
 822                                                 strpos++;
 823                                                 if (char_group_end != 0)
 824                                                         goto test_char_group_passed;
 825                                                 pc++;
 826                                                 continue;
 827                                         }
 828                                         if (char_group_end == 0)
 829                                                 return false;
 830                                         pc++;
 831                                         continue;
 832                                 case RxOp.CategoryEcmaWord:
 833                                         if (strpos < string_end) {
 834                                                 int c = str [strpos];
 835                                                 if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' || c == '_') {
 836                                                         strpos++;
 837                                                         if (char_group_end != 0)
 838                                                                 goto test_char_group_passed;
 839                                                         pc++;
 840                                                         continue;
 841                                                 }
 842                                         }
 843                                         if (char_group_end == 0)
 844                                                 return false;
 845                                         pc++;
 846                                         continue;
 847                                 case RxOp.NoCategoryEcmaWord:
 848                                         if (strpos < string_end) {
 849                                                 int c = str [strpos];
 850                                                 if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' || c == '_') {
 851                                                         if (char_group_end == 0)
 852                                                                 return false;
 853                                                         pc++;
 854                                                         continue;
 855                                                 }
 856                                                 strpos++;
 857                                                 if (char_group_end != 0)
 858                                                         goto test_char_group_passed;
 859                                                 pc++;
 860                                                 continue;
 861                                         }
 862                                         if (char_group_end == 0)
 863                                                 return false;
 864                                         pc++;
 865                                         continue;
 866                                 case RxOp.CategoryEcmaWhiteSpace:
 867                                         if (strpos < string_end) {
 868                                                 int c = str [strpos];
 869                                                 if (c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f' || c == '\v') {
 870                                                         strpos++;
 871                                                         if (char_group_end != 0)
 872                                                                 goto test_char_group_passed;
 873                                                         pc++;
 874                                                         continue;
 875                                                 }
 876                                         }
 877                                         if (char_group_end == 0)
 878                                                 return false;
 879                                         pc++;
 880                                         continue;
 881                                 case RxOp.NoCategoryEcmaWhiteSpace:
 882                                         if (strpos < string_end) {
 883                                                 int c = str [strpos];
 884                                                 if (c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f' || c == '\v') {
 885                                                         if (char_group_end == 0)
 886                                                                 return false;
 887                                                         pc++;
 888                                                         continue;
 889                                                 }
 890                                                 strpos++;
 891                                                 if (char_group_end != 0)
 892                                                         goto test_char_group_passed;
 893                                                 pc++;
 894                                                 continue;
 895                                         }
 896                                         if (char_group_end == 0)
 897                                                 return false;
 898                                         pc++;
 899                                         continue;
 900                                 case RxOp.CategoryUnicodeSpecials:
 901                                         if (strpos < string_end) {
 902                                                 int c = str [strpos];
 903                                                 if ('\uFEFF' <= c && c <= '\uFEFF' || '\uFFF0' <= c && c <= '\uFFFD') {
 904                                                         strpos++;
 905                                                         if (char_group_end != 0)
 906                                                                 goto test_char_group_passed;
 907                                                         pc++;
 908                                                         continue;
 909                                                 }
 910                                         }
 911                                         if (char_group_end == 0)
 912                                                 return false;
 913                                         pc++;
 914                                         continue;
 915                                 case RxOp.NoCategoryUnicodeSpecials:
 916                                         if (strpos < string_end) {
 917                                                 int c = str [strpos];
 918                                                 if ('\uFEFF' <= c && c <= '\uFEFF' || '\uFFF0' <= c && c <= '\uFFFD') {
 919                                                         if (char_group_end == 0)
 920                                                                 return false;
 921                                                         pc++;
 922                                                         continue;
 923                                                 }
 924                                                 strpos++;
 925                                                 if (char_group_end != 0)
 926                                                         goto test_char_group_passed;
 927                                                 pc++;
 928                                                 continue;
 929                                         }
 930                                         if (char_group_end == 0)
 931                                                 return false;
 932                                         pc++;
 933                                         continue;
 934                                 case RxOp.CategoryUnicode:
 935                                         if (strpos < string_end && Char.GetUnicodeCategory (str [strpos]) == (UnicodeCategory)program [pc + 1]) {
 936                                                 strpos++;
 937                                                 if (char_group_end != 0)
 938                                                         goto test_char_group_passed;
 939                                                 pc += 2;
 940                                                 continue;
 941                                         }
 942                                         if (char_group_end == 0)
 943                                                 return false;
 944                                         pc += 2;
 945                                         continue;
 946                                 case RxOp.NoCategoryUnicode:
 947                                         if (strpos < string_end && Char.GetUnicodeCategory (str [strpos]) != (UnicodeCategory)program [pc + 1]) {
 948                                                 strpos++;
 949                                                 if (char_group_end != 0)
 950                                                         goto test_char_group_passed;
 951                                                 pc += 2;
 952                                                 continue;
 953                                         }
 954                                         if (char_group_end == 0)
 955                                                 return false;
 956                                         pc += 2;
 957                                         continue;
 958                                 case RxOp.Branch: {
 959                                         int res = 0;
 960                                         if (EvalByteCode (pc + 3, strpos, ref res)) {
 961                                                 strpos_result = res;
 962                                                 return true;
 963                                         }
 964                                         //Console.WriteLine ("branch offset: {0}", program [pc + 1] | (program [pc + 2] << 8));
 965                                         pc += program [pc + 1] | (program [pc + 2] << 8);
 966                                         continue;
 967                                 }
 968                                 case RxOp.Repeat:
 969                                 case RxOp.RepeatLazy: {
 970                                         int res = 0;
 971                                         start = ReadInt (program, pc + 3);
 972                                         end = ReadInt (program, pc + 7);
 973                                         //Console.WriteLine ("min: {0}, max: {1}", start, end);
 974                                         length = 0;
 975                                         int cp = Checkpoint ();
 976                                         while (length < end) {
 977                                                 if (!EvalByteCode (pc + 11, strpos, ref res)) {
 978                                                         if (length >= start) {
 979                                                                 goto repeat_success;
 980                                                         }
 981                                                         return false;
 982                                                 }
 983                                                 strpos = res;
 984                                                 length++;
 985                                                 Backtrack (cp);
 986                                         }
 987                                         if (length != end)
 988                                                 return false;
 989                                 repeat_success:
 990                                         pc += program [pc + 1] | (program [pc + 2] << 8);
 991                                         continue;
 992                                 }
 993                                 default:
 994                                         Console.WriteLine ("evaluating: {0} at pc: {1}, strpos: {2}", (RxOp)program [pc], pc, strpos);
 995                                         throw new NotSupportedException ();
 996                                 }
 997                                 continue;
 998                         test_char_group_passed:
 999                                 pc = char_group_end;
1000                                 char_group_end = 0;
1001                                 continue;
1002                         } // end of while (true)
1003                 }
1004         }
1005 }
1006