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

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