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