mcs/class/referencesource/System/regex/system/text/regularexpressions/RegexCompiler.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="RegexCompiler.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //------------------------------------------------------------------------------
   6
   7 // The RegexCompiler class is internal to the Regex package.
   8 // It translates a block of RegexCode to MSIL, and creates a
   9 // subclass of the RegexRunner type.
  10
  11
  12 #if !SILVERLIGHT && !FULL_AOT_RUNTIME
  13
  14 namespace System.Text.RegularExpressions {
  15
  16     using System.Collections;
  17         using System.Collections.Generic;
  18     using System.Threading;
  19     using System.Reflection;
  20     using System.Reflection.Emit;
  21     using System.Security;
  22     using System.Security.Policy;
  23     using System.Security.Permissions;
  24     using System.Diagnostics;
  25     using System.Diagnostics.CodeAnalysis;
  26     using System.Globalization;
  27     using System.Runtime.Versioning;
  28
  29     /*
  30      * RegexDynamicModule
  31      *
  32      * Because dynamic modules are expensive and not thread-safe, we create
  33      * one dynamic module per-thread, and cache as much information about it
  34      * as we can.
  35      *
  36      * While we're at it, we just create one RegexCompiler per thread
  37      * as well, and have RegexCompiler inherit from RegexDynamicModule.
  38      */
  39     internal abstract class RegexCompiler {
  40         // fields that never change (making them saves about 6% overall running time)
  41
  42         internal static FieldInfo      _textbegF;
  43         internal static FieldInfo      _textendF;
  44         internal static FieldInfo      _textstartF;
  45         internal static FieldInfo      _textposF;
  46         internal static FieldInfo      _textF;
  47         internal static FieldInfo      _trackposF;
  48         internal static FieldInfo      _trackF;
  49         internal static FieldInfo      _stackposF;
  50         internal static FieldInfo      _stackF;
  51         internal static FieldInfo      _trackcountF;
  52
  53         // note some methods
  54
  55         internal static MethodInfo     _ensurestorageM;
  56         internal static MethodInfo     _captureM;
  57         internal static MethodInfo     _transferM;
  58         internal static MethodInfo     _uncaptureM;
  59         internal static MethodInfo     _ismatchedM;
  60         internal static MethodInfo     _matchlengthM;
  61         internal static MethodInfo     _matchindexM;
  62         internal static MethodInfo     _isboundaryM;
  63         internal static MethodInfo     _isECMABoundaryM;
  64         internal static MethodInfo     _chartolowerM;
  65         internal static MethodInfo     _getcharM;
  66         internal static MethodInfo     _crawlposM;
  67         internal static MethodInfo     _charInSetM;
  68         internal static MethodInfo     _getCurrentCulture;
  69         internal static MethodInfo     _getInvariantCulture;
  70         internal static MethodInfo     _checkTimeoutM;
  71     #if DBG
  72         internal static MethodInfo     _dumpstateM;
  73     #endif
  74
  75         internal ILGenerator     _ilg;
  76
  77         // tokens representing local variables
  78         internal LocalBuilder      _textstartV;
  79         internal LocalBuilder      _textbegV;
  80         internal LocalBuilder      _textendV;
  81         internal LocalBuilder      _textposV;
  82         internal LocalBuilder      _textV;
  83         internal LocalBuilder      _trackposV;
  84         internal LocalBuilder      _trackV;
  85         internal LocalBuilder      _stackposV;
  86         internal LocalBuilder      _stackV;
  87         internal LocalBuilder      _tempV;
  88         internal LocalBuilder      _temp2V;
  89         internal LocalBuilder      _temp3V;
  90
  91
  92         internal RegexCode       _code;              // the RegexCode object (used for debugging only)
  93         internal int[]           _codes;             // the RegexCodes being translated
  94         internal String[]        _strings;           // the stringtable associated with the RegexCodes
  95         internal RegexPrefix     _fcPrefix;          // the possible first chars computed by RegexFCD
  96         internal RegexBoyerMoore _bmPrefix;          // a prefix as a boyer-moore machine
  97         internal int             _anchors;           // the set of anchors
  98
  99         internal Label[]         _labels;            // a label for every operation in _codes
 100         internal BacktrackNote[] _notes;             // a list of the backtracking states to be generated
 101         internal int             _notecount;         // true count of _notes (allocation grows exponentially)
 102         internal int             _trackcount;        // count of backtracking states (used to reduce allocations)
 103
 104         internal Label           _backtrack;         // label for backtracking
 105
 106
 107         internal int             _regexopcode;       // the current opcode being processed
 108         internal int             _codepos;           // the current code being translated
 109         internal int             _backpos;           // the current backtrack-note being translated
 110
 111         internal RegexOptions    _options;           // options
 112
 113         // special code fragments
 114         internal int[]           _uniquenote;        // _notes indices for code that should be emitted <= once
 115         internal int[]           _goto;              // indices for forward-jumps-through-switch (for allocations)
 116
 117         // indices for unique code fragments
 118         internal const int stackpop               = 0;    // pop one
 119         internal const int stackpop2              = 1;    // pop two
 120         internal const int stackpop3              = 2;    // pop three
 121         internal const int capback                = 3;    // uncapture
 122         internal const int capback2               = 4;    // uncapture 2
 123         internal const int branchmarkback2        = 5;    // back2 part of branchmark
 124         internal const int lazybranchmarkback2    = 6;    // back2 part of lazybranchmark
 125         internal const int branchcountback2       = 7;    // back2 part of branchcount
 126         internal const int lazybranchcountback2   = 8;    // back2 part of lazybranchcount
 127         internal const int forejumpback           = 9;    // back part of forejump
 128         internal const int uniquecount            = 10;
 129
 130         static RegexCompiler() {
 131             // <SECREVIEW> Regex only generates string manipulation, so this is ok.
 132             // </SECREVIEW>
 133
 134 #if !DISABLE_CAS_USE
 135             new ReflectionPermission(PermissionState.Unrestricted).Assert();
 136 #endif
 137             try {
 138                 // note some fields
 139                 _textbegF       = RegexRunnerField("runtextbeg");
 140                 _textendF       = RegexRunnerField("runtextend");
 141                 _textstartF     = RegexRunnerField("runtextstart");
 142                 _textposF       = RegexRunnerField("runtextpos");
 143                 _textF          = RegexRunnerField("runtext");
 144                 _trackposF      = RegexRunnerField("runtrackpos");
 145                 _trackF         = RegexRunnerField("runtrack");
 146                 _stackposF      = RegexRunnerField("runstackpos");
 147                 _stackF         = RegexRunnerField("runstack");
 148                 _trackcountF    = RegexRunnerField("runtrackcount");
 149
 150                 // note some methods
 151                 _ensurestorageM = RegexRunnerMethod("EnsureStorage");
 152                 _captureM       = RegexRunnerMethod("Capture");
 153                 _transferM      = RegexRunnerMethod("TransferCapture");
 154                 _uncaptureM     = RegexRunnerMethod("Uncapture");
 155                 _ismatchedM     = RegexRunnerMethod("IsMatched");
 156                 _matchlengthM   = RegexRunnerMethod("MatchLength");
 157                 _matchindexM    = RegexRunnerMethod("MatchIndex");
 158                 _isboundaryM    = RegexRunnerMethod("IsBoundary");
 159                 _charInSetM     = RegexRunnerMethod("CharInClass");
 160                 _isECMABoundaryM= RegexRunnerMethod("IsECMABoundary");
 161                 _crawlposM      = RegexRunnerMethod("Crawlpos");
 162                 _checkTimeoutM  = RegexRunnerMethod("CheckTimeout");
 163
 164                 _chartolowerM   = typeof(Char).GetMethod("ToLower", new Type[] {typeof(Char), typeof(CultureInfo)});
 165                 _getcharM       = typeof(String).GetMethod("get_Chars", new Type[] {typeof(int)});
 166                 _getCurrentCulture   = typeof(CultureInfo).GetMethod("get_CurrentCulture");
 167                 _getInvariantCulture = typeof(CultureInfo).GetMethod("get_InvariantCulture");
 168
 169
 170 #if DBG
 171                 _dumpstateM     = RegexRunnerMethod("DumpState");
 172 #endif
 173             }
 174             finally {
 175 #if !DISABLE_CAS_USE
 176                 CodeAccessPermission.RevertAssert();
 177 #endif
 178             }
 179         }
 180
 181         private static FieldInfo RegexRunnerField(String fieldname) {
 182             return typeof(RegexRunner).GetField(fieldname, BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance | BindingFlags.Static);
 183         }
 184
 185         private static MethodInfo RegexRunnerMethod(String methname) {
 186             return typeof(RegexRunner).GetMethod(methname, BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance | BindingFlags.Static);
 187         }
 188
 189
 190         /*
 191          * Entry point to dynamically compile a regular expression.  The expression is compiled to
 192          * an in-memory assembly.
 193          */
 194         internal static RegexRunnerFactory Compile(RegexCode code, RegexOptions options) {
 195             RegexLWCGCompiler c = new RegexLWCGCompiler();
 196             RegexRunnerFactory factory;
 197
 198             // <SECREVIEW> Regex only generates string manipulation, so this is ok.
 199             // </SECREVIEW>
 200 #if !DISABLE_CAS_USE
 201             new ReflectionPermission(PermissionState.Unrestricted).Assert();
 202 #endif
 203             try {
 204                 factory = c.FactoryInstanceFromCode(code, options);
 205             }
 206             finally {
 207 #if !DISABLE_CAS_USE
 208                 CodeAccessPermission.RevertAssert();
 209 #endif
 210             }
 211             return factory;
 212         }
 213
 214         /*
 215          * Compile regular expressions into an assembly on disk.
 216          */
 217         [ResourceExposure(ResourceScope.Machine)]
 218         [ResourceConsumption(ResourceScope.Machine)]
 219         [SuppressMessage("Microsoft.Security","CA2106:SecureAsserts", Justification="[....]: SECREVIEW : Regex only generates string manipulation, so this is OK")]
 220         internal static void CompileToAssembly(RegexCompilationInfo[] regexes, AssemblyName an, CustomAttributeBuilder[] attribs, String resourceFile) {
 221             RegexTypeCompiler c = new RegexTypeCompiler(an, attribs, resourceFile);
 222
 223             for (int i=0; i<regexes.Length; i++) {
 224                 if (regexes[i] == null) {
 225                     throw new ArgumentNullException("regexes", SR.GetString(SR.ArgumentNull_ArrayWithNullElements));
 226                 }
 227                 String pattern = regexes[i].Pattern;
 228                 RegexOptions options = regexes[i].Options;
 229                 String fullname;
 230                 if (regexes[i].Namespace.Length == 0)
 231                     fullname = regexes[i].Name;
 232                 else
 233                     fullname = regexes[i].Namespace + "." + regexes[i].Name;
 234
 235                 TimeSpan mTimeout = regexes[i].MatchTimeout;
 236
 237                 RegexTree tree = RegexParser.Parse(pattern, options);
 238                 RegexCode code = RegexWriter.Write(tree);
 239
 240                 Type factory;
 241
 242 #if !DISABLE_CAS_USE
 243                 new ReflectionPermission(PermissionState.Unrestricted).Assert();
 244 #endif
 245                 try {
 246                     factory = c.FactoryTypeFromCode(code, options, fullname);
 247                     c.GenerateRegexType(pattern, options, fullname, regexes[i].IsPublic, code, tree, factory, mTimeout);
 248                 }
 249                 finally {
 250 #if !DISABLE_CAS_USE
 251                     CodeAccessPermission.RevertAssert();
 252 #endif
 253                 }
 254             }
 255
 256             c.Save();
 257         }
 258
 259
 260         /*
 261          * Keeps track of an operation that needs to be referenced in the backtrack-jump
 262          * switch table, and that needs backtracking code to be emitted (if flags != 0)
 263          */
 264         internal sealed class BacktrackNote {
 265             internal BacktrackNote(int flags, Label label, int codepos) {
 266                 _codepos = codepos;
 267                 _flags = flags;
 268                 _label = label;
 269             }
 270
 271             internal int _codepos;
 272             internal int _flags;
 273             internal Label _label;
 274         }
 275
 276         /*
 277          * Adds a backtrack note to the list of them, and returns the index of the new
 278          * note (which is also the index for the jump used by the switch table)
 279          */
 280         internal int AddBacktrackNote(int flags, Label l, int codepos) {
 281             if (_notes == null || _notecount >= _notes.Length) {
 282                 BacktrackNote[] newnotes = new BacktrackNote[_notes == null ? 16 : _notes.Length * 2];
 283                 if (_notes != null)
 284                     System.Array.Copy(_notes, 0, newnotes, 0, _notecount);
 285                 _notes = newnotes;
 286             }
 287
 288             _notes[_notecount] = new BacktrackNote(flags, l, codepos);
 289
 290             return _notecount++;
 291         }
 292
 293         /*
 294          * Adds a backtrack note for the current operation; creates a new label for
 295          * where the code will be, and returns the switch index.
 296          */
 297         internal int AddTrack() {
 298             return AddTrack(RegexCode.Back);
 299         }
 300
 301         /*
 302          * Adds a backtrack note for the current operation; creates a new label for
 303          * where the code will be, and returns the switch index.
 304          */
 305         internal int AddTrack(int flags) {
 306             return AddBacktrackNote(flags, DefineLabel(), _codepos);
 307         }
 308
 309         /*
 310          * Adds a switchtable entry for the specified position (for the forward
 311          * logic; does not cause backtracking logic to be generated)
 312          */
 313         internal int AddGoto(int destpos) {
 314             if (_goto[destpos] == -1)
 315                 _goto[destpos] = AddBacktrackNote(0, _labels[destpos], destpos);
 316
 317             return _goto[destpos];
 318         }
 319
 320         /*
 321          * Adds a note for backtracking code that only needs to be generated once;
 322          * if it's already marked to be generated, returns the switch index
 323          * for the unique piece of code.
 324          */
 325         internal int AddUniqueTrack(int i) {
 326             return AddUniqueTrack(i, RegexCode.Back);
 327         }
 328
 329         /*
 330          * Adds a note for backtracking code that only needs to be generated once;
 331          * if it's already marked to be generated, returns the switch index
 332          * for the unique piece of code.
 333          */
 334         internal int AddUniqueTrack(int i, int flags) {
 335             if (_uniquenote[i] == -1)
 336                 _uniquenote[i] = AddTrack(flags);
 337
 338             return _uniquenote[i];
 339         }
 340
 341         /*
 342          * A macro for _ilg.DefineLabel
 343          */
 344         internal Label DefineLabel() {
 345             return _ilg.DefineLabel();
 346         }
 347
 348         /*
 349          * A macro for _ilg.MarkLabel
 350          */
 351         internal void MarkLabel(Label l) {
 352             _ilg.MarkLabel(l);
 353         }
 354
 355         /*
 356          * Returns the ith operand of the current operation
 357          */
 358         internal int Operand(int i) {
 359             return _codes[_codepos + i + 1];
 360         }
 361
 362         /*
 363          * True if the current operation is marked for the leftward direction
 364          */
 365         internal bool IsRtl() {
 366             return(_regexopcode & RegexCode.Rtl) != 0;
 367         }
 368
 369         /*
 370          * True if the current operation is marked for case insensitive operation
 371          */
 372         internal bool IsCi() {
 373             return(_regexopcode & RegexCode.Ci) != 0;
 374         }
 375
 376 #if DBG
 377         /*
 378          * True if we need to do the backtrack logic for the current operation
 379          */
 380         internal bool IsBack() {
 381             return(_regexopcode & RegexCode.Back) != 0;
 382         }
 383
 384         /*
 385          * True if we need to do the second-backtrack logic for the current operation
 386          */
 387         internal bool IsBack2() {
 388             return(_regexopcode & RegexCode.Back2) != 0;
 389         }
 390 #endif
 391
 392         /*
 393          * Returns the raw regex opcode (masking out Back and Rtl)
 394          */
 395         internal int Code() {
 396             return _regexopcode & RegexCode.Mask;
 397         }
 398
 399         internal void Ldstr(string str) {
 400             _ilg.Emit(OpCodes.Ldstr, str);
 401         }
 402
 403         /*
 404          * A macro for the various forms of Ldc
 405          */
 406         internal void Ldc(int i) {
 407             if (i <= 127 && i >= -128)
 408                 _ilg.Emit(OpCodes.Ldc_I4_S, (byte)i);
 409             else
 410                 _ilg.Emit(OpCodes.Ldc_I4, i);
 411         }
 412
 413         internal void LdcI8(long i) {
 414             if (i <= Int32.MaxValue && i >= Int32.MinValue) {
 415                 Ldc((Int32) i);
 416                 _ilg.Emit(OpCodes.Conv_I8);
 417             } else {
 418                 _ilg.Emit(OpCodes.Ldc_I8, i);
 419             }
 420         }
 421
 422         /*
 423          * A macro for _ilg.Emit(OpCodes.Dup)
 424          */
 425         internal void Dup() {
 426             _ilg.Emit(OpCodes.Dup);
 427         }
 428
 429         /*
 430          * A macro for _ilg.Emit(OpCodes.Ret)
 431          */
 432         internal void Ret() {
 433             _ilg.Emit(OpCodes.Ret);
 434         }
 435
 436         /*
 437          * A macro for _ilg.Emit(OpCodes.Pop)
 438          */
 439         internal void Pop() {
 440             _ilg.Emit(OpCodes.Pop);
 441         }
 442
 443         /*
 444          * A macro for _ilg.Emit(OpCodes.Add)
 445          */
 446         internal void Add() {
 447             _ilg.Emit(OpCodes.Add);
 448         }
 449
 450         /*
 451          * A macro for _ilg.Emit(OpCodes.Add); a true flag can turn it into a Sub
 452          */
 453         internal void Add(bool negate) {
 454             if (negate)
 455                 _ilg.Emit(OpCodes.Sub);
 456             else
 457                 _ilg.Emit(OpCodes.Add);
 458         }
 459
 460         /*
 461          * A macro for _ilg.Emit(OpCodes.Sub)
 462          */
 463         internal void Sub() {
 464             _ilg.Emit(OpCodes.Sub);
 465         }
 466
 467         /*
 468          * A macro for _ilg.Emit(OpCodes.Sub); a true flag can turn it into a Add
 469          */
 470         internal void Sub(bool negate) {
 471             if (negate)
 472                 _ilg.Emit(OpCodes.Add);
 473             else
 474                 _ilg.Emit(OpCodes.Sub);
 475         }
 476
 477         /*
 478          * A macro for _ilg.Emit(OpCodes.Ldloc);
 479          */
 480         internal void Ldloc(LocalBuilder lt) {
 481             _ilg.Emit(OpCodes.Ldloc_S, lt);
 482         }
 483
 484         /*
 485          * A macro for _ilg.Emit(OpCodes.Stloc);
 486          */
 487         internal void Stloc(LocalBuilder lt) {
 488             _ilg.Emit(OpCodes.Stloc_S, lt);
 489         }
 490
 491         /*
 492          * A macro for _ilg.Emit(OpCodes.Ldarg_0);
 493          */
 494         internal void Ldthis() {
 495             _ilg.Emit(OpCodes.Ldarg_0);
 496         }
 497
 498         /*
 499          * A macro for Ldthis(); Ldfld();
 500          */
 501         internal void Ldthisfld(FieldInfo ft) {
 502             Ldthis();
 503             _ilg.Emit(OpCodes.Ldfld, ft);
 504         }
 505
 506         /*
 507          * A macro for Ldthis(); Ldfld(); Stloc();
 508          */
 509         internal void Mvfldloc(FieldInfo ft, LocalBuilder lt) {
 510             Ldthisfld(ft);
 511             Stloc(lt);
 512         }
 513
 514         /*
 515          * A macro for Ldthis(); Ldthisfld(); Stloc();
 516          */
 517         internal void Mvlocfld(LocalBuilder lt, FieldInfo ft) {
 518             Ldthis();
 519             Ldloc(lt);
 520             Stfld(ft);
 521         }
 522
 523         /*
 524          * A macro for _ilg.Emit(OpCodes.Stfld);
 525          */
 526         internal void Stfld(FieldInfo ft) {
 527             _ilg.Emit(OpCodes.Stfld, ft);
 528         }
 529
 530         /*
 531          * A macro for _ilg.Emit(OpCodes.Callvirt);
 532          */
 533         internal void Callvirt(MethodInfo mt) {
 534             _ilg.Emit(OpCodes.Callvirt, mt);
 535         }
 536
 537         /*
 538          * A macro for _ilg.Emit(OpCodes.Call);
 539          */
 540         internal void Call(MethodInfo mt) {
 541             _ilg.Emit(OpCodes.Call, mt);
 542         }
 543
 544         /*
 545          * A macro for _ilg.Emit(OpCodes.Newobj);
 546          */
 547         internal void Newobj(ConstructorInfo ct) {
 548             _ilg.Emit(OpCodes.Newobj, ct);
 549         }
 550
 551         /*
 552          * A macro for _ilg.Emit(OpCodes.Brfalse) (long form)
 553          */
 554         internal void BrfalseFar(Label l) {
 555             _ilg.Emit(OpCodes.Brfalse, l);
 556         }
 557
 558         /*
 559          * A macro for _ilg.Emit(OpCodes.Brtrue) (long form)
 560          */
 561         internal void BrtrueFar(Label l) {
 562             _ilg.Emit(OpCodes.Brtrue, l);
 563         }
 564
 565         /*
 566          * A macro for _ilg.Emit(OpCodes.Br) (long form)
 567          */
 568         internal void BrFar(Label l) {
 569             _ilg.Emit(OpCodes.Br, l);
 570         }
 571
 572         /*
 573          * A macro for _ilg.Emit(OpCodes.Ble) (long form)
 574          */
 575         internal void BleFar(Label l) {
 576             _ilg.Emit(OpCodes.Ble, l);
 577         }
 578
 579         /*
 580          * A macro for _ilg.Emit(OpCodes.Blt) (long form)
 581          */
 582         internal void BltFar(Label l) {
 583             _ilg.Emit(OpCodes.Blt, l);
 584         }
 585
 586         /*
 587          * A macro for _ilg.Emit(OpCodes.Bge) (long form)
 588          */
 589         internal void BgeFar(Label l) {
 590             _ilg.Emit(OpCodes.Bge, l);
 591         }
 592
 593         /*
 594          * A macro for _ilg.Emit(OpCodes.Bgt) (long form)
 595          */
 596         internal void BgtFar(Label l) {
 597             _ilg.Emit(OpCodes.Bgt, l);
 598         }
 599
 600         /*
 601          * A macro for _ilg.Emit(OpCodes.Bne) (long form)
 602          */
 603         internal void BneFar(Label l) {
 604             _ilg.Emit(OpCodes.Bne_Un, l);
 605         }
 606
 607         /*
 608          * A macro for _ilg.Emit(OpCodes.Beq) (long form)
 609          */
 610         internal void BeqFar(Label l) {
 611             _ilg.Emit(OpCodes.Beq, l);
 612         }
 613
 614         /*
 615          * A macro for _ilg.Emit(OpCodes.Brfalse_S) (short jump)
 616          */
 617         internal void Brfalse(Label l) {
 618             _ilg.Emit(OpCodes.Brfalse_S, l);
 619         }
 620
 621         /*
 622          * A macro for _ilg.Emit(OpCodes.Br_S) (short jump)
 623          */
 624         internal void Br(Label l) {
 625             _ilg.Emit(OpCodes.Br_S, l);
 626         }
 627
 628         /*
 629          * A macro for _ilg.Emit(OpCodes.Ble_S) (short jump)
 630          */
 631         internal void Ble(Label l) {
 632             _ilg.Emit(OpCodes.Ble_S, l);
 633         }
 634
 635         /*
 636          * A macro for _ilg.Emit(OpCodes.Blt_S) (short jump)
 637          */
 638         internal void Blt(Label l) {
 639             _ilg.Emit(OpCodes.Blt_S, l);
 640         }
 641
 642         /*
 643          * A macro for _ilg.Emit(OpCodes.Bge_S) (short jump)
 644          */
 645         internal void Bge(Label l) {
 646             _ilg.Emit(OpCodes.Bge_S, l);
 647         }
 648
 649         /*
 650          * A macro for _ilg.Emit(OpCodes.Bgt_S) (short jump)
 651          */
 652         internal void Bgt(Label l) {
 653             _ilg.Emit(OpCodes.Bgt_S, l);
 654         }
 655
 656         /*
 657          * A macro for _ilg.Emit(OpCodes.Bleun_S) (short jump)
 658          */
 659         internal void Bgtun(Label l) {
 660             _ilg.Emit(OpCodes.Bgt_Un_S, l);
 661         }
 662
 663         /*
 664          * A macro for _ilg.Emit(OpCodes.Bne_S) (short jump)
 665          */
 666         internal void Bne(Label l) {
 667             _ilg.Emit(OpCodes.Bne_Un_S, l);
 668         }
 669
 670         /*
 671          * A macro for _ilg.Emit(OpCodes.Beq_S) (short jump)
 672          */
 673         internal void Beq(Label l) {
 674             _ilg.Emit(OpCodes.Beq_S, l);
 675         }
 676
 677         /*
 678          * A macro for the Ldlen instruction
 679          */
 680         internal void Ldlen() {
 681             _ilg.Emit(OpCodes.Ldlen);
 682         }
 683
 684         /*
 685          * Loads the char to the right of the current position
 686          */
 687         internal void Rightchar() {
 688             Ldloc(_textV);
 689             Ldloc(_textposV);
 690             Callvirt(_getcharM);
 691         }
 692
 693         /*
 694          * Loads the char to the right of the current position and advances the current position
 695          */
 696         internal void Rightcharnext() {
 697             Ldloc(_textV);
 698             Ldloc(_textposV);
 699             Dup();
 700             Ldc(1);
 701             Add();
 702             Stloc(_textposV);
 703             Callvirt(_getcharM);
 704         }
 705
 706         /*
 707          * Loads the char to the left of the current position
 708          */
 709         internal void Leftchar() {
 710             Ldloc(_textV);
 711             Ldloc(_textposV);
 712             Ldc(1);
 713             Sub();
 714             Callvirt(_getcharM);
 715         }
 716
 717         /*
 718          * Loads the char to the left of the current position and advances (leftward)
 719          */
 720         internal void Leftcharnext() {
 721             Ldloc(_textV);
 722             Ldloc(_textposV);
 723             Ldc(1);
 724             Sub();
 725             Dup();
 726             Stloc(_textposV);
 727             Callvirt(_getcharM);
 728         }
 729
 730         /*
 731          * Creates a backtrack note and pushes the switch index it on the tracking stack
 732          */
 733         internal void Track() {
 734             ReadyPushTrack();
 735             Ldc(AddTrack());
 736             DoPush();
 737         }
 738
 739         /*
 740          * Pushes the current switch index on the tracking stack so the backtracking
 741          * logic will be repeated again next time we backtrack here.
 742          *
 743          * <
 744
 745 */
 746         internal void Trackagain() {
 747             ReadyPushTrack();
 748             Ldc(_backpos);
 749             DoPush();
 750         }
 751
 752         /*
 753          * Saves the value of a local variable on the tracking stack
 754          */
 755         internal void PushTrack(LocalBuilder lt) {
 756             ReadyPushTrack();
 757             Ldloc(lt);
 758             DoPush();
 759         }
 760
 761         /*
 762          * Creates a backtrack note for a piece of code that should only be generated once,
 763          * and emits code that pushes the switch index on the backtracking stack.
 764          */
 765         internal void TrackUnique(int i) {
 766             ReadyPushTrack();
 767             Ldc(AddUniqueTrack(i));
 768             DoPush();
 769         }
 770
 771         /*
 772          * Creates a second-backtrack note for a piece of code that should only be
 773          * generated once, and emits code that pushes the switch index on the
 774          * backtracking stack.
 775          */
 776         internal void TrackUnique2(int i) {
 777             ReadyPushTrack();
 778             Ldc(AddUniqueTrack(i, RegexCode.Back2));
 779             DoPush();
 780         }
 781
 782         /*
 783          * Prologue to code that will push an element on the tracking stack
 784          */
 785         internal void ReadyPushTrack() {
 786             _ilg.Emit(OpCodes.Ldloc_S, _trackV);
 787             _ilg.Emit(OpCodes.Ldloc_S, _trackposV);
 788             _ilg.Emit(OpCodes.Ldc_I4_1);
 789             _ilg.Emit(OpCodes.Sub);
 790             _ilg.Emit(OpCodes.Dup);
 791             _ilg.Emit(OpCodes.Stloc_S, _trackposV);
 792         }
 793
 794         /*
 795          * Pops an element off the tracking stack (leave it on the operand stack)
 796          */
 797         internal void PopTrack() {
 798             _ilg.Emit(OpCodes.Ldloc_S, _trackV);
 799             _ilg.Emit(OpCodes.Ldloc_S, _trackposV);
 800             _ilg.Emit(OpCodes.Dup);
 801             _ilg.Emit(OpCodes.Ldc_I4_1);
 802             _ilg.Emit(OpCodes.Add);
 803             _ilg.Emit(OpCodes.Stloc_S, _trackposV);
 804             _ilg.Emit(OpCodes.Ldelem_I4);
 805         }
 806
 807         /*
 808          * Retrieves the top entry on the tracking stack without popping
 809          */
 810         internal void TopTrack() {
 811             _ilg.Emit(OpCodes.Ldloc_S, _trackV);
 812             _ilg.Emit(OpCodes.Ldloc_S, _trackposV);
 813             _ilg.Emit(OpCodes.Ldelem_I4);
 814         }
 815
 816         /*
 817          * Saves the value of a local variable on the grouping stack
 818          */
 819         internal void PushStack(LocalBuilder lt) {
 820             ReadyPushStack();
 821             _ilg.Emit(OpCodes.Ldloc_S, lt);
 822             DoPush();
 823         }
 824
 825         /*
 826          * Prologue to code that will replace the ith element on the grouping stack
 827          */
 828         internal void ReadyReplaceStack(int i) {
 829             _ilg.Emit(OpCodes.Ldloc_S, _stackV);
 830             _ilg.Emit(OpCodes.Ldloc_S, _stackposV);
 831             if (i != 0) {
 832                 Ldc(i);
 833                 _ilg.Emit(OpCodes.Add);
 834             }
 835         }
 836
 837         /*
 838          * Prologue to code that will push an element on the grouping stack
 839          */
 840         internal void ReadyPushStack() {
 841             _ilg.Emit(OpCodes.Ldloc_S, _stackV);
 842             _ilg.Emit(OpCodes.Ldloc_S, _stackposV);
 843             _ilg.Emit(OpCodes.Ldc_I4_1);
 844             _ilg.Emit(OpCodes.Sub);
 845             _ilg.Emit(OpCodes.Dup);
 846             _ilg.Emit(OpCodes.Stloc_S, _stackposV);
 847         }
 848
 849         /*
 850          * Retrieves the top entry on the stack without popping
 851          */
 852         internal void TopStack() {
 853             _ilg.Emit(OpCodes.Ldloc_S, _stackV);
 854             _ilg.Emit(OpCodes.Ldloc_S, _stackposV);
 855             _ilg.Emit(OpCodes.Ldelem_I4);
 856         }
 857
 858         /*
 859          * Pops an element off the grouping stack (leave it on the operand stack)
 860          */
 861         internal void PopStack() {
 862             _ilg.Emit(OpCodes.Ldloc_S, _stackV);
 863             _ilg.Emit(OpCodes.Ldloc_S, _stackposV);
 864             _ilg.Emit(OpCodes.Dup);
 865             _ilg.Emit(OpCodes.Ldc_I4_1);
 866             _ilg.Emit(OpCodes.Add);
 867             _ilg.Emit(OpCodes.Stloc_S, _stackposV);
 868             _ilg.Emit(OpCodes.Ldelem_I4);
 869         }
 870
 871         /*
 872          * Pops 1 element off the grouping stack and discards it
 873          */
 874         internal void PopDiscardStack() {
 875             PopDiscardStack(1);
 876         }
 877
 878         /*
 879          * Pops i elements off the grouping stack and discards them
 880          */
 881         internal void PopDiscardStack(int i) {
 882             _ilg.Emit(OpCodes.Ldloc_S, _stackposV);
 883             Ldc(i);
 884             _ilg.Emit(OpCodes.Add);
 885             _ilg.Emit(OpCodes.Stloc_S, _stackposV);
 886         }
 887
 888         /*
 889          * Epilogue to code that will replace an element on a stack (use Ld* in between)
 890          */
 891         internal void DoReplace() {
 892             _ilg.Emit(OpCodes.Stelem_I4);
 893         }
 894
 895         /*
 896          * Epilogue to code that will push an element on a stack (use Ld* in between)
 897          */
 898         internal void DoPush() {
 899             _ilg.Emit(OpCodes.Stelem_I4);
 900         }
 901
 902         /*
 903          * Jump to the backtracking switch
 904          */
 905         internal void Back() {
 906             _ilg.Emit(OpCodes.Br, _backtrack);
 907         }
 908
 909         /*
 910          * Branch to the MSIL corresponding to the regex code at i
 911          *
 912          * A trick: since track and stack space is gobbled up unboundedly
 913          * only as a result of branching backwards, this is where we check
 914          * for sufficient space and trigger reallocations.
 915          *
 916          * If the "goto" is backwards, we generate code that checks
 917          * available space against the amount of space that would be needed
 918          * in the worst case by code that will only go forward; if there's
 919          * not enough, we push the destination on the tracking stack, then
 920          * we jump to the place where we invoke the allocator.
 921          *
 922          * Since forward gotos pose no threat, they just turn into a Br.
 923          */
 924         internal void Goto(int i) {
 925             if (i < _codepos) {
 926                 Label l1 = DefineLabel();
 927
 928                 // When going backwards, ensure enough space.
 929                 Ldloc(_trackposV);
 930                 Ldc(_trackcount * 4);
 931                 Ble(l1);
 932                 Ldloc(_stackposV);
 933                 Ldc(_trackcount * 3);
 934                 BgtFar(_labels[i]);
 935                 MarkLabel(l1);
 936                 ReadyPushTrack();
 937                 Ldc(AddGoto(i));
 938                 DoPush();
 939                 BrFar(_backtrack);
 940             }
 941             else {
 942                 BrFar(_labels[i]);
 943             }
 944         }
 945
 946         /*
 947          * Returns the position of the next operation in the regex code, taking
 948          * into account the different numbers of arguments taken by operations
 949          */
 950         internal int NextCodepos() {
 951             return _codepos + RegexCode.OpcodeSize(_codes[_codepos]);
 952         }
 953
 954         /*
 955          * The label for the next (forward) operation
 956          */
 957         internal Label AdvanceLabel() {
 958             return _labels[NextCodepos()];
 959         }
 960
 961         /*
 962          * Goto the next (forward) operation
 963          */
 964         internal void Advance() {
 965             _ilg.Emit(OpCodes.Br, AdvanceLabel());
 966         }
 967
 968         internal void CallToLower()
 969         {
 970             if ((_options & RegexOptions.CultureInvariant) != 0)
 971                 Call(_getInvariantCulture);
 972             else
 973                 Call(_getCurrentCulture);
 974
 975             Call(_chartolowerM);
 976         }
 977
 978         /*
 979          * Generates the first section of the MSIL. This section contains all
 980          * the forward logic, and corresponds directly to the regex codes.
 981          *
 982          * In the absence of backtracking, this is all we would need.
 983          */
 984         internal void GenerateForwardSection() {
 985             int codepos;
 986
 987             _labels = new Label[_codes.Length];
 988             _goto   = new int[_codes.Length];
 989
 990             // initialize
 991
 992             for (codepos = 0; codepos < _codes.Length; codepos += RegexCode.OpcodeSize(_codes[codepos])) {
 993                 _goto[codepos]   = -1;
 994                 _labels[codepos] = _ilg.DefineLabel();
 995             }
 996
 997             _uniquenote   = new int[uniquecount];
 998             for (int i = 0; i < uniquecount; i++)
 999                 _uniquenote[i] = -1;
1000
1001             // emit variable initializers
1002
1003             Mvfldloc(_textF,      _textV);
1004             Mvfldloc(_textstartF, _textstartV);
1005             Mvfldloc(_textbegF,   _textbegV);
1006             Mvfldloc(_textendF,   _textendV);
1007             Mvfldloc(_textposF,   _textposV);
1008             Mvfldloc(_trackF,     _trackV);
1009             Mvfldloc(_trackposF,  _trackposV);
1010             Mvfldloc(_stackF,     _stackV);
1011             Mvfldloc(_stackposF,  _stackposV);
1012
1013             _backpos = -1;
1014
1015             for (codepos = 0; codepos < _codes.Length; codepos += RegexCode.OpcodeSize(_codes[codepos])) {
1016                 MarkLabel(_labels[codepos]);
1017                 _codepos = codepos;
1018                 _regexopcode = _codes[codepos];
1019                 GenerateOneCode();
1020             }
1021         }
1022
1023         /*
1024          * Generates the middle section of the MSIL. This section contains the
1025          * big switch jump that allows us to simulate a stack of addresses,
1026          * and it also contains the calls that expand the tracking and the
1027          * grouping stack when they get too full.
1028          */
1029         internal void GenerateMiddleSection() {
1030 #pragma warning disable 219
1031             Label l1 = DefineLabel();
1032 #pragma warning restore 219
1033             Label[] table;
1034             int i;
1035
1036             // Backtrack switch
1037             MarkLabel(_backtrack);
1038
1039             // first call EnsureStorage
1040             Mvlocfld(_trackposV, _trackposF);
1041             Mvlocfld(_stackposV, _stackposF);
1042             Ldthis();
1043             Callvirt(_ensurestorageM);
1044             Mvfldloc(_trackposF, _trackposV);
1045             Mvfldloc(_stackposF, _stackposV);
1046             Mvfldloc(_trackF, _trackV);
1047             Mvfldloc(_stackF, _stackV);
1048
1049
1050             PopTrack();
1051
1052             table = new Label[_notecount];
1053             for (i = 0; i < _notecount; i++)
1054                 table[i] = _notes[i]._label;
1055
1056             _ilg.Emit(OpCodes.Switch, table);
1057
1058         }
1059
1060         /*
1061          * Generates the last section of the MSIL. This section contains all of
1062          * the backtracking logic.
1063          */
1064         internal void GenerateBacktrackSection() {
1065             int i;
1066
1067             for (i = 0; i < _notecount; i++) {
1068                 BacktrackNote n = _notes[i];
1069                 if (n._flags != 0) {
1070                     _ilg.MarkLabel(n._label);
1071                     _codepos = n._codepos;
1072                     _backpos = i;
1073                     _regexopcode = _codes[n._codepos] | n._flags;
1074                     GenerateOneCode();
1075                 }
1076             }
1077         }
1078
1079         /*
1080          * Generates FindFirstChar
1081          */
1082         // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1083         // !!!! This function must be kept synchronized with FindFirstChar in      !!!!
1084         // !!!! RegexInterpreter.cs                                                !!!!
1085         // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1086         internal void GenerateFindFirstChar() {
1087             _textposV       = DeclareInt();
1088             _textV          = DeclareString();
1089             _tempV          = DeclareInt();
1090             _temp2V         = DeclareInt();
1091
1092             if (0 != (_anchors & (RegexFCD.Beginning | RegexFCD.Start | RegexFCD.EndZ | RegexFCD.End))) {
1093                 if (!_code._rightToLeft) {
1094                     if (0 != (_anchors & RegexFCD.Beginning)) {
1095                         Label l1 = DefineLabel();
1096                         Ldthisfld(_textposF);
1097                         Ldthisfld(_textbegF);
1098                         Ble(l1);
1099                         Ldthis();
1100                         Ldthisfld(_textendF);
1101                         Stfld(_textposF);
1102                         Ldc(0);
1103                         Ret();
1104                         MarkLabel(l1);
1105                     }
1106
1107                     if (0 != (_anchors & RegexFCD.Start)) {
1108                         Label l1 = DefineLabel();
1109                         Ldthisfld(_textposF);
1110                         Ldthisfld(_textstartF);
1111                         Ble(l1);
1112                         Ldthis();
1113                         Ldthisfld(_textendF);
1114                         Stfld(_textposF);
1115                         Ldc(0);
1116                         Ret();
1117                         MarkLabel(l1);
1118                     }
1119
1120                     if (0 != (_anchors & RegexFCD.EndZ)) {
1121                         Label l1 = DefineLabel();
1122                         Ldthisfld(_textposF);
1123                         Ldthisfld(_textendF);
1124                         Ldc(1);
1125                         Sub();
1126                         Bge(l1);
1127                         Ldthis();
1128                         Ldthisfld(_textendF);
1129                         Ldc(1);
1130                         Sub();
1131                         Stfld(_textposF);
1132                         MarkLabel(l1);
1133                     }
1134
1135                     if (0 != (_anchors & RegexFCD.End)) {
1136                         Label l1 = DefineLabel();
1137                         Ldthisfld(_textposF);
1138                         Ldthisfld(_textendF);
1139                         Bge(l1);
1140                         Ldthis();
1141                         Ldthisfld(_textendF);
1142                         Stfld(_textposF);
1143                         MarkLabel(l1);
1144                     }
1145                 }
1146                 else {
1147                     if (0 != (_anchors & RegexFCD.End)) {
1148                         Label l1 = DefineLabel();
1149                         Ldthisfld(_textposF);
1150                         Ldthisfld(_textendF);
1151                         Bge(l1);
1152                         Ldthis();
1153                         Ldthisfld(_textbegF);
1154                         Stfld(_textposF);
1155                         Ldc(0);
1156                         Ret();
1157                         MarkLabel(l1);
1158                     }
1159
1160                     if (0 != (_anchors & RegexFCD.EndZ)) {
1161                         Label l1 = DefineLabel();
1162                         Label l2 = DefineLabel();
1163                         Ldthisfld(_textposF);
1164                         Ldthisfld(_textendF);
1165                         Ldc(1);
1166                         Sub();
1167                         Blt(l1);
1168                         Ldthisfld(_textposF);
1169                         Ldthisfld(_textendF);
1170                         Beq(l2);
1171                         Ldthisfld(_textF);
1172                         Ldthisfld(_textposF);
1173                         Callvirt(_getcharM);
1174                         Ldc((int)'\n');
1175                         Beq(l2);
1176                         MarkLabel(l1);
1177                         Ldthis();
1178                         Ldthisfld(_textbegF);
1179                         Stfld(_textposF);
1180                         Ldc(0);
1181                         Ret();
1182                         MarkLabel(l2);
1183                     }
1184
1185                     if (0 != (_anchors & RegexFCD.Start)) {
1186                         Label l1 = DefineLabel();
1187                         Ldthisfld(_textposF);
1188                         Ldthisfld(_textstartF);
1189                         Bge(l1);
1190                         Ldthis();
1191                         Ldthisfld(_textbegF);
1192                         Stfld(_textposF);
1193                         Ldc(0);
1194                         Ret();
1195                         MarkLabel(l1);
1196                     }
1197
1198                     if (0 != (_anchors & RegexFCD.Beginning)) {
1199                         Label l1 = DefineLabel();
1200                         Ldthisfld(_textposF);
1201                         Ldthisfld(_textbegF);
1202                         Ble(l1);
1203                         Ldthis();
1204                         Ldthisfld(_textbegF);
1205                         Stfld(_textposF);
1206                         MarkLabel(l1);
1207                     }
1208                 }
1209
1210                 // <
1211
1212
1213                 Ldc(1);
1214                 Ret();
1215             }
1216             else if (_bmPrefix != null && _bmPrefix._negativeUnicode == null) {
1217                 // Compiled Boyer-Moore string matching
1218                 // <
1219
1220
1221                 LocalBuilder chV      = _tempV;
1222                 LocalBuilder testV    = _tempV;
1223                 LocalBuilder limitV   = _temp2V;
1224                 Label      lDefaultAdvance  = DefineLabel();
1225                 Label      lAdvance         = DefineLabel();
1226                 Label      lFail            = DefineLabel();
1227                 Label      lStart           = DefineLabel();
1228 #pragma warning disable 219
1229                 Label      lOutOfRange      = DefineLabel();
1230 #pragma warning restore 219
1231                 Label      lPartialMatch    = DefineLabel();
1232
1233
1234                 int chLast;
1235                 int i;
1236                 int beforefirst;
1237                 int last;
1238                 Label[] table;
1239
1240                 if (!_code._rightToLeft) {
1241                     beforefirst = -1;
1242                     last = _bmPrefix._pattern.Length - 1;
1243                 }
1244                 else {
1245                     beforefirst = _bmPrefix._pattern.Length;
1246                     last = 0;
1247                 }
1248
1249                 chLast = _bmPrefix._pattern[last];
1250
1251                 Mvfldloc(_textF, _textV);
1252                 if (!_code._rightToLeft)
1253                     Ldthisfld(_textendF);
1254                 else
1255                     Ldthisfld(_textbegF);
1256                 Stloc(limitV);
1257
1258                 Ldthisfld(_textposF);
1259                 if (!_code._rightToLeft) {
1260                     Ldc(_bmPrefix._pattern.Length - 1);
1261                     Add();
1262                 }
1263                 else {
1264                     Ldc(_bmPrefix._pattern.Length);
1265                     Sub();
1266                 }
1267                 Stloc(_textposV);
1268                 Br(lStart);
1269
1270                 MarkLabel(lDefaultAdvance);
1271
1272                 if (!_code._rightToLeft)
1273                     Ldc(_bmPrefix._pattern.Length);
1274                 else
1275                     Ldc(-_bmPrefix._pattern.Length);
1276
1277                 MarkLabel(lAdvance);
1278
1279                 Ldloc(_textposV);
1280                 Add();
1281                 Stloc(_textposV);
1282
1283                 MarkLabel(lStart);
1284
1285                 Ldloc(_textposV);
1286                 Ldloc(limitV);
1287                 if (!_code._rightToLeft)
1288                     BgeFar(lFail);
1289                 else
1290                     BltFar(lFail);
1291
1292                 Rightchar();
1293                 if (_bmPrefix._caseInsensitive)
1294                     CallToLower();
1295
1296                 Dup();
1297                 Stloc(chV);
1298                 Ldc(chLast);
1299                 BeqFar(lPartialMatch);
1300
1301                 Ldloc(chV);
1302                 Ldc(_bmPrefix._lowASCII);
1303                 Sub();
1304                 Dup();
1305                 Stloc(chV);
1306                 Ldc(_bmPrefix._highASCII - _bmPrefix._lowASCII);
1307                 Bgtun(lDefaultAdvance);
1308
1309                 table = new Label[_bmPrefix._highASCII - _bmPrefix._lowASCII + 1];
1310
1311                 for (i = _bmPrefix._lowASCII; i <= _bmPrefix._highASCII; i++) {
1312                     if (_bmPrefix._negativeASCII[i] == beforefirst)
1313                         table[i - _bmPrefix._lowASCII] = lDefaultAdvance;
1314                     else
1315                         table[i - _bmPrefix._lowASCII] = DefineLabel();
1316                 }
1317
1318                 Ldloc(chV);
1319                 _ilg.Emit(OpCodes.Switch, table);
1320
1321                 for (i = _bmPrefix._lowASCII; i <= _bmPrefix._highASCII; i++) {
1322                     if (_bmPrefix._negativeASCII[i] == beforefirst)
1323                         continue;
1324
1325                     MarkLabel(table[i - _bmPrefix._lowASCII]);
1326
1327                     Ldc(_bmPrefix._negativeASCII[i]);
1328                     BrFar(lAdvance);
1329                 }
1330
1331                 MarkLabel(lPartialMatch);
1332
1333                 Ldloc(_textposV);
1334                 Stloc(testV);
1335
1336                 for (i = _bmPrefix._pattern.Length - 2; i >= 0; i--) {
1337                     Label lNext = DefineLabel();
1338                     int charindex;
1339
1340                     if (!_code._rightToLeft)
1341                         charindex = i;
1342                     else
1343                         charindex = _bmPrefix._pattern.Length - 1 - i;
1344
1345                     Ldloc(_textV);
1346                     Ldloc(testV);
1347                     Ldc(1);
1348                     Sub(_code._rightToLeft);
1349                     Dup();
1350                     Stloc(testV);
1351                     Callvirt(_getcharM);
1352                     if (_bmPrefix._caseInsensitive)
1353                         CallToLower();
1354
1355                     Ldc(_bmPrefix._pattern[charindex]);
1356                     Beq(lNext);
1357                     Ldc(_bmPrefix._positive[charindex]);
1358                     BrFar(lAdvance);
1359
1360                     MarkLabel(lNext);
1361
1362                 }
1363
1364                 Ldthis();
1365                 Ldloc(testV);
1366                 if (_code._rightToLeft) {
1367                     Ldc(1);
1368                     Add();
1369                 }
1370                 Stfld(_textposF);
1371                 Ldc(1);
1372                 Ret();
1373
1374                 MarkLabel(lFail);
1375
1376                 Ldthis();
1377                 if (!_code._rightToLeft)
1378                     Ldthisfld(_textendF);
1379                 else
1380                     Ldthisfld(_textbegF);
1381                 Stfld(_textposF);
1382                 Ldc(0);
1383                 Ret();
1384             }
1385             else if (_fcPrefix == null) {
1386                 Ldc(1);
1387                 Ret();
1388             }
1389             else {
1390                 LocalBuilder cV   = _temp2V;
1391 #pragma warning disable 219
1392                 LocalBuilder chV  = _tempV;
1393 #pragma warning restore 219
1394                 Label      l1   = DefineLabel();
1395                 Label      l2   = DefineLabel();
1396                 Label      l3   = DefineLabel();
1397                 Label      l4   = DefineLabel();
1398                 Label      l5   = DefineLabel();
1399
1400                 Mvfldloc(_textposF, _textposV);
1401                 Mvfldloc(_textF, _textV);
1402
1403                 if (!_code._rightToLeft) {
1404                     Ldthisfld(_textendF);
1405                     Ldloc(_textposV);
1406                 }
1407                 else {
1408                     Ldloc(_textposV);
1409                     Ldthisfld(_textbegF);
1410                 }
1411                 Sub();
1412                 Stloc(cV);
1413
1414                 Ldloc(cV);
1415                 Ldc(0);
1416                 BleFar(l4);
1417
1418                 MarkLabel(l1);
1419
1420                 Ldloc(cV);
1421                 Ldc(1);
1422                 Sub();
1423                 Stloc(cV);
1424
1425                 if (_code._rightToLeft)
1426                     Leftcharnext();
1427                 else
1428                     Rightcharnext();
1429
1430                 if (_fcPrefix.CaseInsensitive)
1431                     CallToLower();
1432
1433                 if (!RegexCharClass.IsSingleton(_fcPrefix.Prefix)) {
1434                     Ldstr(_fcPrefix.Prefix);
1435                     Call(_charInSetM);
1436
1437                     BrtrueFar(l2);
1438                 }
1439                 else {
1440                     Ldc(RegexCharClass.SingletonChar(_fcPrefix.Prefix));
1441                     Beq(l2);
1442                 }
1443
1444                 MarkLabel(l5);
1445
1446                 Ldloc(cV);
1447                 Ldc(0);
1448                 if (!RegexCharClass.IsSingleton(_fcPrefix.Prefix))
1449                     BgtFar(l1);
1450                 else
1451                     Bgt(l1);
1452
1453                 Ldc(0);
1454                 BrFar(l3);
1455
1456                 MarkLabel(l2);
1457
1458                 /*          // CURRENTLY DISABLED
1459                             // If for some reason we have a prefix we didn't use, use it now.
1460
1461                             if (_bmPrefix != null) {
1462                                 if (!_code._rightToLeft) {
1463                                     Ldthisfld(_textendF);
1464                                     Ldloc(_textposV);
1465                                 }
1466                                 else {
1467                                     Ldloc(_textposV);
1468                                     Ldthisfld(_textbegF);
1469                                 }
1470                                 Sub();
1471                                 Ldc(_bmPrefix._pattern.Length - 1);
1472                                 BltFar(l5);
1473
1474                                 for (int i = 1; i < _bmPrefix._pattern.Length; i++) {
1475                                     Ldloc(_textV);
1476                                     Ldloc(_textposV);
1477                                     if (!_code._rightToLeft) {
1478                                         Ldc(i - 1);
1479                                         Add();
1480                                     }
1481                                     else {
1482                                         Ldc(i);
1483                                         Sub();
1484                                     }
1485                                     Callvirt(_getcharM);
1486                                     if (!_code._rightToLeft)
1487                                         Ldc(_bmPrefix._pattern[i]);
1488                                     else
1489                                         Ldc(_bmPrefix._pattern[_bmPrefix._pattern.Length - 1 - i]);
1490                                     BneFar(l5);
1491                                 }
1492                             }
1493                 */
1494
1495                 Ldloc(_textposV);
1496                 Ldc(1);
1497                 Sub(_code._rightToLeft);
1498                 Stloc(_textposV);
1499                 Ldc(1);
1500
1501                 MarkLabel(l3);
1502
1503                 Mvlocfld(_textposV, _textposF);
1504                 Ret();
1505
1506                 MarkLabel(l4);
1507                 Ldc(0);
1508                 Ret();
1509             }
1510
1511         }
1512
1513         /*
1514          * Generates a very simple method that sets the _trackcount field.
1515          */
1516         internal void GenerateInitTrackCount() {
1517             Ldthis();
1518             Ldc(_trackcount);
1519             Stfld(_trackcountF);
1520             Ret();
1521         }
1522
1523         /*
1524          * Declares a local int
1525          */
1526         internal LocalBuilder DeclareInt() {
1527             return _ilg.DeclareLocal(typeof(int));
1528         }
1529
1530         /*
1531          * Declares a local int array
1532          */
1533         internal LocalBuilder DeclareIntArray() {
1534             return _ilg.DeclareLocal(typeof(int[]));
1535         }
1536
1537         /*
1538          * Declares a local string
1539          */
1540         internal LocalBuilder DeclareString() {
1541             return _ilg.DeclareLocal(typeof(string));
1542         }
1543
1544         /*
1545          * Generates the code for "RegexRunner.Go"
1546          */
1547         internal void GenerateGo() {
1548             // declare some locals
1549
1550             _textposV       = DeclareInt();
1551             _textV          = DeclareString();
1552             _trackposV      = DeclareInt();
1553             _trackV         = DeclareIntArray();
1554             _stackposV      = DeclareInt();
1555             _stackV         = DeclareIntArray();
1556             _tempV          = DeclareInt();
1557             _temp2V         = DeclareInt();
1558             _temp3V         = DeclareInt();
1559             _textbegV       = DeclareInt();
1560             _textendV       = DeclareInt();
1561             _textstartV     = DeclareInt();
1562
1563             // clear some tables
1564
1565             _labels = null;
1566             _notes = null;
1567             _notecount = 0;
1568
1569             // globally used labels
1570
1571             _backtrack = DefineLabel();
1572
1573             // emit the code!
1574
1575             GenerateForwardSection();
1576             GenerateMiddleSection();
1577             GenerateBacktrackSection();
1578         }
1579
1580 #if DBG
1581         /*
1582          * Some simple debugging stuff
1583          */
1584         internal static MethodInfo _debugWriteLine = typeof(Debug).GetMethod("WriteLine", new Type[] {typeof(string)});
1585
1586         /*
1587          * Debug only: emit code to print out a message
1588          */
1589         internal void Message(String str) {
1590             Ldstr(str);
1591             Call(_debugWriteLine);
1592         }
1593
1594 #endif
1595
1596         /*
1597          * The main translation function. It translates the logic for a single opcode at
1598          * the current position. The structure of this function exactly mirrors
1599          * the structure of the inner loop of RegexInterpreter.Go().
1600          *
1601          * The C# code from RegexInterpreter.Go() that corresponds to each case is
1602          * included as a comment.
1603          *
1604          * Note that since we're generating code, we can collapse many cases that are
1605          * dealt with one-at-a-time in RegexIntepreter. We can also unroll loops that
1606          * iterate over constant strings or sets.
1607          */
1608         internal void GenerateOneCode() {
1609 #if DBG
1610             if ((_options & RegexOptions.Debug) != 0) {
1611                 Mvlocfld(_textposV, _textposF);
1612                 Mvlocfld(_trackposV, _trackposF);
1613                 Mvlocfld(_stackposV, _stackposF);
1614                 Ldthis();
1615                 Callvirt(_dumpstateM);
1616                 StringBuilder sb = new StringBuilder();
1617                 if (_backpos > 0)
1618                     sb.AppendFormat("{0:D6} ", _backpos);
1619                 else
1620                     sb.Append("       ");
1621                 sb.Append(_code.OpcodeDescription(_codepos));
1622                 if (IsBack())
1623                     sb.Append(" Back");
1624                 if (IsBack2())
1625                     sb.Append(" Back2");
1626                 Message(sb.ToString());
1627             }
1628 #endif
1629
1630             // Before executing any RegEx code in the unrolled loop,
1631             // we try checking for the match timeout:
1632
1633             Ldthis();
1634             Callvirt(_checkTimeoutM);
1635
1636             // Now generate the IL for the RegEx code saved in _regexopcode.
1637             // We unroll the loop done by the RegexCompiler creating as very long method
1638             // that is longer if the pattern is longer:
1639
1640             switch (_regexopcode) {
1641                 case RegexCode.Stop:
1642                     //: return;
1643                     Mvlocfld(_textposV, _textposF);       // update _textpos
1644                     Ret();
1645                     break;
1646
1647                 case RegexCode.Nothing:
1648                     //: break Backward;
1649                     Back();
1650                     break;
1651
1652                 case RegexCode.Goto:
1653                     //: Goto(Operand(0));
1654                     Goto(Operand(0));
1655                     break;
1656
1657                 case RegexCode.Testref:
1658                     //: if (!_match.IsMatched(Operand(0)))
1659                     //:     break Backward;
1660                     Ldthis();
1661                     Ldc(Operand(0));
1662                     Callvirt(_ismatchedM);
1663                     BrfalseFar(_backtrack);
1664                     break;
1665
1666                 case RegexCode.Lazybranch:
1667                     //: Track(Textpos());
1668                     PushTrack(_textposV);
1669                     Track();
1670                     break;
1671
1672                 case RegexCode.Lazybranch | RegexCode.Back:
1673                     //: Trackframe(1);
1674                     //: Textto(Tracked(0));
1675                     //: Goto(Operand(0));
1676                     PopTrack();
1677                     Stloc(_textposV);
1678                     Goto(Operand(0));
1679                     break;
1680
1681                 case RegexCode.Nullmark:
1682                     //: Stack(-1);
1683                     //: Track();
1684                     ReadyPushStack();
1685                     Ldc(-1);
1686                     DoPush();
1687                     TrackUnique(stackpop);
1688                     break;
1689
1690                 case RegexCode.Setmark:
1691                     //: Stack(Textpos());
1692                     //: Track();
1693                     PushStack(_textposV);
1694                     TrackUnique(stackpop);
1695                     break;
1696
1697                 case RegexCode.Nullmark | RegexCode.Back:
1698                 case RegexCode.Setmark | RegexCode.Back:
1699                     //: Stackframe(1);
1700                     //: break Backward;
1701                     PopDiscardStack();
1702                     Back();
1703                     break;
1704
1705                 case RegexCode.Getmark:
1706                     //: Stackframe(1);
1707                     //: Track(Stacked(0));
1708                     //: Textto(Stacked(0));
1709                     ReadyPushTrack();
1710                     PopStack();
1711                     Dup();
1712                     Stloc(_textposV);
1713                     DoPush();
1714
1715                     Track();
1716                     break;
1717
1718                 case RegexCode.Getmark | RegexCode.Back:
1719                     //: Trackframe(1);
1720                     //: Stack(Tracked(0));
1721                     //: break Backward;
1722                     ReadyPushStack();
1723                     PopTrack();
1724                     DoPush();
1725                     Back();
1726                     break;
1727
1728                 case RegexCode.Capturemark:
1729                     //: if (!IsMatched(Operand(1)))
1730                     //:     break Backward;
1731                     //: Stackframe(1);
1732                     //: if (Operand(1) != -1)
1733                     //:     TransferCapture(Operand(0), Operand(1), Stacked(0), Textpos());
1734                     //: else
1735                     //:     Capture(Operand(0), Stacked(0), Textpos());
1736                     //: Track(Stacked(0));
1737
1738                     //: Stackframe(1);
1739                     //: Capture(Operand(0), Stacked(0), Textpos());
1740                     //: Track(Stacked(0));
1741
1742                     if (Operand(1) != -1) {
1743                         Ldthis();
1744                         Ldc(Operand(1));
1745                         Callvirt(_ismatchedM);
1746                         BrfalseFar(_backtrack);
1747                     }
1748
1749                     PopStack();
1750                     Stloc(_tempV);
1751
1752                     if (Operand(1) != -1) {
1753                         Ldthis();
1754                         Ldc(Operand(0));
1755                         Ldc(Operand(1));
1756                         Ldloc(_tempV);
1757                         Ldloc(_textposV);
1758                         Callvirt(_transferM);
1759                     }
1760                     else {
1761                         Ldthis();
1762                         Ldc(Operand(0));
1763                         Ldloc(_tempV);
1764                         Ldloc(_textposV);
1765                         Callvirt(_captureM);
1766                     }
1767
1768                     PushTrack(_tempV);
1769
1770                     if (Operand(0) != -1 && Operand(1) != -1)
1771                         TrackUnique(capback2);
1772                     else
1773                         TrackUnique(capback);
1774
1775                     break;
1776
1777
1778                 case RegexCode.Capturemark | RegexCode.Back:
1779                     //: Trackframe(1);
1780                     //: Stack(Tracked(0));
1781                     //: Uncapture();
1782                     //: if (Operand(0) != -1 && Operand(1) != -1)
1783                     //:     Uncapture();
1784                     //: break Backward;
1785                     ReadyPushStack();
1786                     PopTrack();
1787                     DoPush();
1788                     Ldthis();
1789                     Callvirt(_uncaptureM);
1790                     if (Operand(0) != -1 && Operand(1) != -1) {
1791                         Ldthis();
1792                         Callvirt(_uncaptureM);
1793                     }
1794                     Back();
1795                     break;
1796
1797                 case RegexCode.Branchmark:
1798                     //: Stackframe(1);
1799                     //:
1800                     //: if (Textpos() != Stacked(0))
1801                     //: {                                   // Nonempty match -> loop now
1802                     //:     Track(Stacked(0), Textpos());   // Save old mark, textpos
1803                     //:     Stack(Textpos());               // Make new mark
1804                     //:     Goto(Operand(0));               // Loop
1805                     //: }
1806                     //: else
1807                     //: {                                   // Empty match -> straight now
1808                     //:     Track2(Stacked(0));             // Save old mark
1809                     //:     Advance(1);                     // Straight
1810                     //: }
1811                     //: continue Forward;
1812                     {
1813                         LocalBuilder mark = _tempV;
1814                         Label      l1   = DefineLabel();
1815
1816                         PopStack();
1817                         Dup();
1818                         Stloc(mark);                            // Stacked(0) -> temp
1819                         PushTrack(mark);
1820                         Ldloc(_textposV);
1821                         Beq(l1);                                // mark == textpos -> branch
1822
1823                         // (matched != 0)
1824
1825                         PushTrack(_textposV);
1826                         PushStack(_textposV);
1827                         Track();
1828                         Goto(Operand(0));                       // Goto(Operand(0))
1829
1830                         // else
1831
1832                         MarkLabel(l1);
1833                         TrackUnique2(branchmarkback2);
1834                         break;
1835                     }
1836
1837                 case RegexCode.Branchmark | RegexCode.Back:
1838                     //: Trackframe(2);
1839                     //: Stackframe(1);
1840                     //: Textto(Tracked(1));                     // Recall position
1841                     //: Track2(Tracked(0));                     // Save old mark
1842                     //: Advance(1);
1843                     PopTrack();
1844                     Stloc(_textposV);
1845                     PopStack();
1846                     Pop();
1847                     // track spot 0 is already in place
1848                     TrackUnique2(branchmarkback2);
1849                     Advance();
1850                     break;
1851
1852                 case RegexCode.Branchmark | RegexCode.Back2:
1853                     //: Trackframe(1);
1854                     //: Stack(Tracked(0));                      // Recall old mark
1855                     //: break Backward;                         // Backtrack
1856                     ReadyPushStack();
1857                     PopTrack();
1858                     DoPush();
1859                     Back();
1860                     break;
1861
1862
1863                 case RegexCode.Lazybranchmark:
1864                     //: StackPop();
1865                     //: int oldMarkPos = StackPeek();
1866                     //:
1867                     //: if (Textpos() != oldMarkPos) {         // Nonempty match -> next loop
1868                     //: {                                   // Nonempty match -> next loop
1869                     //:     if (oldMarkPos != -1)
1870                     //:         Track(Stacked(0), Textpos());   // Save old mark, textpos
1871                     //:     else
1872                     //:         TrackPush(Textpos(), Textpos());
1873                     //: }
1874                     //: else
1875                     //: {                                   // Empty match -> no loop
1876                     //:     Track2(Stacked(0));             // Save old mark
1877                     //: }
1878                     //: Advance(1);
1879                     //: continue Forward;
1880                     {
1881                         LocalBuilder mark = _tempV;
1882                         Label      l1   = DefineLabel();
1883                         Label      l2   = DefineLabel();
1884                         Label      l3   = DefineLabel();
1885
1886                         PopStack();
1887                         Dup();
1888                         Stloc(mark);                      // Stacked(0) -> temp
1889
1890                         // if (oldMarkPos != -1)
1891                         Ldloc(mark);
1892                         Ldc(-1);
1893                         Beq(l2);                                // mark == -1 -> branch
1894                             PushTrack(mark);
1895                             Br(l3);
1896                         // else
1897                             MarkLabel(l2);
1898                             PushTrack(_textposV);
1899                         MarkLabel(l3);
1900
1901                         // if (Textpos() != mark)
1902                         Ldloc(_textposV);
1903                         Beq(l1);                                // mark == textpos -> branch
1904                             PushTrack(_textposV);
1905                             Track();
1906                             Br(AdvanceLabel());                 // Advance (near)
1907                         // else
1908                             MarkLabel(l1);
1909                             ReadyPushStack();                   // push the current textPos on the stack.
1910                                                                 // May be ignored by 'back2' or used by a true empty match.
1911                             Ldloc(mark);
1912
1913                             DoPush();
1914                             TrackUnique2(lazybranchmarkback2);
1915
1916                         break;
1917                     }
1918
1919                 case RegexCode.Lazybranchmark | RegexCode.Back:
1920                     //: Trackframe(2);
1921                     //: Track2(Tracked(0));                     // Save old mark
1922                     //: Stack(Textpos());                       // Make new mark
1923                     //: Textto(Tracked(1));                     // Recall position
1924                     //: Goto(Operand(0));                       // Loop
1925
1926                     PopTrack();
1927                     Stloc(_textposV);
1928                     PushStack(_textposV);
1929                     TrackUnique2(lazybranchmarkback2);
1930                     Goto(Operand(0));
1931                     break;
1932
1933                 case RegexCode.Lazybranchmark | RegexCode.Back2:
1934                     //: Stackframe(1);
1935                     //: Trackframe(1);
1936                     //: Stack(Tracked(0));                  // Recall old mark
1937                     //: break Backward;
1938                     ReadyReplaceStack(0);
1939                     PopTrack();
1940                     DoReplace();
1941                     Back();
1942                     break;
1943
1944                 case RegexCode.Nullcount:
1945                     //: Stack(-1, Operand(0));
1946                     //: Track();
1947                     ReadyPushStack();
1948                     Ldc(-1);
1949                     DoPush();
1950                     ReadyPushStack();
1951                     Ldc(Operand(0));
1952                     DoPush();
1953                     TrackUnique(stackpop2);
1954                     break;
1955
1956                 case RegexCode.Setcount:
1957                     //: Stack(Textpos(), Operand(0));
1958                     //: Track();
1959                     PushStack(_textposV);
1960                     ReadyPushStack();
1961                     Ldc(Operand(0));
1962                     DoPush();
1963                     TrackUnique(stackpop2);
1964                     break;
1965
1966
1967                 case RegexCode.Nullcount | RegexCode.Back:
1968                 case RegexCode.Setcount | RegexCode.Back:
1969                     //: Stackframe(2);
1970                     //: break Backward;
1971                     PopDiscardStack(2);
1972                     Back();
1973                     break;
1974
1975
1976                 case RegexCode.Branchcount:
1977                     //: Stackframe(2);
1978                     //: int mark = Stacked(0);
1979                     //: int count = Stacked(1);
1980                     //:
1981                     //: if (count >= Operand(1) || Textpos() == mark && count >= 0)
1982                     //: {                                   // Max loops or empty match -> straight now
1983                     //:     Track2(mark, count);            // Save old mark, count
1984                     //:     Advance(2);                     // Straight
1985                     //: }
1986                     //: else
1987                     //: {                                   // Nonempty match -> count+loop now
1988                     //:     Track(mark);                    // remember mark
1989                     //:     Stack(Textpos(), count + 1);    // Make new mark, incr count
1990                     //:     Goto(Operand(0));               // Loop
1991                     //: }
1992                     //: continue Forward;
1993                     {
1994                         LocalBuilder count = _tempV;
1995                         LocalBuilder mark  = _temp2V;
1996                         Label      l1    = DefineLabel();
1997                         Label      l2    = DefineLabel();
1998
1999                         PopStack();
2000                         Stloc(count);                           // count -> temp
2001                         PopStack();
2002                         Dup();
2003                         Stloc(mark);                            // mark -> temp2
2004                         PushTrack(mark);
2005
2006                         Ldloc(_textposV);
2007                         Bne(l1);                                // mark != textpos -> l1
2008                         Ldloc(count);
2009                         Ldc(0);
2010                         Bge(l2);                                // count >= 0 && mark == textpos -> l2
2011
2012                         MarkLabel(l1);
2013                         Ldloc(count);
2014                         Ldc(Operand(1));
2015                         Bge(l2);                                // count >= Operand(1) -> l2
2016
2017                         // else
2018                         PushStack(_textposV);
2019                         ReadyPushStack();
2020                         Ldloc(count);                           // mark already on track
2021                         Ldc(1);
2022                         Add();
2023                         DoPush();
2024                         Track();
2025                         Goto(Operand(0));
2026
2027                         // if (count >= Operand(1) || Textpos() == mark)
2028                         MarkLabel(l2);
2029                         PushTrack(count);                       // mark already on track
2030                         TrackUnique2(branchcountback2);
2031                         break;
2032                     }
2033
2034                 case RegexCode.Branchcount | RegexCode.Back:
2035                     //: Trackframe(1);
2036                     //: Stackframe(2);
2037                     //: if (Stacked(1) > 0)                     // Positive -> can go straight
2038                     //: {
2039                     //:     Textto(Stacked(0));                 // Zap to mark
2040                     //:     Track2(Tracked(0), Stacked(1) - 1); // Save old mark, old count
2041                     //:     Advance(2);                         // Straight
2042                     //:     continue Forward;
2043                     //: }
2044                     //: Stack(Tracked(0), Stacked(1) - 1);      // recall old mark, old count
2045                     //: break Backward;
2046                     {
2047
2048                         LocalBuilder count = _tempV;
2049                         Label      l1    = DefineLabel();
2050                         PopStack();
2051                         Ldc(1);
2052                         Sub();
2053                         Dup();
2054                         Stloc(count);
2055                         Ldc(0);
2056                         Blt(l1);
2057
2058                         // if (count >= 0)
2059                         PopStack();
2060                         Stloc(_textposV);
2061                         PushTrack(count);                       // Tracked(0) is alredy on the track
2062                         TrackUnique2(branchcountback2);
2063                         Advance();
2064
2065                         // else
2066                         MarkLabel(l1);
2067                         ReadyReplaceStack(0);
2068                         PopTrack();
2069                         DoReplace();
2070                         PushStack(count);
2071                         Back();
2072                         break;
2073                     }
2074
2075                 case RegexCode.Branchcount | RegexCode.Back2:
2076                     //: Trackframe(2);
2077                     //: Stack(Tracked(0), Tracked(1));      // Recall old mark, old count
2078                     //: break Backward;                     // Backtrack
2079
2080                     PopTrack();
2081                     Stloc(_tempV);
2082                     ReadyPushStack();
2083                     PopTrack();
2084                     DoPush();
2085                     PushStack(_tempV);
2086                     Back();
2087                     break;
2088
2089                 case RegexCode.Lazybranchcount:
2090                     //: Stackframe(2);
2091                     //: int mark = Stacked(0);
2092                     //: int count = Stacked(1);
2093                     //:
2094                     //: if (count < 0)
2095                     //: {                                   // Negative count -> loop now
2096                     //:     Track2(mark);                   // Save old mark
2097                     //:     Stack(Textpos(), count + 1);    // Make new mark, incr count
2098                     //:     Goto(Operand(0));               // Loop
2099                     //: }
2100                     //: else
2101                     //: {                                   // Nonneg count or empty match -> straight now
2102                     //:     Track(mark, count, Textpos());  // Save mark, count, position
2103                     //: }
2104                     {
2105                         LocalBuilder count = _tempV;
2106                         LocalBuilder mark  = _temp2V;
2107                         Label      l1    = DefineLabel();
2108 #pragma warning disable 219
2109                         Label      l2    = DefineLabel();
2110                         Label      l3    = _labels[NextCodepos()];
2111 #pragma warning restore 219
2112
2113                         PopStack();
2114                         Stloc(count);                           // count -> temp
2115                         PopStack();
2116                         Stloc(mark);                            // mark -> temp2
2117
2118                         Ldloc(count);
2119                         Ldc(0);
2120                         Bge(l1);                                // count >= 0 -> l1
2121
2122                         // if (count < 0)
2123                         PushTrack(mark);
2124                         PushStack(_textposV);
2125                         ReadyPushStack();
2126                         Ldloc(count);
2127                         Ldc(1);
2128                         Add();
2129                         DoPush();
2130                         TrackUnique2(lazybranchcountback2);
2131                         Goto(Operand(0));
2132
2133                         // else
2134                         MarkLabel(l1);
2135                         PushTrack(mark);
2136                         PushTrack(count);
2137                         PushTrack(_textposV);
2138                         Track();
2139                         break;
2140                     }
2141
2142                 case RegexCode.Lazybranchcount | RegexCode.Back:
2143                     //: Trackframe(3);
2144                     //: int mark = Tracked(0);
2145                     //: int textpos = Tracked(2);
2146                     //: if (Tracked(1) < Operand(1) && textpos != mark)
2147                     //: {                                       // Under limit and not empty match -> loop
2148                     //:     Textto(Tracked(2));                 // Recall position
2149                     //:     Stack(Textpos(), Tracked(1) + 1);   // Make new mark, incr count
2150                     //:     Track2(Tracked(0));                 // Save old mark
2151                     //:     Goto(Operand(0));                   // Loop
2152                     //:     continue Forward;
2153                     //: }
2154                     //: else
2155                     //: {
2156                     //:     Stack(Tracked(0), Tracked(1));      // Recall old mark, count
2157                     //:     break Backward;                     // backtrack
2158                     //: }
2159                     {
2160                         Label       l1 = DefineLabel();
2161                         LocalBuilder  cV = _tempV;
2162                         PopTrack();
2163                         Stloc(_textposV);
2164                         PopTrack();
2165                         Dup();
2166                         Stloc(cV);
2167                         Ldc(Operand(1));
2168                         Bge(l1);                                // Tracked(1) >= Operand(1) -> l1
2169
2170                         Ldloc(_textposV);
2171                         TopTrack();
2172                         Beq(l1);                                // textpos == mark -> l1
2173
2174                         PushStack(_textposV);
2175                         ReadyPushStack();
2176                         Ldloc(cV);
2177                         Ldc(1);
2178                         Add();
2179                         DoPush();
2180                         TrackUnique2(lazybranchcountback2);
2181                         Goto(Operand(0));
2182
2183                         MarkLabel(l1);
2184                         ReadyPushStack();
2185                         PopTrack();
2186                         DoPush();
2187                         PushStack(cV);
2188                         Back();
2189                         break;
2190                     }
2191
2192                 case RegexCode.Lazybranchcount | RegexCode.Back2:
2193                     // <
2194
2195
2196
2197
2198
2199                     ReadyReplaceStack(1);
2200                     PopTrack();
2201                     DoReplace();
2202                     ReadyReplaceStack(0);
2203                     TopStack();
2204                     Ldc(1);
2205                     Sub();
2206                     DoReplace();
2207                     Back();
2208                     break;
2209
2210
2211                 case RegexCode.Setjump:
2212                     //: Stack(Trackpos(), Crawlpos());
2213                     //: Track();
2214                     ReadyPushStack();
2215                     Ldthisfld(_trackF);
2216                     Ldlen();
2217                     Ldloc(_trackposV);
2218                     Sub();
2219                     DoPush();
2220                     ReadyPushStack();
2221                     Ldthis();
2222                     Callvirt(_crawlposM);
2223                     DoPush();
2224                     TrackUnique(stackpop2);
2225                     break;
2226
2227                 case RegexCode.Setjump | RegexCode.Back:
2228                     //: Stackframe(2);
2229                     PopDiscardStack(2);
2230                     Back();
2231                     break;
2232
2233
2234                 case RegexCode.Backjump:
2235                     //: Stackframe(2);
2236                     //: Trackto(Stacked(0));
2237                     //: while (Crawlpos() != Stacked(1))
2238                     //:     Uncapture();
2239                     //: break Backward;
2240                     {
2241                         Label      l1    = DefineLabel();
2242                         Label      l2    = DefineLabel();
2243
2244                         PopStack();
2245                         Ldthisfld(_trackF);
2246                         Ldlen();
2247                         PopStack();
2248                         Sub();
2249                         Stloc(_trackposV);
2250                         Dup();
2251                         Ldthis();
2252                         Callvirt(_crawlposM);
2253                         Beq(l2);
2254
2255                         MarkLabel(l1);
2256                         Ldthis();
2257                         Callvirt(_uncaptureM);
2258                         Dup();
2259                         Ldthis();
2260                         Callvirt(_crawlposM);
2261                         Bne(l1);
2262
2263                         MarkLabel(l2);
2264                         Pop();
2265                         Back();
2266                         break;
2267                     }
2268
2269                 case RegexCode.Forejump:
2270                     //: Stackframe(2);
2271                     //: Trackto(Stacked(0));
2272                     //: Track(Stacked(1));
2273                     PopStack();
2274                     Stloc(_tempV);
2275                     Ldthisfld(_trackF);
2276                     Ldlen();
2277                     PopStack();
2278                     Sub();
2279                     Stloc(_trackposV);
2280                     PushTrack(_tempV);
2281                     TrackUnique(forejumpback);
2282                     break;
2283
2284                 case RegexCode.Forejump | RegexCode.Back:
2285                     //: Trackframe(1);
2286                     //: while (Crawlpos() != Tracked(0))
2287                     //:     Uncapture();
2288                     //: break Backward;
2289                     {
2290                         Label      l1    = DefineLabel();
2291                         Label      l2    = DefineLabel();
2292
2293                         PopTrack();
2294
2295                         Dup();
2296                         Ldthis();
2297                         Callvirt(_crawlposM);
2298                         Beq(l2);
2299
2300                         MarkLabel(l1);
2301                         Ldthis();
2302                         Callvirt(_uncaptureM);
2303                         Dup();
2304                         Ldthis();
2305                         Callvirt(_crawlposM);
2306                         Bne(l1);
2307
2308                         MarkLabel(l2);
2309                         Pop();
2310                         Back();
2311                         break;
2312                     }
2313
2314                 case RegexCode.Bol:
2315                     //: if (Leftchars() > 0 && CharAt(Textpos() - 1) != '\n')
2316                     //:     break Backward;
2317                     {
2318                         Label      l1    = _labels[NextCodepos()];
2319                         Ldloc(_textposV);
2320                         Ldloc(_textbegV);
2321                         Ble(l1);
2322                         Leftchar();
2323                         Ldc((int)'\n');
2324                         BneFar(_backtrack);
2325                         break;
2326                     }
2327
2328                 case RegexCode.Eol:
2329                     //: if (Rightchars() > 0 && CharAt(Textpos()) != '\n')
2330                     //:     break Backward;
2331                     {
2332                         Label      l1    = _labels[NextCodepos()];
2333                         Ldloc(_textposV);
2334                         Ldloc(_textendV);
2335                         Bge(l1);
2336                         Rightchar();
2337                         Ldc((int)'\n');
2338                         BneFar(_backtrack);
2339                         break;
2340                     }
2341
2342                 case RegexCode.Boundary:
2343                 case RegexCode.Nonboundary:
2344                     //: if (!IsBoundary(Textpos(), _textbeg, _textend))
2345                     //:     break Backward;
2346                     Ldthis();
2347                     Ldloc(_textposV);
2348                     Ldloc(_textbegV);
2349                     Ldloc(_textendV);
2350                     Callvirt(_isboundaryM);
2351                     if (Code() == RegexCode.Boundary)
2352                         BrfalseFar(_backtrack);
2353                     else
2354                         BrtrueFar(_backtrack);
2355                     break;
2356
2357                 case RegexCode.ECMABoundary:
2358                 case RegexCode.NonECMABoundary:
2359                     //: if (!IsECMABoundary(Textpos(), _textbeg, _textend))
2360                     //:     break Backward;
2361                     Ldthis();
2362                     Ldloc(_textposV);
2363                     Ldloc(_textbegV);
2364                     Ldloc(_textendV);
2365                     Callvirt(_isECMABoundaryM);
2366                     if (Code() == RegexCode.ECMABoundary)
2367                         BrfalseFar(_backtrack);
2368                     else
2369                         BrtrueFar(_backtrack);
2370                     break;
2371
2372                 case RegexCode.Beginning:
2373                     //: if (Leftchars() > 0)
2374                     //:    break Backward;
2375                     Ldloc(_textposV);
2376                     Ldloc(_textbegV);
2377                     BgtFar(_backtrack);
2378                     break;
2379
2380                 case RegexCode.Start:
2381                     //: if (Textpos() != Textstart())
2382                     //:    break Backward;
2383                     Ldloc(_textposV);
2384                     Ldthisfld(_textstartF);
2385                     BneFar(_backtrack);
2386                     break;
2387
2388                 case RegexCode.EndZ:
2389                     //: if (Rightchars() > 1 || Rightchars() == 1 && CharAt(Textpos()) != '\n')
2390                     //:    break Backward;
2391                     Ldloc(_textposV);
2392                     Ldloc(_textendV);
2393                     Ldc(1);
2394                     Sub();
2395                     BltFar(_backtrack);
2396                     Ldloc(_textposV);
2397                     Ldloc(_textendV);
2398                     Bge(_labels[NextCodepos()]);
2399                     Rightchar();
2400                     Ldc((int)'\n');
2401                     BneFar(_backtrack);
2402                     break;
2403
2404                 case RegexCode.End:
2405                     //: if (Rightchars() > 0)
2406                     //:    break Backward;
2407                     Ldloc(_textposV);
2408                     Ldloc(_textendV);
2409                     BltFar(_backtrack);
2410                     break;
2411
2412                 case RegexCode.One:
2413                 case RegexCode.Notone:
2414                 case RegexCode.Set:
2415                 case RegexCode.One      | RegexCode.Rtl:
2416                 case RegexCode.Notone   | RegexCode.Rtl:
2417                 case RegexCode.Set      | RegexCode.Rtl:
2418                 case RegexCode.One      | RegexCode.Ci:
2419                 case RegexCode.Notone   | RegexCode.Ci:
2420                 case RegexCode.Set      | RegexCode.Ci:
2421                 case RegexCode.One      | RegexCode.Ci  | RegexCode.Rtl:
2422                 case RegexCode.Notone   | RegexCode.Ci  | RegexCode.Rtl:
2423                 case RegexCode.Set      | RegexCode.Ci  | RegexCode.Rtl:
2424
2425                     //: if (Rightchars() < 1 || Rightcharnext() != (char)Operand(0))
2426                     //:    break Backward;
2427                     Ldloc(_textposV);
2428
2429                     if (!IsRtl()) {
2430                         Ldloc(_textendV);
2431                         BgeFar(_backtrack);
2432                         Rightcharnext();
2433                     }
2434                     else {
2435                         Ldloc(_textbegV);
2436                         BleFar(_backtrack);
2437                         Leftcharnext();
2438                     }
2439
2440                     if (IsCi())
2441                         CallToLower();
2442
2443                     if (Code() == RegexCode.Set) {
2444
2445                         Ldstr(_strings[Operand(0)]);
2446                         Call(_charInSetM);
2447
2448                         BrfalseFar(_backtrack);
2449                     }
2450                     else {
2451                         Ldc(Operand(0));
2452                         if (Code() == RegexCode.One)
2453                             BneFar(_backtrack);
2454                         else
2455                             BeqFar(_backtrack);
2456                     }
2457                     break;
2458
2459                 case RegexCode.Multi:
2460                 case RegexCode.Multi | RegexCode.Ci:
2461                     //
2462                     // <
2463
2464
2465
2466
2467
2468
2469                     //: String Str = _strings[Operand(0)];
2470                     //: int i, c;
2471                     //: if (Rightchars() < (c = Str.Length))
2472                     //:     break Backward;
2473                     //: for (i = 0; c > 0; i++, c--)
2474                     //:     if (Str[i] != Rightcharnext())
2475                     //:         break Backward;
2476                     {
2477                         int i;
2478                         String str;
2479
2480                         str = _strings[Operand(0)];
2481
2482                         Ldc(str.Length);
2483                         Ldloc(_textendV);
2484                         Ldloc(_textposV);
2485                         Sub();
2486                         BgtFar(_backtrack);
2487
2488                         // unroll the string
2489                         for (i = 0; i < str.Length; i++) {
2490                             Ldloc(_textV);
2491                             Ldloc(_textposV);
2492                             if (i != 0) {
2493                                 Ldc(i);
2494                                 Add();
2495                             }
2496                             Callvirt(_getcharM);
2497                             if (IsCi())
2498                                 CallToLower();
2499
2500                             Ldc((int)str[i]);
2501                             BneFar(_backtrack);
2502                         }
2503
2504                         Ldloc(_textposV);
2505                         Ldc(str.Length);
2506                         Add();
2507                         Stloc(_textposV);
2508                         break;
2509                     }
2510
2511
2512                 case RegexCode.Multi | RegexCode.Rtl:
2513                 case RegexCode.Multi | RegexCode.Ci  | RegexCode.Rtl:
2514                     //: String Str = _strings[Operand(0)];
2515                     //: int c;
2516                     //: if (Leftchars() < (c = Str.Length))
2517                     //:     break Backward;
2518                     //: while (c > 0)
2519                     //:     if (Str[--c] != Leftcharnext())
2520                     //:         break Backward;
2521                     {
2522                         int i;
2523                         String str;
2524
2525                         str = _strings[Operand(0)];
2526
2527                         Ldc(str.Length);
2528                         Ldloc(_textposV);
2529                         Ldloc(_textbegV);
2530                         Sub();
2531                         BgtFar(_backtrack);
2532
2533                         // unroll the string
2534                         for (i = str.Length; i > 0;) {
2535                             i--;
2536                             Ldloc(_textV);
2537                             Ldloc(_textposV);
2538                             Ldc(str.Length - i);
2539                             Sub();
2540                             Callvirt(_getcharM);
2541                             if (IsCi())
2542                             {
2543                                 CallToLower();
2544                             }
2545                             Ldc((int)str[i]);
2546                             BneFar(_backtrack);
2547                         }
2548
2549                         Ldloc(_textposV);
2550                         Ldc(str.Length);
2551                         Sub();
2552                         Stloc(_textposV);
2553
2554                         break;
2555                     }
2556
2557                 case RegexCode.Ref:
2558                 case RegexCode.Ref | RegexCode.Rtl:
2559                 case RegexCode.Ref | RegexCode.Ci:
2560                 case RegexCode.Ref | RegexCode.Ci | RegexCode.Rtl:
2561                     //: int capnum = Operand(0);
2562                     //: int j, c;
2563                     //: if (!_match.IsMatched(capnum)) {
2564                     //:     if (!RegexOptions.ECMAScript)
2565                     //:         break Backward;
2566                     //: } else {
2567                     //:     if (Rightchars() < (c = _match.MatchLength(capnum)))
2568                     //:         break Backward;
2569                     //:     for (j = _match.MatchIndex(capnum); c > 0; j++, c--)
2570                     //:         if (CharAt(j) != Rightcharnext())
2571                     //:             break Backward;
2572                     //: }
2573                     {
2574                         LocalBuilder lenV     = _tempV;
2575                         LocalBuilder indexV   = _temp2V;
2576                         Label      l1       = DefineLabel();
2577
2578                         Ldthis();
2579                         Ldc(Operand(0));
2580                         Callvirt(_ismatchedM);
2581                         if ((_options & RegexOptions.ECMAScript) != 0)
2582                             Brfalse(AdvanceLabel());
2583                         else
2584                             BrfalseFar(_backtrack); // !IsMatched() -> back
2585
2586                         Ldthis();
2587                         Ldc(Operand(0));
2588                         Callvirt(_matchlengthM);
2589                         Dup();
2590                         Stloc(lenV);
2591                         if (!IsRtl()) {
2592                             Ldloc(_textendV);
2593                             Ldloc(_textposV);
2594                         }
2595                         else {
2596                             Ldloc(_textposV);
2597                             Ldloc(_textbegV);
2598                         }
2599                         Sub();
2600                         BgtFar(_backtrack);         // Matchlength() > Rightchars() -> back
2601
2602                         Ldthis();
2603                         Ldc(Operand(0));
2604                         Callvirt(_matchindexM);
2605                         if (!IsRtl()) {
2606                             Ldloc(lenV);
2607                             Add(IsRtl());
2608                         }
2609                         Stloc(indexV);              // index += len
2610
2611                         Ldloc(_textposV);
2612                         Ldloc(lenV);
2613                         Add(IsRtl());
2614                         Stloc(_textposV);           // texpos += len
2615
2616                         MarkLabel(l1);
2617                         Ldloc(lenV);
2618                         Ldc(0);
2619                         Ble(AdvanceLabel());
2620                         Ldloc(_textV);
2621                         Ldloc(indexV);
2622                         Ldloc(lenV);
2623                         if (IsRtl()) {
2624                             Ldc(1);
2625                             Sub();
2626                             Dup();
2627                             Stloc(lenV);
2628                         }
2629                         Sub(IsRtl());
2630                         Callvirt(_getcharM);
2631                         if (IsCi())
2632                             CallToLower();
2633
2634                         Ldloc(_textV);
2635                         Ldloc(_textposV);
2636                         Ldloc(lenV);
2637                         if (!IsRtl()) {
2638                             Dup();
2639                             Ldc(1);
2640                             Sub();
2641                             Stloc(lenV);
2642                         }
2643                         Sub(IsRtl());
2644                         Callvirt(_getcharM);
2645                         if (IsCi())
2646                             CallToLower();
2647
2648                         Beq(l1);
2649                         Back();
2650                         break;
2651                     }
2652
2653
2654                 case RegexCode.Onerep:
2655                 case RegexCode.Notonerep:
2656                 case RegexCode.Setrep:
2657                 case RegexCode.Onerep | RegexCode.Rtl:
2658                 case RegexCode.Notonerep | RegexCode.Rtl:
2659                 case RegexCode.Setrep | RegexCode.Rtl:
2660                 case RegexCode.Onerep | RegexCode.Ci:
2661                 case RegexCode.Notonerep | RegexCode.Ci:
2662                 case RegexCode.Setrep | RegexCode.Ci:
2663                 case RegexCode.Onerep | RegexCode.Ci | RegexCode.Rtl:
2664                 case RegexCode.Notonerep | RegexCode.Ci | RegexCode.Rtl:
2665                 case RegexCode.Setrep | RegexCode.Ci | RegexCode.Rtl:
2666                     //: int c = Operand(1);
2667                     //: if (Rightchars() < c)
2668                     //:     break Backward;
2669                     //: char ch = (char)Operand(0);
2670                     //: while (c-- > 0)
2671                     //:     if (Rightcharnext() != ch)
2672                     //:         break Backward;
2673                     {
2674                         LocalBuilder lenV = _tempV;
2675                         Label      l1   = DefineLabel();
2676
2677                         int c = Operand(1);
2678
2679                         if (c == 0)
2680                             break;
2681
2682                         Ldc(c);
2683                         if (!IsRtl()) {
2684                             Ldloc(_textendV);
2685                             Ldloc(_textposV);
2686                         }
2687                         else {
2688                             Ldloc(_textposV);
2689                             Ldloc(_textbegV);
2690                         }
2691                         Sub();
2692                         BgtFar(_backtrack);         // Matchlength() > Rightchars() -> back
2693
2694                         Ldloc(_textposV);
2695                         Ldc(c);
2696                         Add(IsRtl());
2697                         Stloc(_textposV);           // texpos += len
2698
2699                         Ldc(c);
2700                         Stloc(lenV);
2701
2702                         MarkLabel(l1);
2703                         Ldloc(_textV);
2704                         Ldloc(_textposV);
2705                         Ldloc(lenV);
2706                         if (IsRtl()) {
2707                             Ldc(1);
2708                             Sub();
2709                             Dup();
2710                             Stloc(lenV);
2711                             Add();
2712                         }
2713                         else {
2714                             Dup();
2715                             Ldc(1);
2716                             Sub();
2717                             Stloc(lenV);
2718                             Sub();
2719                         }
2720                         Callvirt(_getcharM);
2721                         if (IsCi())
2722                             CallToLower();
2723
2724                         if (Code() == RegexCode.Setrep) {
2725                             Ldstr(_strings[Operand(0)]);
2726                             Call(_charInSetM);
2727
2728                             BrfalseFar(_backtrack);
2729                         }
2730                         else {
2731                             Ldc(Operand(0));
2732                             if (Code() == RegexCode.Onerep)
2733                                 BneFar(_backtrack);
2734                             else
2735                                 BeqFar(_backtrack);
2736                         }
2737                         Ldloc(lenV);
2738                         Ldc(0);
2739                         if (Code() == RegexCode.Setrep)
2740                             BgtFar(l1);
2741                         else
2742                             Bgt(l1);
2743                         break;
2744                     }
2745
2746
2747                 case RegexCode.Oneloop:
2748                 case RegexCode.Notoneloop:
2749                 case RegexCode.Setloop:
2750                 case RegexCode.Oneloop | RegexCode.Rtl:
2751                 case RegexCode.Notoneloop | RegexCode.Rtl:
2752                 case RegexCode.Setloop | RegexCode.Rtl:
2753                 case RegexCode.Oneloop | RegexCode.Ci:
2754                 case RegexCode.Notoneloop | RegexCode.Ci:
2755                 case RegexCode.Setloop | RegexCode.Ci:
2756                 case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Rtl:
2757                 case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Rtl:
2758                 case RegexCode.Setloop | RegexCode.Ci | RegexCode.Rtl:
2759                     //: int c = Operand(1);
2760                     //: if (c > Rightchars())
2761                     //:     c = Rightchars();
2762                     //: char ch = (char)Operand(0);
2763                     //: int i;
2764                     //: for (i = c; i > 0; i--)
2765                     //: {
2766                     //:     if (Rightcharnext() != ch)
2767                     //:     {
2768                     //:         Leftnext();
2769                     //:         break;
2770                     //:     }
2771                     //: }
2772                     //: if (c > i)
2773                     //:     Track(c - i - 1, Textpos() - 1);
2774
2775                     {
2776                         LocalBuilder cV   = _tempV;
2777                         LocalBuilder lenV = _temp2V;
2778                         Label      l1   = DefineLabel();
2779                         Label      l2   = DefineLabel();
2780
2781                         int c = Operand(1);
2782
2783                         if (c == 0)
2784                             break;
2785                         if (!IsRtl()) {
2786                             Ldloc(_textendV);
2787                             Ldloc(_textposV);
2788                         }
2789                         else {
2790                             Ldloc(_textposV);
2791                             Ldloc(_textbegV);
2792                         }
2793                         Sub();
2794                         if (c != Int32.MaxValue) {
2795                             Label l4 = DefineLabel();
2796                             Dup();
2797                             Ldc(c);
2798                             Blt(l4);
2799                             Pop();
2800                             Ldc(c);
2801                             MarkLabel(l4);
2802                         }
2803                         Dup();
2804                         Stloc(lenV);
2805                         Ldc(1);
2806                         Add();
2807                         Stloc(cV);
2808
2809                         MarkLabel(l1);
2810                         Ldloc(cV);
2811                         Ldc(1);
2812                         Sub();
2813                         Dup();
2814                         Stloc(cV);
2815                         Ldc(0);
2816                         if (Code() == RegexCode.Setloop)
2817                             BleFar(l2);
2818                         else
2819                             Ble(l2);
2820
2821                         if (IsRtl())
2822                             Leftcharnext();
2823                         else
2824                             Rightcharnext();
2825                         if (IsCi())
2826                             CallToLower();
2827
2828                         if (Code() == RegexCode.Setloop) {
2829                             Ldstr(_strings[Operand(0)]);
2830                             Call(_charInSetM);
2831
2832                             BrtrueFar(l1);
2833                         }
2834                         else {
2835                             Ldc(Operand(0));
2836                             if (Code() == RegexCode.Oneloop)
2837                                 Beq(l1);
2838                             else
2839                                 Bne(l1);
2840                         }
2841
2842                         Ldloc(_textposV);
2843                         Ldc(1);
2844                         Sub(IsRtl());
2845                         Stloc(_textposV);
2846
2847                         MarkLabel(l2);
2848                         Ldloc(lenV);
2849                         Ldloc(cV);
2850                         Ble(AdvanceLabel());
2851
2852                         ReadyPushTrack();
2853                         Ldloc(lenV);
2854                         Ldloc(cV);
2855                         Sub();
2856                         Ldc(1);
2857                         Sub();
2858                         DoPush();
2859
2860                         ReadyPushTrack();
2861                         Ldloc(_textposV);
2862                         Ldc(1);
2863                         Sub(IsRtl());
2864                         DoPush();
2865
2866                         Track();
2867                         break;
2868                     }
2869
2870                 case RegexCode.Oneloop | RegexCode.Back:
2871                 case RegexCode.Notoneloop | RegexCode.Back:
2872                 case RegexCode.Setloop | RegexCode.Back:
2873                 case RegexCode.Oneloop | RegexCode.Rtl | RegexCode.Back:
2874                 case RegexCode.Notoneloop | RegexCode.Rtl | RegexCode.Back:
2875                 case RegexCode.Setloop | RegexCode.Rtl | RegexCode.Back:
2876                 case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Back:
2877                 case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Back:
2878                 case RegexCode.Setloop | RegexCode.Ci | RegexCode.Back:
2879                 case RegexCode.Oneloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2880                 case RegexCode.Notoneloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2881                 case RegexCode.Setloop | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2882                     //: Trackframe(2);
2883                     //: int i   = Tracked(0);
2884                     //: int pos = Tracked(1);
2885                     //: Textto(pos);
2886                     //: if (i > 0)
2887                     //:     Track(i - 1, pos - 1);
2888                     //: Advance(2);
2889                     PopTrack();
2890                     Stloc(_textposV);
2891                     PopTrack();
2892                     Stloc(_tempV);
2893                     Ldloc(_tempV);
2894                     Ldc(0);
2895                     BleFar(AdvanceLabel());
2896                     ReadyPushTrack();
2897                     Ldloc(_tempV);
2898                     Ldc(1);
2899                     Sub();
2900                     DoPush();
2901                     ReadyPushTrack();
2902                     Ldloc(_textposV);
2903                     Ldc(1);
2904                     Sub(IsRtl());
2905                     DoPush();
2906                     Trackagain();
2907                     Advance();
2908                     break;
2909
2910                 case RegexCode.Onelazy:
2911                 case RegexCode.Notonelazy:
2912                 case RegexCode.Setlazy:
2913                 case RegexCode.Onelazy | RegexCode.Rtl:
2914                 case RegexCode.Notonelazy | RegexCode.Rtl:
2915                 case RegexCode.Setlazy | RegexCode.Rtl:
2916                 case RegexCode.Onelazy | RegexCode.Ci:
2917                 case RegexCode.Notonelazy | RegexCode.Ci:
2918                 case RegexCode.Setlazy | RegexCode.Ci:
2919                 case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Rtl:
2920                 case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Rtl:
2921                 case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Rtl:
2922                     //: int c = Operand(1);
2923                     //: if (c > Rightchars())
2924                     //:     c = Rightchars();
2925                     //: if (c > 0)
2926                     //:     Track(c - 1, Textpos());
2927                     {
2928                         LocalBuilder cV   = _tempV;
2929
2930                         int c = Operand(1);
2931
2932                         if (c == 0)
2933                             break;
2934
2935                         if (!IsRtl()) {
2936                             Ldloc(_textendV);
2937                             Ldloc(_textposV);
2938                         }
2939                         else {
2940                             Ldloc(_textposV);
2941                             Ldloc(_textbegV);
2942                         }
2943                         Sub();
2944                         if (c != Int32.MaxValue) {
2945                             Label l4 = DefineLabel();
2946                             Dup();
2947                             Ldc(c);
2948                             Blt(l4);
2949                             Pop();
2950                             Ldc(c);
2951                             MarkLabel(l4);
2952                         }
2953                         Dup();
2954                         Stloc(cV);
2955                         Ldc(0);
2956                         Ble(AdvanceLabel());
2957                         ReadyPushTrack();
2958                         Ldloc(cV);
2959                         Ldc(1);
2960                         Sub();
2961                         DoPush();
2962                         PushTrack(_textposV);
2963                         Track();
2964                         break;
2965                     }
2966
2967                 case RegexCode.Onelazy | RegexCode.Back:
2968                 case RegexCode.Notonelazy | RegexCode.Back:
2969                 case RegexCode.Setlazy | RegexCode.Back:
2970                 case RegexCode.Onelazy | RegexCode.Rtl | RegexCode.Back:
2971                 case RegexCode.Notonelazy | RegexCode.Rtl | RegexCode.Back:
2972                 case RegexCode.Setlazy | RegexCode.Rtl | RegexCode.Back:
2973                 case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Back:
2974                 case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Back:
2975                 case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Back:
2976                 case RegexCode.Onelazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2977                 case RegexCode.Notonelazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2978                 case RegexCode.Setlazy | RegexCode.Ci | RegexCode.Rtl | RegexCode.Back:
2979                     //: Trackframe(2);
2980                     //: int pos = Tracked(1);
2981                     //: Textto(pos);
2982                     //: if (Rightcharnext() != (char)Operand(0))
2983                     //:     break Backward;
2984                     //: int i = Tracked(0);
2985                     //: if (i > 0)
2986                     //:     Track(i - 1, pos + 1);
2987
2988                     PopTrack();
2989                     Stloc(_textposV);
2990                     PopTrack();
2991                     Stloc(_temp2V);
2992
2993                     if (!IsRtl())
2994                         Rightcharnext();
2995                     else
2996                         Leftcharnext();
2997
2998                     if (IsCi())
2999                         CallToLower();
3000
3001                     if (Code() == RegexCode.Setlazy) {
3002                         Ldstr(_strings[Operand(0)]);
3003                         Call(_charInSetM);
3004
3005                         BrfalseFar(_backtrack);
3006                     }
3007                     else {
3008                         Ldc(Operand(0));
3009                         if (Code() == RegexCode.Onelazy)
3010                             BneFar(_backtrack);
3011                         else
3012                             BeqFar(_backtrack);
3013                     }
3014
3015                     Ldloc(_temp2V);
3016                     Ldc(0);
3017                     BleFar(AdvanceLabel());
3018                     ReadyPushTrack();
3019                     Ldloc(_temp2V);
3020                     Ldc(1);
3021                     Sub();
3022                     DoPush();
3023                     PushTrack(_textposV);
3024                     Trackagain();
3025                     Advance();
3026                     break;
3027
3028                 default:
3029                     throw new NotImplementedException(SR.GetString(SR.UnimplementedState));
3030             }
3031         }
3032     }
3033
3034     internal class RegexTypeCompiler : RegexCompiler {
3035         private static int _typeCount = 0;
3036         private static LocalDataStoreSlot _moduleSlot = Thread.AllocateDataSlot();
3037
3038         private  AssemblyBuilder _assembly;
3039         private  ModuleBuilder  _module;
3040
3041         // state of the type builder
3042         private  TypeBuilder     _typebuilder;
3043         private  MethodBuilder   _methbuilder;
3044
3045         [ResourceExposure(ResourceScope.Machine)]
3046         [ResourceConsumption(ResourceScope.Machine)]
3047         [SuppressMessage("Microsoft.Security","CA2106:SecureAsserts", Justification="[....]: SECREVIEW : Regex only generates string manipulation, so this is OK")]
3048         internal RegexTypeCompiler(AssemblyName an, CustomAttributeBuilder[] attribs, String resourceFile) {
3049             // SECREVIEW : Regex only generates string manipulation, so this is
3050             //           : ok.
3051             //
3052 #if !DISABLE_CAS_USE
3053             new ReflectionPermission(PermissionState.Unrestricted).Assert();
3054 #endif
3055             try {
3056                 Debug.Assert(an != null, "AssemblyName should not be null");
3057
3058                 List<CustomAttributeBuilder> assemblyAttributes = new List<CustomAttributeBuilder>();
3059
3060                 ConstructorInfo transparencyCtor = typeof(SecurityTransparentAttribute).GetConstructor(Type.EmptyTypes);
3061                 CustomAttributeBuilder transparencyAttribute = new CustomAttributeBuilder(transparencyCtor, new object[0]);
3062                 assemblyAttributes.Add(transparencyAttribute);
3063
3064 #if !DISABLE_CAS_USE
3065                 ConstructorInfo securityRulesCtor = typeof(SecurityRulesAttribute).GetConstructor(new Type[] { typeof(SecurityRuleSet) });
3066                 CustomAttributeBuilder securityRulesAttribute =
3067                     new CustomAttributeBuilder(securityRulesCtor, new object[] { SecurityRuleSet.Level2 });
3068                 assemblyAttributes.Add(securityRulesAttribute);
3069 #endif
3070
3071                 _assembly = AppDomain.CurrentDomain.DefineDynamicAssembly(an, AssemblyBuilderAccess.RunAndSave, assemblyAttributes);
3072                 _module = _assembly.DefineDynamicModule(an.Name + ".dll");
3073
3074                 if (attribs != null) {
3075                     for (int i=0; i<attribs.Length; i++) {
3076                         _assembly.SetCustomAttribute(attribs[i]);
3077                     }
3078                 }
3079
3080                 if (resourceFile != null) {
3081 #if FEATURE_PAL
3082                     // unmanaged resources are not supported
3083                     throw new ArgumentOutOfRangeException("resourceFile");
3084 #else
3085                     _assembly.DefineUnmanagedResource(resourceFile);
3086 #endif
3087                 }
3088             }
3089             finally {
3090 #if !DISABLE_CAS_USE
3091                 CodeAccessPermission.RevertAssert();
3092 #endif
3093             }
3094         }
3095
3096         /*
3097          * The top-level driver. Initializes everything then calls the Generate* methods.
3098          */
3099         internal Type FactoryTypeFromCode(RegexCode code, RegexOptions options, String typeprefix) {
3100             String runnertypename;
3101             String runnerfactoryname;
3102             Type runnertype;
3103             Type factory;
3104
3105             _code       = code;
3106             _codes      = code._codes;
3107             _strings    = code._strings;
3108             _fcPrefix   = code._fcPrefix;
3109             _bmPrefix   = code._bmPrefix;
3110             _anchors    = code._anchors;
3111             _trackcount = code._trackcount;
3112             _options    = options;
3113
3114             // pick a name for the class
3115             int typenum = Interlocked.Increment(ref _typeCount);
3116             string typenumString = typenum.ToString(CultureInfo.InvariantCulture);
3117             runnertypename = typeprefix + "Runner" + typenumString ;
3118             runnerfactoryname = typeprefix + "Factory" + typenumString;
3119
3120             // Generate a RegexRunner class
3121             // (blocks are simply illustrative)
3122
3123             DefineType(runnertypename, false, typeof(RegexRunner));
3124             {
3125                 DefineMethod("Go", null);
3126                 {
3127                     GenerateGo();
3128                     BakeMethod();
3129                 }
3130
3131                 DefineMethod("FindFirstChar", typeof(bool));
3132                 {
3133                     GenerateFindFirstChar();
3134                     BakeMethod();
3135                 }
3136
3137                 DefineMethod("InitTrackCount", null);
3138                 {
3139                     GenerateInitTrackCount();
3140                     BakeMethod();
3141                 }
3142
3143                 runnertype = BakeType();
3144             }
3145
3146             // Generate a RegexRunnerFactory class
3147
3148             DefineType(runnerfactoryname, false, typeof(RegexRunnerFactory));
3149             {
3150                 DefineMethod("CreateInstance", typeof(RegexRunner));
3151                 {
3152                     GenerateCreateInstance(runnertype);
3153                     BakeMethod();
3154                 }
3155
3156                 factory = BakeType();
3157             }
3158
3159             return factory;
3160         }
3161
3162         internal void GenerateRegexType(String pattern, RegexOptions opts, String name, bool ispublic, RegexCode code, RegexTree tree, Type factory, TimeSpan matchTimeout) {
3163             FieldInfo patternF                = RegexField("pattern");
3164             FieldInfo optionsF                = RegexField("roptions");
3165             FieldInfo factoryF                = RegexField("factory");
3166             FieldInfo capsF                   = RegexField("caps");
3167             FieldInfo capnamesF               = RegexField("capnames");
3168             FieldInfo capslistF               = RegexField("capslist");
3169             FieldInfo capsizeF                = RegexField("capsize");
3170             FieldInfo internalMatchTimeoutF   = RegexField("internalMatchTimeout");
3171             Type[] noTypeArray                = new Type[0];
3172             ConstructorBuilder defCtorBuilder, tmoutCtorBuilder;
3173
3174             DefineType(name, ispublic, typeof(Regex));
3175             {
3176                 // Define default constructor:
3177                 _methbuilder = null;
3178                 MethodAttributes ma = System.Reflection.MethodAttributes.Public;
3179                 defCtorBuilder = _typebuilder.DefineConstructor(ma, CallingConventions.Standard, noTypeArray);
3180                 _ilg = defCtorBuilder.GetILGenerator();
3181                 {
3182                     // call base constructor
3183                     Ldthis();
3184                     _ilg.Emit(OpCodes.Call, typeof(Regex).GetConstructor(BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance,
3185                                                                          null, new Type[0], new ParameterModifier[0]));
3186                     // set pattern
3187                     Ldthis();
3188                     Ldstr(pattern);
3189                     Stfld(patternF);
3190
3191                     // set options
3192                     Ldthis();
3193                     Ldc((int) opts);
3194                     Stfld(optionsF);
3195
3196                     // Set timeout (no need to validate as it should have happened in RegexCompilationInfo):
3197                     Ldthis();
3198                     LdcI8(matchTimeout.Ticks);
3199                     Call(typeof(TimeSpan).GetMethod("FromTicks", BindingFlags.Static | BindingFlags.Public));
3200                     Stfld(internalMatchTimeoutF);
3201
3202                     // set factory
3203                     Ldthis();
3204                     Newobj(factory.GetConstructor(noTypeArray));
3205                     Stfld(factoryF);
3206
3207                     // set caps
3208                     if (code._caps != null)
3209 #if SILVERLIGHT
3210                         GenerateCreateType(typeof(Dictionary<Int32, Int32>), capsF, code._caps);
3211 #else
3212                         GenerateCreateHashtable(capsF, code._caps);
3213 #endif
3214
3215                     // set capnames
3216                     if (tree._capnames != null)
3217 #if SILVERLIGHT
3218                         GenerateCreateType(typeof(Dictionary<String, Int32>), capnamesF, tree._capnames);
3219 #else
3220                         GenerateCreateHashtable(capnamesF, tree._capnames);
3221 #endif
3222
3223
3224                     // set capslist
3225                     if (tree._capslist != null) {
3226                         Ldthis();
3227                         Ldc(tree._capslist.Length);
3228                         _ilg.Emit(OpCodes.Newarr, typeof(String));  // create new string array
3229                         Stfld(capslistF);
3230
3231                         for (int i=0; i< tree._capslist.Length; i++) {
3232                             Ldthisfld(capslistF);
3233
3234                             Ldc(i);
3235                             Ldstr(tree._capslist[i]);
3236                             _ilg.Emit(OpCodes.Stelem_Ref);
3237                         }
3238                     }
3239
3240                     // set capsize
3241                     Ldthis();
3242                     Ldc(code._capsize);
3243                     Stfld(capsizeF);
3244
3245                     // set runnerref and replref by calling InitializeReferences()
3246                     Ldthis();
3247                     Call(typeof(Regex).GetMethod("InitializeReferences", BindingFlags.Instance | BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic));
3248
3249
3250                     Ret();
3251                 }
3252
3253                 // Constructor with the timeout parameter:
3254                 _methbuilder = null;
3255                 ma = System.Reflection.MethodAttributes.Public;
3256                 tmoutCtorBuilder = _typebuilder.DefineConstructor(ma, CallingConventions.Standard, new Type[] { typeof(TimeSpan) });
3257                 _ilg = tmoutCtorBuilder.GetILGenerator();
3258                 {
3259                     // Call the default constructor:
3260                     Ldthis();
3261                     _ilg.Emit(OpCodes.Call, defCtorBuilder);
3262
3263                     // Validate timeout:
3264                     _ilg.Emit(OpCodes.Ldarg_1);
3265                     Call(typeof(Regex).GetMethod("ValidateMatchTimeout", BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic));
3266
3267                     // Set timeout:
3268                     Ldthis();
3269                     _ilg.Emit(OpCodes.Ldarg_1);
3270                     Stfld(internalMatchTimeoutF);
3271
3272                     Ret();
3273                 }
3274             }
3275
3276             // bake the constructor and type, then save the assembly
3277             defCtorBuilder = null;
3278             tmoutCtorBuilder = null;
3279             _typebuilder.CreateType();
3280             _ilg = null;
3281             _typebuilder = null;
3282         }
3283
3284 #if SILVERLIGHT
3285         internal void GenerateCreateType<TKey>(Type myCollectionType, FieldInfo field, Dictionary<TKey,int> ht) {
3286             MethodInfo addMethod = myCollectionType.GetMethod("Add", BindingFlags.Instance | BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic);
3287
3288             Ldthis();
3289             Newobj(myCollectionType.GetConstructor(new Type[0]));
3290 #else
3291         internal void GenerateCreateHashtable(FieldInfo field, Hashtable ht) {
3292             MethodInfo addMethod = typeof(Hashtable).GetMethod("Add", BindingFlags.Instance | BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic);
3293
3294             Ldthis();
3295             Newobj(typeof(Hashtable).GetConstructor(new Type[0]));
3296 #endif
3297
3298             Stfld(field);
3299
3300             IDictionaryEnumerator en = ht.GetEnumerator();
3301             while (en.MoveNext()) {
3302                 Ldthisfld(field);
3303
3304                 if (en.Key is int) {
3305                     Ldc((int) en.Key);
3306 #if !SILVERLIGHT
3307                     _ilg.Emit(OpCodes.Box, typeof(Int32));
3308 #endif
3309                 }
3310                 else
3311                     Ldstr((String) en.Key);
3312
3313                 Ldc((int) en.Value);
3314 #if !SILVERLIGHT
3315                 _ilg.Emit(OpCodes.Box, typeof(Int32));
3316 #endif
3317                 Callvirt(addMethod);
3318             }
3319         }
3320
3321         private FieldInfo RegexField(String fieldname) {
3322             return typeof(Regex).GetField(fieldname, BindingFlags.Instance | BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic);
3323         }
3324
3325         // Note that we save the assembly to the current directory, and we believe this is not a
3326         // problem because this should only be used by tools, not at runtime.
3327         [ResourceExposure(ResourceScope.None)]
3328         [ResourceConsumption(ResourceScope.Machine, ResourceScope.Machine)]
3329         internal void Save() {
3330             _assembly.Save(_assembly.GetName().Name + ".dll");
3331         }
3332
3333         /*
3334          * Generates a very simple factory method.
3335          */
3336         internal void GenerateCreateInstance(Type newtype) {
3337             Newobj(newtype.GetConstructor(new Type[0]));
3338             Ret();
3339         }
3340
3341         /*
3342          * Begins the definition of a new type with a specified base class
3343          */
3344         internal void DefineType(String typename, bool ispublic, Type inheritfromclass) {
3345             if (ispublic)
3346                 _typebuilder = _module.DefineType(typename, TypeAttributes.Class | TypeAttributes.Public, inheritfromclass);
3347             else
3348                 _typebuilder = _module.DefineType(typename, TypeAttributes.Class | TypeAttributes.NotPublic, inheritfromclass);
3349
3350         }
3351
3352         /*
3353          * Begins the definition of a new method (no args) with a specified return value
3354          */
3355         internal void DefineMethod(String methname, Type returntype) {
3356             MethodAttributes ma = System.Reflection.MethodAttributes.Public | System.Reflection.MethodAttributes.Virtual;
3357
3358             _methbuilder = _typebuilder.DefineMethod(methname, ma, returntype, null);
3359             _ilg = _methbuilder.GetILGenerator();
3360         }
3361
3362         /*
3363          * Ends the definition of a method
3364          */
3365         internal void BakeMethod() {
3366             _methbuilder = null;
3367         }
3368
3369         /*
3370          * Ends the definition of a class and returns the type
3371          */
3372         internal Type BakeType() {
3373             Type retval = _typebuilder.CreateType();
3374             _typebuilder = null;
3375
3376             return retval;
3377         }
3378
3379     }
3380
3381     internal class RegexLWCGCompiler : RegexCompiler {
3382         private static int _regexCount = 0;
3383         private static Type[] _paramTypes = new Type[] {typeof(RegexRunner)};
3384
3385         internal RegexLWCGCompiler() {
3386         }
3387
3388         /*
3389          * The top-level driver. Initializes everything then calls the Generate* methods.
3390          */
3391         internal RegexRunnerFactory FactoryInstanceFromCode(RegexCode code, RegexOptions options) {
3392             _code       = code;
3393             _codes      = code._codes;
3394             _strings    = code._strings;
3395             _fcPrefix   = code._fcPrefix;
3396             _bmPrefix   = code._bmPrefix;
3397             _anchors    = code._anchors;
3398             _trackcount = code._trackcount;
3399             _options    = options;
3400
3401             // pick a unique number for the methods we generate
3402             int regexnum = Interlocked.Increment(ref _regexCount);
3403             string regexnumString = regexnum.ToString(CultureInfo.InvariantCulture);
3404
3405             DynamicMethod goMethod = DefineDynamicMethod("Go" + regexnumString, null, typeof(CompiledRegexRunner));
3406             GenerateGo();
3407
3408             DynamicMethod firstCharMethod = DefineDynamicMethod("FindFirstChar" + regexnumString, typeof(bool), typeof(CompiledRegexRunner));
3409             GenerateFindFirstChar();
3410
3411             DynamicMethod trackCountMethod = DefineDynamicMethod("InitTrackCount" + regexnumString, null, typeof(CompiledRegexRunner));
3412             GenerateInitTrackCount();
3413
3414             return new CompiledRegexRunnerFactory(goMethod, firstCharMethod, trackCountMethod);
3415         }
3416
3417         /*
3418          * Begins the definition of a new method (no args) with a specified return value
3419          */
3420         internal DynamicMethod DefineDynamicMethod(String methname, Type returntype, Type hostType) {
3421             // We're claiming that these are static methods, but really they are instance methods.
3422             // By giving them a parameter which represents "this", we're tricking them into
3423             // being instance methods.
3424
3425             MethodAttributes attribs =  MethodAttributes.Public | MethodAttributes.Static;
3426             CallingConventions conventions = CallingConventions.Standard;
3427
3428             DynamicMethod dm = new DynamicMethod(methname, attribs, conventions, returntype, _paramTypes, hostType, false /*skipVisibility*/);
3429             _ilg = dm.GetILGenerator();
3430             return dm;
3431         }
3432
3433     }
3434
3435 }
3436 #endif