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

   1 //
   2 // assembly:    System
   3 // namespace:   System.Text.RegularExpressions
   4 // file:        compiler.cs
   5 //
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)
   7 //              (c) 2002
   8
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining
  11 // a copy of this software and associated documentation files (the
  12 // "Software"), to deal in the Software without restriction, including
  13 // without limitation the rights to use, copy, modify, merge, publish,
  14 // distribute, sublicense, and/or sell copies of the Software, and to
  15 // permit persons to whom the Software is furnished to do so, subject to
  16 // the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 //
  29
  30 using System;
  31 using System.Collections;
  32
  33 namespace System.Text.RegularExpressions {
  34         abstract class LinkRef {
  35                 // empty
  36         }
  37
  38         interface ICompiler {
  39                 void Reset ();
  40                 IMachineFactory GetMachineFactory ();
  41
  42                 // instruction emission
  43
  44                 void EmitFalse ();
  45                 void EmitTrue ();
  46
  47                 // character matching
  48
  49                 void EmitCharacter (char c, bool negate, bool ignore, bool reverse);
  50                 void EmitCategory (Category cat, bool negate, bool reverse);
  51                 void EmitNotCategory (Category cat, bool negate, bool reverse);
  52                 void EmitRange (char lo, char hi, bool negate, bool ignore, bool reverse);
  53                 void EmitSet (char lo, BitArray set, bool negate, bool ignore, bool reverse);
  54
  55                 // other operators
  56
  57                 void EmitString (string str, bool ignore, bool reverse);
  58                 void EmitPosition (Position pos);
  59                 void EmitOpen (int gid);
  60                 void EmitClose (int gid);
  61                 void EmitBalanceStart(int gid, int balance, bool capture,  LinkRef tail);
  62                 void EmitBalance ();
  63                 void EmitReference (int gid, bool ignore, bool reverse);
  64
  65                 // constructs
  66
  67                 void EmitIfDefined (int gid, LinkRef tail);
  68                 void EmitSub (LinkRef tail);
  69                 void EmitTest (LinkRef yes, LinkRef tail);
  70                 void EmitBranch (LinkRef next);
  71                 void EmitJump (LinkRef target);
  72                 void EmitRepeat (int min, int max, bool lazy, LinkRef until);
  73                 void EmitUntil (LinkRef repeat);
  74                 void EmitIn (LinkRef tail);
  75                 void EmitInfo (int count, int min, int max);
  76                 void EmitFastRepeat (int min, int max, bool lazy, LinkRef tail);
  77                 void EmitAnchor (bool reverse, int offset, LinkRef tail);
  78
  79                 // event for the CILCompiler
  80                 void EmitBranchEnd();
  81                 void EmitAlternationEnd();
  82
  83                 LinkRef NewLink ();
  84                 void ResolveLink (LinkRef link);
  85         }
  86
  87         class InterpreterFactory : IMachineFactory {
  88                 public InterpreterFactory (ushort[] pattern) {
  89                         this.pattern = pattern;
  90                 }
  91
  92                 public IMachine NewInstance () {
  93                         return new Interpreter (pattern);
  94                 }
  95
  96                 public int GroupCount {
  97                         get { return pattern[1]; }
  98                 }
  99
 100                 public int Gap {
 101                         get { return gap; }
 102                         set { gap = value; }
 103                 }
 104
 105                 public IDictionary Mapping {
 106                         get { return mapping; }
 107                         set { mapping = value; }
 108                 }
 109
 110                 public string [] NamesMapping {
 111                         get { return namesMapping; }
 112                         set { namesMapping = value; }
 113                 }
 114
 115                 private IDictionary mapping;
 116                 private ushort[] pattern;
 117                 private string [] namesMapping;
 118                 private int gap;
 119         }
 120
 121         class PatternCompiler : ICompiler {
 122                 public static ushort EncodeOp (OpCode op, OpFlags flags) {
 123                         return (ushort)((int)op | ((int)flags & 0xff00));
 124                 }
 125
 126                 internal static readonly bool trace_regex =
 127 #if !NET_2_1
 128                         Environment.GetEnvironmentVariable ("MONO_TRACE_REGEX") != null;
 129 #else
 130                         false;
 131 #endif
 132                 public static void DecodeOp (ushort word, out OpCode op, out OpFlags flags) {
 133                         op = (OpCode)(word & 0x00ff);
 134                         flags = (OpFlags)(word & 0xff00);
 135                 }
 136
 137                 public PatternCompiler () {
 138                         pgm = new ArrayList ();
 139                 }
 140
 141                 // ICompiler implementation
 142
 143                 public void Reset () {
 144                         pgm.Clear ();
 145                 }
 146
 147                 public IMachineFactory GetMachineFactory () {
 148                         ushort[] image = new ushort[pgm.Count];
 149                         pgm.CopyTo (image);
 150
 151                         return new InterpreterFactory (image);
 152                 }
 153
 154                 public void EmitFalse () {
 155                         Emit (OpCode.False);
 156                         if (trace_regex)
 157                                 Console.WriteLine ("false");
 158                 }
 159
 160                 public void EmitTrue () {
 161                         Emit (OpCode.True);
 162                         if (trace_regex)
 163                                 Console.WriteLine ("true");
 164                 }
 165
 166                 void EmitCount (int count)
 167                 {
 168                         uint ucount = (uint) count;
 169                         Emit ((ushort) (ucount & 0xFFFF)); // lo 16bits
 170                         Emit ((ushort) (ucount >> 16));    // hi
 171                         if (trace_regex)
 172                                 Console.WriteLine ("count {0}", count);
 173                 }
 174
 175                 public void EmitCharacter (char c, bool negate, bool ignore, bool reverse) {
 176                         Emit (OpCode.Character, MakeFlags (negate, ignore, reverse, false));
 177
 178                         if (ignore)
 179                                 c = Char.ToLower (c);
 180
 181                         Emit ((ushort)c);
 182
 183                         if (trace_regex)
 184                                 Console.WriteLine ("character {0} negate {1} ignore {2} reverse {3}", c, negate, ignore, reverse);
 185                 }
 186
 187                 public void EmitCategory (Category cat, bool negate, bool reverse) {
 188                         Emit (OpCode.Category, MakeFlags (negate, false, reverse, false));
 189                         Emit ((ushort)cat);
 190
 191                         if (trace_regex)
 192                                 Console.WriteLine ("category {0} negate {1} reverse {2}", cat, negate, reverse);
 193                 }
 194
 195                 public void EmitNotCategory (Category cat, bool negate, bool reverse) {
 196                         Emit (OpCode.NotCategory, MakeFlags (negate, false, reverse, false));
 197                         Emit ((ushort)cat);
 198
 199                         if (trace_regex)
 200                                 Console.WriteLine ("not category {0} negate {1} reverse {2}", cat, negate, reverse);
 201                 }
 202
 203                 public void EmitRange (char lo, char hi, bool negate, bool ignore, bool reverse) {
 204                         Emit (OpCode.Range, MakeFlags (negate, ignore, reverse, false));
 205                         Emit ((ushort)lo);
 206                         Emit ((ushort)hi);
 207
 208                         if (trace_regex)
 209                                 Console.WriteLine ("char range '{0}' - '{1}' negate {2} ignore {3} reverse {4}", lo, hi, negate, ignore, reverse);
 210                 }
 211
 212                 public void EmitSet (char lo, BitArray set, bool negate, bool ignore, bool reverse) {
 213                         Emit (OpCode.Set, MakeFlags (negate, ignore, reverse, false));
 214                         Emit ((ushort)lo);
 215
 216                         int len = (set.Length + 0xf) >> 4;
 217                         Emit ((ushort)len);
 218
 219                         int b = 0;
 220                         while (len -- != 0) {
 221                                 ushort word = 0;
 222                                 for (int i = 0; i < 16; ++ i) {
 223                                         if (b >= set.Length)
 224                                                 break;
 225
 226                                         if (set[b ++])
 227                                                 word |= (ushort)(1 << i);
 228                                 }
 229
 230                                 Emit (word);
 231                         }
 232
 233                         if (trace_regex)
 234                                 Console.WriteLine ("set lo '{0}' - '{1}' negate {2} ignore {3} reverse {4}", lo, set, negate, ignore, reverse);
 235                 }
 236
 237                 public void EmitString (string str, bool ignore, bool reverse) {
 238                         Emit (OpCode.String, MakeFlags (false, ignore, reverse, false));
 239                         int len = str.Length;
 240                         Emit ((ushort)len);
 241
 242                         if (ignore)
 243                                 str = str.ToLower ();
 244
 245                         for (int i = 0; i < len; ++ i)
 246                                 Emit ((ushort)str[i]);
 247                         if (trace_regex)
 248                                 Console.WriteLine ("string '{0}' ignore {1} reverse {2}", str, ignore, reverse);
 249                 }
 250
 251                 public void EmitPosition (Position pos) {
 252                         Emit (OpCode.Position, 0);
 253                         Emit ((ushort)pos);
 254
 255                         if (trace_regex)
 256                                 Console.WriteLine ("position {0}", pos);
 257                 }
 258
 259                 public void EmitOpen (int gid) {
 260                         Emit (OpCode.Open);
 261                         Emit ((ushort)gid);
 262
 263                         if (trace_regex)
 264                                 Console.WriteLine ("open {0}", gid);
 265                 }
 266
 267                 public void EmitClose (int gid) {
 268                         Emit (OpCode.Close);
 269                         Emit ((ushort)gid);
 270
 271                         if (trace_regex)
 272                                 Console.WriteLine ("close {0}", gid);
 273                 }
 274
 275
 276
 277                 public void EmitBalanceStart (int gid, int balance, bool capture, LinkRef tail) {
 278                         BeginLink (tail);
 279                         Emit (OpCode.BalanceStart);
 280                         Emit ((ushort)gid);
 281                         Emit ((ushort)balance);
 282                         Emit ((ushort)(capture ? 1 : 0));
 283                         EmitLink (tail);
 284
 285                         if (trace_regex)
 286                                 Console.WriteLine ("balance start gid {0} balance {1} capture {2} tail {3}", gid, balance, capture, tail);
 287                 }
 288
 289                 public void EmitBalance () {
 290                         Emit (OpCode.Balance);
 291
 292                         if (trace_regex)
 293                                 Console.WriteLine ("balance");
 294                 }
 295
 296                 public void EmitReference (int gid, bool ignore, bool reverse) {
 297                         Emit (OpCode.Reference, MakeFlags (false, ignore, reverse, false));
 298                         Emit ((ushort)gid);
 299
 300                         if (trace_regex)
 301                                 Console.WriteLine ("reference gid {0} ignore {1} reverse {2}", gid, ignore, reverse);
 302                 }
 303
 304                 public void EmitIfDefined (int gid, LinkRef tail) {
 305                         BeginLink (tail);
 306                         Emit (OpCode.IfDefined);
 307                         EmitLink (tail);
 308                         Emit ((ushort)gid);
 309
 310                         if (trace_regex)
 311                                 Console.WriteLine ("if defined gid {1} tail {2}", gid, tail);
 312                 }
 313
 314                 public void EmitSub (LinkRef tail) {
 315                         BeginLink (tail);
 316                         Emit (OpCode.Sub);
 317                         EmitLink (tail);
 318
 319                         if (trace_regex)
 320                                 Console.WriteLine ("sub {0}", tail);
 321                 }
 322
 323                 public void EmitTest (LinkRef yes, LinkRef tail) {
 324                         BeginLink (yes);
 325                         BeginLink (tail);
 326                         Emit (OpCode.Test);
 327                         EmitLink (yes);
 328                         EmitLink (tail);
 329
 330                         if (trace_regex)
 331                                 Console.WriteLine ("test yes {0} tail {1}", yes, tail);
 332                 }
 333
 334                 public void EmitBranch (LinkRef next) {
 335                         BeginLink (next);
 336                         Emit (OpCode.Branch, 0);
 337                         EmitLink (next);
 338
 339                         if (trace_regex)
 340                                 Console.WriteLine ("branch next {0}", next);
 341                 }
 342
 343                 public void EmitJump (LinkRef target) {
 344                         BeginLink (target);
 345                         Emit (OpCode.Jump, 0);
 346                         EmitLink (target);
 347
 348                         if (trace_regex)
 349                                 Console.WriteLine ("jmp target {0}", target);
 350                 }
 351
 352                 public void EmitRepeat (int min, int max, bool lazy, LinkRef until) {
 353                         BeginLink (until);
 354                         Emit (OpCode.Repeat, MakeFlags (false, false, false, lazy));
 355                         EmitLink (until);
 356                         EmitCount (min);
 357                         EmitCount (max);
 358
 359                         if (trace_regex)
 360                                 Console.WriteLine ("repeat min {0} max {1} lazy {2} until {3}", min, max, lazy, until);
 361                 }
 362
 363                 public void EmitUntil (LinkRef repeat) {
 364                         ResolveLink (repeat);
 365                         Emit (OpCode.Until);
 366
 367                         if (trace_regex)
 368                                 Console.WriteLine ("end until {0}", repeat);
 369                 }
 370
 371                 public void EmitFastRepeat (int min, int max, bool lazy, LinkRef tail) {
 372                         BeginLink (tail);
 373                         Emit (OpCode.FastRepeat, MakeFlags (false, false, false, lazy));
 374                         EmitLink (tail);
 375                         EmitCount (min);
 376                         EmitCount (max);
 377
 378                         if (trace_regex)
 379                                 Console.WriteLine ("repeat-fast min {0} max {1} lazy {2} tail {3}", min, max, lazy, tail);
 380                 }
 381
 382                 public void EmitIn (LinkRef tail) {
 383                         BeginLink (tail);
 384                         Emit (OpCode.In);
 385                         EmitLink (tail);
 386
 387                         if (trace_regex)
 388                                 Console.WriteLine ("in tail {0}", tail);
 389                 }
 390
 391                 public void EmitAnchor (bool reverse, int offset, LinkRef tail) {
 392                         BeginLink (tail);
 393                         Emit (OpCode.Anchor, MakeFlags(false, false, reverse, false));
 394                         EmitLink (tail);
 395                         Emit ((ushort)offset);
 396
 397                         if (trace_regex)
 398                                 Console.WriteLine ("anchor reverse {0} offset {1} tail {2}", reverse, offset, tail);
 399                 }
 400
 401                 public void EmitInfo (int count, int min, int max) {
 402                         Emit (OpCode.Info);
 403                         EmitCount (count);
 404                         EmitCount (min);
 405                         EmitCount (max);
 406
 407                         if (trace_regex)
 408                                 Console.WriteLine ("info group count {0} match_min {1} match_max {2}", count, min, max);
 409                 }
 410
 411                 public LinkRef NewLink () {
 412                         return new PatternLinkStack ();
 413                 }
 414
 415                 public void ResolveLink (LinkRef lref) {
 416                         PatternLinkStack stack = (PatternLinkStack)lref;
 417
 418                         while (stack.Pop ())
 419                                 pgm[stack.OffsetAddress] = (ushort)stack.GetOffset (CurrentAddress);
 420                 }
 421
 422                 public void EmitBranchEnd(){}
 423                 public void EmitAlternationEnd(){}
 424
 425                 // private members
 426
 427                 private static OpFlags MakeFlags (bool negate, bool ignore, bool reverse, bool lazy) {
 428                         OpFlags flags = 0;
 429                         if (negate) flags |= OpFlags.Negate;
 430                         if (ignore) flags |= OpFlags.IgnoreCase;
 431                         if (reverse) flags |= OpFlags.RightToLeft;
 432                         if (lazy) flags |= OpFlags.Lazy;
 433
 434                         return flags;
 435                 }
 436
 437                 private void Emit (OpCode op) {
 438                         Emit (op, (OpFlags)0);
 439                 }
 440
 441                 private void Emit (OpCode op, OpFlags flags) {
 442                         Emit (EncodeOp (op, flags));
 443                 }
 444
 445                 private void Emit (ushort word) {
 446                         pgm.Add (word);
 447                 }
 448
 449                 private int CurrentAddress {
 450                         get { return pgm.Count; }
 451                 }
 452
 453                 private void BeginLink (LinkRef lref) {
 454                         PatternLinkStack stack = (PatternLinkStack)lref;
 455                         stack.BaseAddress = CurrentAddress;
 456                 }
 457
 458                 private void EmitLink (LinkRef lref) {
 459                         PatternLinkStack stack = (PatternLinkStack)lref;
 460                         stack.OffsetAddress = CurrentAddress;
 461                         Emit ((ushort)0);       // placeholder
 462                         stack.Push ();
 463                 }
 464
 465
 466                 private class PatternLinkStack : LinkStack {
 467                         public PatternLinkStack () {
 468                         }
 469
 470                         public int BaseAddress {
 471                                 set { link.base_addr = value; }
 472                         }
 473
 474                         public int OffsetAddress {
 475                                 get { return link.offset_addr; }
 476                                 set { link.offset_addr = value; }
 477                         }
 478
 479                         public int GetOffset (int target_addr) {
 480                                 return target_addr - link.base_addr;
 481                         }
 482
 483                         // LinkStack implementation
 484
 485                         protected override object GetCurrent () { return link; }
 486                         protected override void SetCurrent (object l) { link = (Link)l; }
 487
 488                         private struct Link {
 489                                 public int base_addr;
 490                                 public int offset_addr;
 491                         }
 492
 493                         Link link;
 494                 }
 495
 496                 private ArrayList pgm;
 497         }
 498
 499         abstract class LinkStack : LinkRef {
 500                 public LinkStack () {
 501                         stack = new Stack ();
 502                 }
 503
 504                 public void Push () {
 505                         stack.Push (GetCurrent ());
 506                 }
 507
 508                 public bool Pop () {
 509                         if (stack.Count > 0) {
 510                                 SetCurrent (stack.Pop ());
 511                                 return true;
 512                         }
 513
 514                         return false;
 515                 }
 516
 517                 protected abstract object GetCurrent ();
 518                 protected abstract void SetCurrent (object l);
 519
 520                 private Stack stack;
 521         }
 522
 523         //Used by CILCompiler and Interpreter
 524         internal struct Mark {
 525                 public int Start, End;
 526                 public int Previous;
 527
 528                 public bool IsDefined {
 529                         get { return Start >= 0 && End >= 0; }
 530                 }
 531
 532                 public int Index {
 533                         get { return Start < End ? Start : End; }
 534                 }
 535
 536                 public int Length {
 537                         get { return Start < End ? End - Start : Start - End; }
 538                 }
 539         }
 540
 541 }