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 using System;
  10 using System.Collections;
  11
  12 namespace System.Text.RegularExpressions {
  13         abstract class LinkRef {
  14                 // empty
  15         }
  16
  17         interface ICompiler {
  18                 void Reset ();
  19                 IMachineFactory GetMachineFactory ();
  20
  21                 // instruction emission
  22
  23                 void EmitFalse ();
  24                 void EmitTrue ();
  25
  26                 // character matching
  27
  28                 void EmitCharacter (char c, bool negate, bool ignore, bool reverse);
  29                 void EmitCategory (Category cat, bool negate, bool reverse);
  30                 void EmitRange (char lo, char hi, bool negate, bool ignore, bool reverse);
  31                 void EmitSet (char lo, BitArray set, bool negate, bool ignore, bool reverse);
  32
  33                 // other operators
  34
  35                 void EmitString (string str, bool ignore, bool reverse);
  36                 void EmitPosition (Position pos);
  37                 void EmitOpen (int gid);
  38                 void EmitClose (int gid);
  39                 void EmitBalanceStart(int gid, int balance, bool capture,  LinkRef tail);
  40                 void EmitBalance ();
  41                 void EmitReference (int gid, bool ignore, bool reverse);
  42
  43                 // constructs
  44
  45                 void EmitIfDefined (int gid, LinkRef tail);
  46                 void EmitSub (LinkRef tail);
  47                 void EmitTest (LinkRef yes, LinkRef tail);
  48                 void EmitBranch (LinkRef next);
  49                 void EmitJump (LinkRef target);
  50                 void EmitRepeat (int min, int max, bool lazy, LinkRef until);
  51                 void EmitUntil (LinkRef repeat);
  52                 void EmitIn (LinkRef tail);
  53                 void EmitInfo (int count, int min, int max);
  54                 void EmitFastRepeat (int min, int max, bool lazy, LinkRef tail);
  55                 void EmitAnchor (bool reverse, int offset, LinkRef tail);
  56
  57                 // event for the CILCompiler
  58                 void EmitBranchEnd();
  59                 void EmitAlternationEnd();
  60
  61                 LinkRef NewLink ();
  62                 void ResolveLink (LinkRef link);
  63         }
  64
  65         class InterpreterFactory : IMachineFactory {
  66                 public InterpreterFactory (ushort[] pattern) {
  67                         this.pattern = pattern;
  68                 }
  69
  70                 public IMachine NewInstance () {
  71                         return new Interpreter (pattern);
  72                 }
  73
  74                 public int GroupCount {
  75                         get { return pattern[0]; }
  76                 }
  77
  78                 public IDictionary Mapping {
  79                         get { return mapping; }
  80                         set { mapping = value; }
  81                 }
  82
  83                 private IDictionary mapping;
  84                 private ushort[] pattern;
  85         }
  86
  87         class PatternCompiler : ICompiler {
  88                 public static ushort EncodeOp (OpCode op, OpFlags flags) {
  89                         return (ushort)((int)op | ((int)flags & 0xff00));
  90                 }
  91
  92                 public static void DecodeOp (ushort word, out OpCode op, out OpFlags flags) {
  93                         op = (OpCode)(word & 0x00ff);
  94                         flags = (OpFlags)(word & 0xff00);
  95                 }
  96
  97                 public PatternCompiler () {
  98                         pgm = new ArrayList ();
  99                 }
 100
 101                 // ICompiler implementation
 102
 103                 public void Reset () {
 104                         pgm.Clear ();
 105                 }
 106
 107                 public IMachineFactory GetMachineFactory () {
 108                         ushort[] image = new ushort[pgm.Count];
 109                         pgm.CopyTo (image);
 110
 111                         return new InterpreterFactory (image);
 112                 }
 113
 114                 public void EmitFalse () {
 115                         Emit (OpCode.False);
 116                 }
 117
 118                 public void EmitTrue () {
 119                         Emit (OpCode.True);
 120                 }
 121
 122                 public void EmitCharacter (char c, bool negate, bool ignore, bool reverse) {
 123                         Emit (OpCode.Character, MakeFlags (negate, ignore, reverse, false));
 124
 125                         if (ignore)
 126                                 c = Char.ToLower (c);
 127
 128                         Emit ((ushort)c);
 129                 }
 130
 131                 public void EmitCategory (Category cat, bool negate, bool reverse) {
 132                         Emit (OpCode.Category, MakeFlags (negate, false, reverse, false));
 133                         Emit ((ushort)cat);
 134                 }
 135
 136                 public void EmitRange (char lo, char hi, bool negate, bool ignore, bool reverse) {
 137                         Emit (OpCode.Range, MakeFlags (negate, ignore, reverse, false));
 138                         Emit ((ushort)lo);
 139                         Emit ((ushort)hi);
 140                 }
 141
 142                 public void EmitSet (char lo, BitArray set, bool negate, bool ignore, bool reverse) {
 143                         Emit (OpCode.Set, MakeFlags (negate, ignore, reverse, false));
 144                         Emit ((ushort)lo);
 145
 146                         int len = (set.Length + 0xf) >> 4;
 147                         Emit ((ushort)len);
 148
 149                         int b = 0;
 150                         while (len -- != 0) {
 151                                 ushort word = 0;
 152                                 for (int i = 0; i < 16; ++ i) {
 153                                         if (b >= set.Length)
 154                                                 break;
 155
 156                                         if (set[b ++])
 157                                                 word |= (ushort)(1 << i);
 158                                 }
 159
 160                                 Emit (word);
 161                         }
 162                 }
 163
 164                 public void EmitString (string str, bool ignore, bool reverse) {
 165                         Emit (OpCode.String, MakeFlags (false, ignore, reverse, false));
 166                         int len = str.Length;
 167                         Emit ((ushort)len);
 168
 169                         if (ignore)
 170                                 str = str.ToLower ();
 171
 172                         for (int i = 0; i < len; ++ i)
 173                                 Emit ((ushort)str[i]);
 174                 }
 175
 176                 public void EmitPosition (Position pos) {
 177                         Emit (OpCode.Position, 0);
 178                         Emit ((ushort)pos);
 179                 }
 180
 181                 public void EmitOpen (int gid) {
 182                         Emit (OpCode.Open);
 183                         Emit ((ushort)gid);
 184                 }
 185
 186                 public void EmitClose (int gid) {
 187                         Emit (OpCode.Close);
 188                         Emit ((ushort)gid);
 189                 }
 190
 191
 192
 193                 public void EmitBalanceStart (int gid, int balance, bool capture, LinkRef tail) {
 194                         BeginLink (tail);
 195                         Emit (OpCode.BalanceStart);
 196                         Emit ((ushort)gid);
 197                         Emit ((ushort)balance);
 198                         Emit ((ushort)(capture ? 1 : 0));
 199                         EmitLink (tail);
 200                 }
 201
 202                 public void EmitBalance () {
 203                         Emit (OpCode.Balance);
 204                 }
 205
 206                 public void EmitReference (int gid, bool ignore, bool reverse) {
 207                         Emit (OpCode.Reference, MakeFlags (false, ignore, reverse, false));
 208                         Emit ((ushort)gid);
 209                 }
 210
 211                 public void EmitIfDefined (int gid, LinkRef tail) {
 212                         BeginLink (tail);
 213                         Emit (OpCode.IfDefined);
 214                         EmitLink (tail);
 215                         Emit ((ushort)gid);
 216                 }
 217
 218                 public void EmitSub (LinkRef tail) {
 219                         BeginLink (tail);
 220                         Emit (OpCode.Sub);
 221                         EmitLink (tail);
 222                 }
 223
 224                 public void EmitTest (LinkRef yes, LinkRef tail) {
 225                         BeginLink (yes);
 226                         BeginLink (tail);
 227                         Emit (OpCode.Test);
 228                         EmitLink (yes);
 229                         EmitLink (tail);
 230                 }
 231
 232                 public void EmitBranch (LinkRef next) {
 233                         BeginLink (next);
 234                         Emit (OpCode.Branch, 0);
 235                         EmitLink (next);
 236                 }
 237
 238                 public void EmitJump (LinkRef target) {
 239                         BeginLink (target);
 240                         Emit (OpCode.Jump, 0);
 241                         EmitLink (target);
 242                 }
 243
 244                 public void EmitRepeat (int min, int max, bool lazy, LinkRef until) {
 245                         BeginLink (until);
 246                         Emit (OpCode.Repeat, MakeFlags (false, false, false, lazy));
 247                         EmitLink (until);
 248                         Emit ((ushort)min);
 249                         Emit ((ushort)max);
 250                 }
 251
 252                 public void EmitUntil (LinkRef repeat) {
 253                         ResolveLink (repeat);
 254                         Emit (OpCode.Until);
 255                 }
 256
 257                 public void EmitFastRepeat (int min, int max, bool lazy, LinkRef tail) {
 258                         BeginLink (tail);
 259                         Emit (OpCode.FastRepeat, MakeFlags (false, false, false, lazy));
 260                         EmitLink (tail);
 261                         Emit ((ushort)min);
 262                         Emit ((ushort)max);
 263                 }
 264
 265                 public void EmitIn (LinkRef tail) {
 266                         BeginLink (tail);
 267                         Emit (OpCode.In);
 268                         EmitLink (tail);
 269                 }
 270
 271                 public void EmitAnchor (bool reverse, int offset, LinkRef tail) {
 272                         BeginLink (tail);
 273                         Emit (OpCode.Anchor, MakeFlags(false, false, reverse, false));
 274                         EmitLink (tail);
 275                         Emit ((ushort)offset);
 276                 }
 277
 278                 public void EmitInfo (int count, int min, int max) {
 279                         Emit (OpCode.Info);
 280                         Emit ((ushort)count);
 281                         Emit ((ushort)min);
 282                         Emit ((ushort)max);
 283                 }
 284
 285                 public LinkRef NewLink () {
 286                         return new PatternLinkStack ();
 287                 }
 288
 289                 public void ResolveLink (LinkRef lref) {
 290                         PatternLinkStack stack = (PatternLinkStack)lref;
 291
 292                         while (stack.Pop ())
 293                                 pgm[stack.OffsetAddress] = (ushort)stack.GetOffset (CurrentAddress);
 294                 }
 295
 296                 public void EmitBranchEnd(){}
 297                 public void EmitAlternationEnd(){}
 298
 299                 // private members
 300
 301                 private static OpFlags MakeFlags (bool negate, bool ignore, bool reverse, bool lazy) {
 302                         OpFlags flags = 0;
 303                         if (negate) flags |= OpFlags.Negate;
 304                         if (ignore) flags |= OpFlags.IgnoreCase;
 305                         if (reverse) flags |= OpFlags.RightToLeft;
 306                         if (lazy) flags |= OpFlags.Lazy;
 307
 308                         return flags;
 309                 }
 310
 311                 private void Emit (OpCode op) {
 312                         Emit (op, (OpFlags)0);
 313                 }
 314
 315                 private void Emit (OpCode op, OpFlags flags) {
 316                         Emit (EncodeOp (op, flags));
 317                 }
 318
 319                 private void Emit (ushort word) {
 320                         pgm.Add (word);
 321                 }
 322
 323                 private int CurrentAddress {
 324                         get { return pgm.Count; }
 325                 }
 326
 327                 private void BeginLink (LinkRef lref) {
 328                         PatternLinkStack stack = (PatternLinkStack)lref;
 329                         stack.BaseAddress = CurrentAddress;
 330                 }
 331
 332                 private void EmitLink (LinkRef lref) {
 333                         PatternLinkStack stack = (PatternLinkStack)lref;
 334                         stack.OffsetAddress = CurrentAddress;
 335                         Emit ((ushort)0);       // placeholder
 336                         stack.Push ();
 337                 }
 338
 339
 340                 private class PatternLinkStack : LinkStack {
 341                         public PatternLinkStack () {
 342                         }
 343
 344                         public int BaseAddress {
 345                                 set { link.base_addr = value; }
 346                         }
 347
 348                         public int OffsetAddress {
 349                                 get { return link.offset_addr; }
 350                                 set { link.offset_addr = value; }
 351                         }
 352
 353                         public int GetOffset (int target_addr) {
 354                                 return target_addr - link.base_addr;
 355                         }
 356
 357                         // LinkStack implementation
 358
 359                         protected override object GetCurrent () { return link; }
 360                         protected override void SetCurrent (object l) { link = (Link)l; }
 361
 362                         private struct Link {
 363                                 public int base_addr;
 364                                 public int offset_addr;
 365                         }
 366
 367                         Link link;
 368                 }
 369
 370                 private ArrayList pgm;
 371         }
 372
 373         abstract class LinkStack : LinkRef {
 374                 public LinkStack () {
 375                         stack = new Stack ();
 376                 }
 377
 378                 public void Push () {
 379                         stack.Push (GetCurrent ());
 380                 }
 381
 382                 public bool Pop () {
 383                         if (stack.Count > 0) {
 384                                 SetCurrent (stack.Pop ());
 385                                 return true;
 386                         }
 387
 388                         return false;
 389                 }
 390
 391                 protected abstract object GetCurrent ();
 392                 protected abstract void SetCurrent (object l);
 393
 394                 private Stack stack;
 395         }
 396
 397         //Used by CILCompiler and Interpreter
 398         internal struct Mark {
 399                 public int Start, End;
 400                 public int Previous;
 401
 402                 public bool IsDefined {
 403                         get { return Start >= 0 && End >= 0; }
 404                 }
 405
 406                 public int Index {
 407                         get { return Start < End ? Start : End; }
 408                 }
 409
 410                 public int Length {
 411                         get { return Start < End ? End - Start : Start - End; }
 412                 }
 413         }
 414
 415 }