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 IDictionary Mapping {
 101                         get { return mapping; }
 102                         set { mapping = value; }
 103                 }
 104
 105                 public string [] NamesMapping {
 106                         get { return namesMapping; }
 107                         set { namesMapping = value; }
 108                 }
 109
 110                 private IDictionary mapping;
 111                 private ushort[] pattern;
 112                 private string [] namesMapping;
 113         }
 114
 115         class PatternCompiler : ICompiler {
 116                 public static ushort EncodeOp (OpCode op, OpFlags flags) {
 117                         return (ushort)((int)op | ((int)flags & 0xff00));
 118                 }
 119
 120                 public static void DecodeOp (ushort word, out OpCode op, out OpFlags flags) {
 121                         op = (OpCode)(word & 0x00ff);
 122                         flags = (OpFlags)(word & 0xff00);
 123                 }
 124
 125                 public PatternCompiler () {
 126                         pgm = new ArrayList ();
 127                 }
 128
 129                 // ICompiler implementation
 130
 131                 public void Reset () {
 132                         pgm.Clear ();
 133                 }
 134
 135                 public IMachineFactory GetMachineFactory () {
 136                         ushort[] image = new ushort[pgm.Count];
 137                         pgm.CopyTo (image);
 138
 139                         return new InterpreterFactory (image);
 140                 }
 141
 142                 public void EmitFalse () {
 143                         Emit (OpCode.False);
 144                 }
 145
 146                 public void EmitTrue () {
 147                         Emit (OpCode.True);
 148                 }
 149
 150                 void EmitCount (int count)
 151                 {
 152                         uint ucount = (uint) count;
 153                         Emit ((ushort) (ucount & 0xFFFF)); // lo 16bits
 154                         Emit ((ushort) (ucount >> 16));    // hi
 155                 }
 156
 157                 public void EmitCharacter (char c, bool negate, bool ignore, bool reverse) {
 158                         Emit (OpCode.Character, MakeFlags (negate, ignore, reverse, false));
 159
 160                         if (ignore)
 161                                 c = Char.ToLower (c);
 162
 163                         Emit ((ushort)c);
 164                 }
 165
 166                 public void EmitCategory (Category cat, bool negate, bool reverse) {
 167                         Emit (OpCode.Category, MakeFlags (negate, false, reverse, false));
 168                         Emit ((ushort)cat);
 169                 }
 170
 171                 public void EmitNotCategory (Category cat, bool negate, bool reverse) {
 172                         Emit (OpCode.NotCategory, MakeFlags (negate, false, reverse, false));
 173                         Emit ((ushort)cat);
 174                 }
 175
 176                 public void EmitRange (char lo, char hi, bool negate, bool ignore, bool reverse) {
 177                         Emit (OpCode.Range, MakeFlags (negate, ignore, reverse, false));
 178                         Emit ((ushort)lo);
 179                         Emit ((ushort)hi);
 180                 }
 181
 182                 public void EmitSet (char lo, BitArray set, bool negate, bool ignore, bool reverse) {
 183                         Emit (OpCode.Set, MakeFlags (negate, ignore, reverse, false));
 184                         Emit ((ushort)lo);
 185
 186                         int len = (set.Length + 0xf) >> 4;
 187                         Emit ((ushort)len);
 188
 189                         int b = 0;
 190                         while (len -- != 0) {
 191                                 ushort word = 0;
 192                                 for (int i = 0; i < 16; ++ i) {
 193                                         if (b >= set.Length)
 194                                                 break;
 195
 196                                         if (set[b ++])
 197                                                 word |= (ushort)(1 << i);
 198                                 }
 199
 200                                 Emit (word);
 201                         }
 202                 }
 203
 204                 public void EmitString (string str, bool ignore, bool reverse) {
 205                         Emit (OpCode.String, MakeFlags (false, ignore, reverse, false));
 206                         int len = str.Length;
 207                         Emit ((ushort)len);
 208
 209                         if (ignore)
 210                                 str = str.ToLower ();
 211
 212                         for (int i = 0; i < len; ++ i)
 213                                 Emit ((ushort)str[i]);
 214                 }
 215
 216                 public void EmitPosition (Position pos) {
 217                         Emit (OpCode.Position, 0);
 218                         Emit ((ushort)pos);
 219                 }
 220
 221                 public void EmitOpen (int gid) {
 222                         Emit (OpCode.Open);
 223                         Emit ((ushort)gid);
 224                 }
 225
 226                 public void EmitClose (int gid) {
 227                         Emit (OpCode.Close);
 228                         Emit ((ushort)gid);
 229                 }
 230
 231
 232
 233                 public void EmitBalanceStart (int gid, int balance, bool capture, LinkRef tail) {
 234                         BeginLink (tail);
 235                         Emit (OpCode.BalanceStart);
 236                         Emit ((ushort)gid);
 237                         Emit ((ushort)balance);
 238                         Emit ((ushort)(capture ? 1 : 0));
 239                         EmitLink (tail);
 240                 }
 241
 242                 public void EmitBalance () {
 243                         Emit (OpCode.Balance);
 244                 }
 245
 246                 public void EmitReference (int gid, bool ignore, bool reverse) {
 247                         Emit (OpCode.Reference, MakeFlags (false, ignore, reverse, false));
 248                         Emit ((ushort)gid);
 249                 }
 250
 251                 public void EmitIfDefined (int gid, LinkRef tail) {
 252                         BeginLink (tail);
 253                         Emit (OpCode.IfDefined);
 254                         EmitLink (tail);
 255                         Emit ((ushort)gid);
 256                 }
 257
 258                 public void EmitSub (LinkRef tail) {
 259                         BeginLink (tail);
 260                         Emit (OpCode.Sub);
 261                         EmitLink (tail);
 262                 }
 263
 264                 public void EmitTest (LinkRef yes, LinkRef tail) {
 265                         BeginLink (yes);
 266                         BeginLink (tail);
 267                         Emit (OpCode.Test);
 268                         EmitLink (yes);
 269                         EmitLink (tail);
 270                 }
 271
 272                 public void EmitBranch (LinkRef next) {
 273                         BeginLink (next);
 274                         Emit (OpCode.Branch, 0);
 275                         EmitLink (next);
 276                 }
 277
 278                 public void EmitJump (LinkRef target) {
 279                         BeginLink (target);
 280                         Emit (OpCode.Jump, 0);
 281                         EmitLink (target);
 282                 }
 283
 284                 public void EmitRepeat (int min, int max, bool lazy, LinkRef until) {
 285                         BeginLink (until);
 286                         Emit (OpCode.Repeat, MakeFlags (false, false, false, lazy));
 287                         EmitLink (until);
 288                         EmitCount (min);
 289                         EmitCount (max);
 290                 }
 291
 292                 public void EmitUntil (LinkRef repeat) {
 293                         ResolveLink (repeat);
 294                         Emit (OpCode.Until);
 295                 }
 296
 297                 public void EmitFastRepeat (int min, int max, bool lazy, LinkRef tail) {
 298                         BeginLink (tail);
 299                         Emit (OpCode.FastRepeat, MakeFlags (false, false, false, lazy));
 300                         EmitLink (tail);
 301                         EmitCount (min);
 302                         EmitCount (max);
 303                 }
 304
 305                 public void EmitIn (LinkRef tail) {
 306                         BeginLink (tail);
 307                         Emit (OpCode.In);
 308                         EmitLink (tail);
 309                 }
 310
 311                 public void EmitAnchor (bool reverse, int offset, LinkRef tail) {
 312                         BeginLink (tail);
 313                         Emit (OpCode.Anchor, MakeFlags(false, false, reverse, false));
 314                         EmitLink (tail);
 315                         Emit ((ushort)offset);
 316                 }
 317
 318                 public void EmitInfo (int count, int min, int max) {
 319                         Emit (OpCode.Info);
 320                         EmitCount (count);
 321                         EmitCount (min);
 322                         EmitCount (max);
 323                 }
 324
 325                 public LinkRef NewLink () {
 326                         return new PatternLinkStack ();
 327                 }
 328
 329                 public void ResolveLink (LinkRef lref) {
 330                         PatternLinkStack stack = (PatternLinkStack)lref;
 331
 332                         while (stack.Pop ())
 333                                 pgm[stack.OffsetAddress] = (ushort)stack.GetOffset (CurrentAddress);
 334                 }
 335
 336                 public void EmitBranchEnd(){}
 337                 public void EmitAlternationEnd(){}
 338
 339                 // private members
 340
 341                 private static OpFlags MakeFlags (bool negate, bool ignore, bool reverse, bool lazy) {
 342                         OpFlags flags = 0;
 343                         if (negate) flags |= OpFlags.Negate;
 344                         if (ignore) flags |= OpFlags.IgnoreCase;
 345                         if (reverse) flags |= OpFlags.RightToLeft;
 346                         if (lazy) flags |= OpFlags.Lazy;
 347
 348                         return flags;
 349                 }
 350
 351                 private void Emit (OpCode op) {
 352                         Emit (op, (OpFlags)0);
 353                 }
 354
 355                 private void Emit (OpCode op, OpFlags flags) {
 356                         Emit (EncodeOp (op, flags));
 357                 }
 358
 359                 private void Emit (ushort word) {
 360                         pgm.Add (word);
 361                 }
 362
 363                 private int CurrentAddress {
 364                         get { return pgm.Count; }
 365                 }
 366
 367                 private void BeginLink (LinkRef lref) {
 368                         PatternLinkStack stack = (PatternLinkStack)lref;
 369                         stack.BaseAddress = CurrentAddress;
 370                 }
 371
 372                 private void EmitLink (LinkRef lref) {
 373                         PatternLinkStack stack = (PatternLinkStack)lref;
 374                         stack.OffsetAddress = CurrentAddress;
 375                         Emit ((ushort)0);       // placeholder
 376                         stack.Push ();
 377                 }
 378
 379
 380                 private class PatternLinkStack : LinkStack {
 381                         public PatternLinkStack () {
 382                         }
 383
 384                         public int BaseAddress {
 385                                 set { link.base_addr = value; }
 386                         }
 387
 388                         public int OffsetAddress {
 389                                 get { return link.offset_addr; }
 390                                 set { link.offset_addr = value; }
 391                         }
 392
 393                         public int GetOffset (int target_addr) {
 394                                 return target_addr - link.base_addr;
 395                         }
 396
 397                         // LinkStack implementation
 398
 399                         protected override object GetCurrent () { return link; }
 400                         protected override void SetCurrent (object l) { link = (Link)l; }
 401
 402                         private struct Link {
 403                                 public int base_addr;
 404                                 public int offset_addr;
 405                         }
 406
 407                         Link link;
 408                 }
 409
 410                 private ArrayList pgm;
 411         }
 412
 413         abstract class LinkStack : LinkRef {
 414                 public LinkStack () {
 415                         stack = new Stack ();
 416                 }
 417
 418                 public void Push () {
 419                         stack.Push (GetCurrent ());
 420                 }
 421
 422                 public bool Pop () {
 423                         if (stack.Count > 0) {
 424                                 SetCurrent (stack.Pop ());
 425                                 return true;
 426                         }
 427
 428                         return false;
 429                 }
 430
 431                 protected abstract object GetCurrent ();
 432                 protected abstract void SetCurrent (object l);
 433
 434                 private Stack stack;
 435         }
 436
 437         //Used by CILCompiler and Interpreter
 438         internal struct Mark {
 439                 public int Start, End;
 440                 public int Previous;
 441
 442                 public bool IsDefined {
 443                         get { return Start >= 0 && End >= 0; }
 444                 }
 445
 446                 public int Index {
 447                         get { return Start < End ? Start : End; }
 448                 }
 449
 450                 public int Length {
 451                         get { return Start < End ? End - Start : Start - End; }
 452                 }
 453         }
 454
 455 }