The Labs \ Source Viewer \ SSCLI \ System.Text.RegularExpressions \ RegexWriter

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexWriter.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. // This RegexWriter class is internal to the Regex package.
  16. // It builds a block of regular expression codes (RegexCode)
  17. // from a RegexTree parse tree.
  18. // Implementation notes:
  19. //
  20. // This step is as simple as walking the tree and emitting
  21. // sequences of codes.
  22. //
  23. namespace System.Text.RegularExpressions
  24. {
  25.    
  26.     using System.Collections;
  27.     using System.Collections.Specialized;
  28.     using System.Globalization;
  29.    
  30.     internal sealed class RegexWriter
  31.     {
  32.         internal int[] _intStack;
  33.         internal int _depth;
  34.         internal int[] _emitted;
  35.         internal int _curpos;
  36.         internal IDictionary _stringhash;
  37.         internal ArrayList _stringtable;
  38.         // not used! internal int _stringcount;
  39.         internal bool _counting;
  40.         internal int _count;
  41.         internal int _trackcount;
  42.         internal Hashtable _caps;
  43.        
  44.         internal const int BeforeChild = 64;
  45.         internal const int AfterChild = 128;
  46.        
  47. /*
  48.         * This is the only function that should be called from outside.
  49.         * It takes a RegexTree and creates a corresponding RegexCode.
  50.         */       
  51.         static internal RegexCode Write(RegexTree t)
  52.         {
  53.             RegexWriter w = new RegexWriter();
  54.             RegexCode retval = w.RegexCodeFromRegexTree(t);
  55.             #if DBG
  56.             if (t.Debug) {
  57.                 t.Dump();
  58.                 retval.Dump();
  59.             }
  60.             #endif
  61.             return retval;
  62.         }
  63.        
  64. /*
  65.         * private constructor; can't be created outside
  66.         */       
  67.         private RegexWriter()
  68.         {
  69.             _intStack = new int[32];
  70.             _emitted = new int[32];
  71.             _stringhash = new HybridDictionary();
  72.             _stringtable = new ArrayList();
  73.         }
  74.        
  75. /*
  76.         * To avoid recursion, we use a simple integer stack.
  77.         * This is the push.
  78.         */       
  79.         internal void PushInt(int I)
  80.         {
  81.             if (_depth >= _intStack.Length) {
  82.                 int[] expanded = new int[_depth * 2];
  83.                
  84.                 System.Array.Copy(_intStack, 0, expanded, 0, _depth);
  85.                
  86.                 _intStack = expanded;
  87.             }
  88.            
  89.             _intStack[_depth++] = I;
  90.         }
  91.        
  92. /*
  93.         * True if the stack is empty.
  94.         */       
  95.         internal bool EmptyStack()
  96.         {
  97.             return _depth == 0;
  98.         }
  99.        
  100. /*
  101.         * This is the pop.
  102.         */       
  103.         internal int PopInt()
  104.         {
  105.             return _intStack[--_depth];
  106.         }
  107.        
  108. /*
  109.         * Returns the current position in the emitted code.
  110.         */       
  111.         internal int CurPos()
  112.         {
  113.             return _curpos;
  114.         }
  115.        
  116. /*
  117.         * Fixes up a jump instruction at the specified offset
  118.         * so that it jumps to the specified jumpDest.
  119.         */       
  120.         internal void PatchJump(int Offset, int jumpDest)
  121.         {
  122.             _emitted[Offset + 1] = jumpDest;
  123.         }
  124.        
  125. /*
  126.         * Emits a zero-argument operation. Note that the emit
  127.         * functions all run in two modes: they can emit code, or
  128.         * they can just count the size of the code.
  129.         */       
  130.         internal void Emit(int op)
  131.         {
  132.             if (_counting) {
  133.                 _count += 1;
  134.                 if (RegexCode.OpcodeBacktracks(op))
  135.                     _trackcount += 1;
  136.                 return;
  137.             }
  138.             _emitted[_curpos++] = op;
  139.         }
  140.        
  141. /*
  142.         * Emits a one-argument operation.
  143.         */       
  144.         internal void Emit(int op, int opd1)
  145.         {
  146.             if (_counting) {
  147.                 _count += 2;
  148.                 if (RegexCode.OpcodeBacktracks(op))
  149.                     _trackcount += 1;
  150.                 return;
  151.             }
  152.             _emitted[_curpos++] = op;
  153.             _emitted[_curpos++] = opd1;
  154.         }
  155.        
  156. /*
  157.         * Emits a two-argument operation.
  158.         */       
  159.         internal void Emit(int op, int opd1, int opd2)
  160.         {
  161.             if (_counting) {
  162.                 _count += 3;
  163.                 if (RegexCode.OpcodeBacktracks(op))
  164.                     _trackcount += 1;
  165.                 return;
  166.             }
  167.             _emitted[_curpos++] = op;
  168.             _emitted[_curpos++] = opd1;
  169.             _emitted[_curpos++] = opd2;
  170.         }
  171.        
  172. /*
  173.         * Returns an index in the string table for a string;
  174.         * uses a hashtable to eliminate duplicates.
  175.         */       
  176.         internal int StringCode(string str)
  177.         {
  178.             Int32 i;
  179.            
  180.             if (_counting)
  181.                 return 0;
  182.            
  183.             if (str == null)
  184.                 str = String.Empty;
  185.            
  186.             if (_stringhash.Contains(str)) {
  187.                 i = (Int32)_stringhash[str];
  188.             }
  189.             else {
  190.                 i = _stringtable.Count;
  191.                 _stringhash[str] = i;
  192.                 _stringtable.Add(str);
  193.             }
  194.            
  195.             return i;
  196.         }
  197.        
  198. /*
  199.         * Just returns an exception; should be dead code
  200.         */       
  201.         internal ArgumentException MakeException(string message)
  202.         {
  203.             return new ArgumentException(message);
  204.         }
  205.        
  206. /*
  207.         * When generating code on a regex that uses a sparse set
  208.         * of capture slots, we hash them to a dense set of indices
  209.         * for an array of capture slots. Instead of doing the hash
  210.         * at match time, it's done at compile time, here.
  211.         */       
  212.         internal int MapCapnum(int capnum)
  213.         {
  214.             if (capnum == -1)
  215.                 return -1;
  216.            
  217.             if (_caps != null)
  218.                 return (Int32)_caps[capnum];
  219.             else
  220.                 return capnum;
  221.         }
  222.        
  223. /*
  224.         * The top level RegexCode generator. It does a depth-first walk
  225.         * through the tree and calls EmitFragment to emits code before
  226.         * and after each child of an interior node, and at each leaf.
  227.         *
  228.         * It runs two passes, first to count the size of the generated
  229.         * code, and second to generate the code.
  230.         *
  231.         * <CONSIDER>we need to time it against the alternative, which is
  232.         * to just generate the code and grow the array as we go.</CONSIDER>
  233.         */       
  234.         internal RegexCode RegexCodeFromRegexTree(RegexTree tree)
  235.         {
  236.             RegexNode curNode;
  237.             int curChild;
  238.             int capsize;
  239.             RegexPrefix fcPrefix;
  240.             RegexPrefix prefix;
  241.             int anchors;
  242.             RegexBoyerMoore bmPrefix;
  243.             bool rtl;
  244.            
  245.             // construct sparse capnum mapping if some numbers are unused
  246.            
  247.             if (tree._capnumlist == null || tree._captop == tree._capnumlist.Length) {
  248.                 capsize = tree._captop;
  249.                 _caps = null;
  250.             }
  251.             else {
  252.                 capsize = tree._capnumlist.Length;
  253.                 _caps = tree._caps;
  254.                 for (int i = 0; i < tree._capnumlist.Length; i++)
  255.                     _caps[tree._capnumlist[i]] = i;
  256.             }
  257.            
  258.             _counting = true;
  259.            
  260.             for (;;) {
  261.                 if (!_counting)
  262.                     _emitted = new int[_count];
  263.                
  264.                 curNode = tree._root;
  265.                 curChild = 0;
  266.                
  267.                 Emit(RegexCode.Lazybranch, 0);
  268.                
  269.                 for (;;) {
  270.                     if (curNode._children == null) {
  271.                         EmitFragment(curNode._type, curNode, 0);
  272.                     }
  273.                     else if (curChild < curNode._children.Count) {
  274.                         EmitFragment(curNode._type | BeforeChild, curNode, curChild);
  275.                        
  276.                         curNode = (RegexNode)curNode._children[curChild];
  277.                         PushInt(curChild);
  278.                         curChild = 0;
  279.                         continue;
  280.                     }
  281.                    
  282.                     if (EmptyStack())
  283.                         break;
  284.                    
  285.                     curChild = PopInt();
  286.                     curNode = curNode._next;
  287.                    
  288.                     EmitFragment(curNode._type | AfterChild, curNode, curChild);
  289.                     curChild++;
  290.                 }
  291.                
  292.                 PatchJump(0, CurPos());
  293.                 Emit(RegexCode.Stop);
  294.                
  295.                 if (!_counting)
  296.                     break;
  297.                
  298.                 _counting = false;
  299.             }
  300.            
  301.             fcPrefix = RegexFCD.FirstChars(tree);
  302.            
  303.             prefix = RegexFCD.Prefix(tree);
  304.             rtl = ((tree._options & RegexOptions.RightToLeft) != 0);
  305.            
  306.             CultureInfo culture = (tree._options & RegexOptions.CultureInvariant) != 0 ? CultureInfo.InvariantCulture : CultureInfo.CurrentCulture;
  307.             if (prefix != null && prefix.Prefix.Length > 0)
  308.                 bmPrefix = new RegexBoyerMoore(prefix.Prefix, prefix.CaseInsensitive, rtl, culture);
  309.             else
  310.                 bmPrefix = null;
  311.            
  312.             anchors = RegexFCD.Anchors(tree);
  313.            
  314.             return new RegexCode(_emitted, _stringtable, _trackcount, _caps, capsize, bmPrefix, fcPrefix, anchors, rtl);
  315.         }
  316.        
  317. /*
  318.         * The main RegexCode generator. It does a depth-first walk
  319.         * through the tree and calls EmitFragment to emits code before
  320.         * and after each child of an interior node, and at each leaf.
  321.         */       
  322.         internal void EmitFragment(int nodetype, RegexNode node, int CurIndex)
  323.         {
  324.             int bits = 0;
  325.            
  326.             if (nodetype <= RegexNode.Ref) {
  327.                 if (node.UseOptionR())
  328.                     bits |= RegexCode.Rtl;
  329.                 if ((node._options & RegexOptions.IgnoreCase) != 0)
  330.                     bits |= RegexCode.Ci;
  331.             }
  332.            
  333.             switch (nodetype) {
  334.                 case RegexNode.Concatenate | BeforeChild:
  335.                 case RegexNode.Concatenate | AfterChild:
  336.                 case RegexNode.Empty:
  337.                     break;
  338.                 case RegexNode.Alternate | BeforeChild:
  339.                    
  340.                     if (CurIndex < node._children.Count - 1) {
  341.                         PushInt(CurPos());
  342.                         Emit(RegexCode.Lazybranch, 0);
  343.                     }
  344.                     break;
  345.                 case RegexNode.Alternate | AfterChild:
  346.                    
  347.                    
  348.                     {
  349.                        
  350.                         if (CurIndex < node._children.Count - 1) {
  351.                             int LBPos = PopInt();
  352.                             PushInt(CurPos());
  353.                             Emit(RegexCode.Goto, 0);
  354.                             PatchJump(LBPos, CurPos());
  355.                         }
  356.                         else {
  357.                             int I;
  358.                             for (I = 0; I < CurIndex; I++) {
  359.                                 PatchJump(PopInt(), CurPos());
  360.                             }
  361.                         }
  362.                         break;
  363.                     }
  364.                     break;
  365.                 case RegexNode.Testref | BeforeChild:
  366.                    
  367.                     switch (CurIndex) {
  368.                         case 0:
  369.                             Emit(RegexCode.Setjump);
  370.                             PushInt(CurPos());
  371.                             Emit(RegexCode.Lazybranch, 0);
  372.                             Emit(RegexCode.Testref, MapCapnum(node._m));
  373.                             Emit(RegexCode.Forejump);
  374.                             break;
  375.                     }
  376.                     break;
  377.                 case RegexNode.Testref | AfterChild:
  378.                    
  379.                     switch (CurIndex) {
  380.                         case 0:
  381.                            
  382.                             {
  383.                                 int Branchpos = PopInt();
  384.                                 PushInt(CurPos());
  385.                                 Emit(RegexCode.Goto, 0);
  386.                                 PatchJump(Branchpos, CurPos());
  387.                                 Emit(RegexCode.Forejump);
  388.                                 if (node._children.Count > 1)
  389.                                     break;
  390.                                 // else fallthrough
  391.                                 goto case 1;
  392.                             }
  393.                             break;
  394.                         case 1:
  395.                             PatchJump(PopInt(), CurPos());
  396.                             break;
  397.                     }
  398.                     break;
  399.                 case RegexNode.Testgroup | BeforeChild:
  400.                    
  401.                     switch (CurIndex) {
  402.                         case 0:
  403.                             Emit(RegexCode.Setjump);
  404.                             Emit(RegexCode.Setmark);
  405.                             PushInt(CurPos());
  406.                             Emit(RegexCode.Lazybranch, 0);
  407.                             break;
  408.                     }
  409.                     break;
  410.                 case RegexNode.Testgroup | AfterChild:
  411.                    
  412.                     switch (CurIndex) {
  413.                         case 0:
  414.                             Emit(RegexCode.Getmark);
  415.                             Emit(RegexCode.Forejump);
  416.                             break;
  417.                         case 1:
  418.                             int Branchpos = PopInt();
  419.                             PushInt(CurPos());
  420.                             Emit(RegexCode.Goto, 0);
  421.                             PatchJump(Branchpos, CurPos());
  422.                             Emit(RegexCode.Getmark);
  423.                             Emit(RegexCode.Forejump);
  424.                            
  425.                             if (node._children.Count > 2)
  426.                                 break;
  427.                             // else fallthrough
  428.                             goto case 2;
  429.                             break;
  430.                         case 2:
  431.                             PatchJump(PopInt(), CurPos());
  432.                             break;
  433.                     }
  434.                     break;
  435.                 case RegexNode.Loop | BeforeChild:
  436.                 case RegexNode.Lazyloop | BeforeChild:
  437.                    
  438.                    
  439.                     if (node._n < Int32.MaxValue || node._m > 1)
  440.                         Emit(node._m == 0 ? RegexCode.Nullcount : RegexCode.Setcount, node._m == 0 ? 0 : 1 - node._m);
  441.                     else
  442.                         Emit(node._m == 0 ? RegexCode.Nullmark : RegexCode.Setmark);
  443.                    
  444.                     if (node._m == 0) {
  445.                         PushInt(CurPos());
  446.                         Emit(RegexCode.Goto, 0);
  447.                     }
  448.                     PushInt(CurPos());
  449.                     break;
  450.                 case RegexNode.Loop | AfterChild:
  451.                 case RegexNode.Lazyloop | AfterChild:
  452.                    
  453.                    
  454.                     {
  455.                         int StartJumpPos = CurPos();
  456.                         int Lazy = (nodetype - (RegexNode.Loop | AfterChild));
  457.                        
  458.                         if (node._n < Int32.MaxValue || node._m > 1)
  459.                             Emit(RegexCode.Branchcount + Lazy, PopInt(), node._n == Int32.MaxValue ? Int32.MaxValue : node._n - node._m);
  460.                         else
  461.                             Emit(RegexCode.Branchmark + Lazy, PopInt());
  462.                        
  463.                         if (node._m == 0)
  464.                             PatchJump(PopInt(), StartJumpPos);
  465.                     }
  466.                     break;
  467.                 case RegexNode.Group | BeforeChild:
  468.                 case RegexNode.Group | AfterChild:
  469.                    
  470.                     break;
  471.                 case RegexNode.Capture | BeforeChild:
  472.                    
  473.                     Emit(RegexCode.Setmark);
  474.                     break;
  475.                 case RegexNode.Capture | AfterChild:
  476.                    
  477.                     Emit(RegexCode.Capturemark, MapCapnum(node._m), MapCapnum(node._n));
  478.                     break;
  479.                 case RegexNode.Require | BeforeChild:
  480.                    
  481.                     // NOTE: the following line causes lookahead/lookbehind to be
  482.                     // NON-BACKTRACKING. It can be commented out with (*)
  483.                     Emit(RegexCode.Setjump);
  484.                    
  485.                    
  486.                     Emit(RegexCode.Setmark);
  487.                     break;
  488.                 case RegexNode.Require | AfterChild:
  489.                    
  490.                     Emit(RegexCode.Getmark);
  491.                    
  492.                     // NOTE: the following line causes lookahead/lookbehind to be
  493.                     // NON-BACKTRACKING. It can be commented out with (*)
  494.                     Emit(RegexCode.Forejump);
  495.                    
  496.                     break;
  497.                 case RegexNode.Prevent | BeforeChild:
  498.                    
  499.                     Emit(RegexCode.Setjump);
  500.                     PushInt(CurPos());
  501.                     Emit(RegexCode.Lazybranch, 0);
  502.                     break;
  503.                 case RegexNode.Prevent | AfterChild:
  504.                    
  505.                     Emit(RegexCode.Backjump);
  506.                     PatchJump(PopInt(), CurPos());
  507.                     Emit(RegexCode.Forejump);
  508.                     break;
  509.                 case RegexNode.Greedy | BeforeChild:
  510.                    
  511.                     Emit(RegexCode.Setjump);
  512.                     break;
  513.                 case RegexNode.Greedy | AfterChild:
  514.                    
  515.                     Emit(RegexCode.Forejump);
  516.                     break;
  517.                 case RegexNode.One:
  518.                 case RegexNode.Notone:
  519.                    
  520.                     Emit(node._type | bits, (int)node._ch);
  521.                     break;
  522.                 case RegexNode.Notoneloop:
  523.                 case RegexNode.Notonelazy:
  524.                 case RegexNode.Oneloop:
  525.                 case RegexNode.Onelazy:
  526.                    
  527.                     if (node._m > 0)
  528.                         Emit(((node._type == RegexNode.Oneloop || node._type == RegexNode.Onelazy) ? RegexCode.Onerep : RegexCode.Notonerep) | bits, (int)node._ch, node._m);
  529.                     if (node._n > node._m)
  530.                         Emit(node._type | bits, (int)node._ch, node._n == Int32.MaxValue ? Int32.MaxValue : node._n - node._m);
  531.                     break;
  532.                 case RegexNode.Setloop:
  533.                 case RegexNode.Setlazy:
  534.                    
  535.                     if (node._m > 0)
  536.                         Emit(RegexCode.Setrep | bits, StringCode(node._str), node._m);
  537.                     if (node._n > node._m)
  538.                         Emit(node._type | bits, StringCode(node._str), (node._n == Int32.MaxValue) ? Int32.MaxValue : node._n - node._m);
  539.                     break;
  540.                 case RegexNode.Multi:
  541.                    
  542.                     Emit(node._type | bits, StringCode(node._str));
  543.                     break;
  544.                 case RegexNode.Set:
  545.                    
  546.                     Emit(node._type | bits, StringCode(node._str));
  547.                     break;
  548.                 case RegexNode.Ref:
  549.                    
  550.                     Emit(node._type | bits, MapCapnum(node._m));
  551.                     break;
  552.                 case RegexNode.Nothing:
  553.                 case RegexNode.Bol:
  554.                 case RegexNode.Eol:
  555.                 case RegexNode.Boundary:
  556.                 case RegexNode.Nonboundary:
  557.                 case RegexNode.ECMABoundary:
  558.                 case RegexNode.NonECMABoundary:
  559.                 case RegexNode.Beginning:
  560.                 case RegexNode.Start:
  561.                 case RegexNode.EndZ:
  562.                 case RegexNode.End:
  563.                    
  564.                     Emit(node._type);
  565.                     break;
  566.                 default:
  567.                    
  568.                     throw MakeException(SR.GetString(SR.UnexpectedOpcode, nodetype.ToString(CultureInfo.CurrentCulture)));
  569.                     break;
  570.             }
  571.         }
  572.     }
  573. }

Developer Fusion