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