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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexFCD.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 RegexFCD class is internal to the Regex package.
  16. // It builds a bunch of FC information (RegexFC) about
  17. // the regex for optimization purposes.
  18. // Implementation notes:
  19. //
  20. // This step is as simple as walking the tree and emitting
  21. // sequences of codes.
  22. namespace System.Text.RegularExpressions
  23. {
  24.    
  25.     using System.Collections;
  26.     using System.Globalization;
  27.    
  28.     internal sealed class RegexFCD
  29.     {
  30.         private int[] _intStack;
  31.         private int _intDepth;
  32.         private RegexFC[] _fcStack;
  33.         private int _fcDepth;
  34.         private bool _skipAllChildren;
  35.         // don't process any more children at the current level
  36.         private bool _skipchild;
  37.         // don't process the current child.
  38.         private bool _failed = false;
  39.        
  40.         private const int BeforeChild = 64;
  41.         private const int AfterChild = 128;
  42.        
  43.         // where the regex can be pegged
  44.        
  45.         internal const int Beginning = 1;
  46.         internal const int Bol = 2;
  47.         internal const int Start = 4;
  48.         internal const int Eol = 8;
  49.         internal const int EndZ = 16;
  50.         internal const int End = 32;
  51.         internal const int Boundary = 64;
  52.         internal const int ECMABoundary = 128;
  53.        
  54. /*
  55.         * This is the one of the only two functions that should be called from outside.
  56.         * It takes a RegexTree and computes the set of chars that can start it.
  57.         */       
  58.         static internal RegexPrefix FirstChars(RegexTree t)
  59.         {
  60.             RegexFCD s = new RegexFCD();
  61.             RegexFC fc = s.RegexFCFromRegexTree(t);
  62.            
  63.             if (fc == null || fc._nullable)
  64.                 return null;
  65.            
  66.             CultureInfo culture = ((t._options & RegexOptions.CultureInvariant) != 0) ? CultureInfo.InvariantCulture : CultureInfo.CurrentCulture;
  67.             return new RegexPrefix(fc.GetFirstChars(culture), fc.IsCaseInsensitive());
  68.         }
  69.        
  70. /*
  71.         * This is a related computation: it takes a RegexTree and computes the
  72.         * leading substring if it see one. It's quite trivial and gives up easily.
  73.         */       
  74.         static internal RegexPrefix Prefix(RegexTree tree)
  75.         {
  76.             RegexNode curNode;
  77.             RegexNode concatNode = null;
  78.             int nextChild = 0;
  79.            
  80.             curNode = tree._root;
  81.            
  82.             for (;;) {
  83.                 switch (curNode._type) {
  84.                     case RegexNode.Concatenate:
  85.                         if (curNode.ChildCount() > 0) {
  86.                             concatNode = curNode;
  87.                             nextChild = 0;
  88.                         }
  89.                         break;
  90.                     case RegexNode.Greedy:
  91.                     case RegexNode.Capture:
  92.                        
  93.                         curNode = curNode.Child(0);
  94.                         concatNode = null;
  95.                         continue;
  96.                     case RegexNode.Oneloop:
  97.                     case RegexNode.Onelazy:
  98.                        
  99.                         if (curNode._m > 0) {
  100.                             string pref = String.Empty.PadRight(curNode._m, curNode._ch);
  101.                             return new RegexPrefix(pref, 0 != (curNode._options & RegexOptions.IgnoreCase));
  102.                         }
  103.                         else
  104.                             return RegexPrefix.Empty;
  105.                         break;
  106.                     case RegexNode.One:
  107.                        
  108.                         return new RegexPrefix(curNode._ch.ToString(CultureInfo.InvariantCulture), 0 != (curNode._options & RegexOptions.IgnoreCase));
  109.                     case RegexNode.Multi:
  110.                        
  111.                         return new RegexPrefix(curNode._str, 0 != (curNode._options & RegexOptions.IgnoreCase));
  112.                     case RegexNode.Bol:
  113.                     case RegexNode.Eol:
  114.                     case RegexNode.Boundary:
  115.                     case RegexNode.ECMABoundary:
  116.                     case RegexNode.Beginning:
  117.                     case RegexNode.Start:
  118.                     case RegexNode.EndZ:
  119.                     case RegexNode.End:
  120.                     case RegexNode.Empty:
  121.                     case RegexNode.Require:
  122.                     case RegexNode.Prevent:
  123.                        
  124.                         break;
  125.                     default:
  126.                        
  127.                         return RegexPrefix.Empty;
  128.                 }
  129.                
  130.                 if (concatNode == null || nextChild >= concatNode.ChildCount())
  131.                     return RegexPrefix.Empty;
  132.                
  133.                 curNode = concatNode.Child(nextChild++);
  134.             }
  135.         }
  136.        
  137. /*
  138.         * Yet another related computation: it takes a RegexTree and computes the
  139.         * leading anchors that it encounters.
  140.         */       
  141.         static internal int Anchors(RegexTree tree)
  142.         {
  143.             RegexNode curNode;
  144.             RegexNode concatNode = null;
  145.             int nextChild = 0;
  146.             int result = 0;
  147.            
  148.             curNode = tree._root;
  149.            
  150.             for (;;) {
  151.                 switch (curNode._type) {
  152.                     case RegexNode.Concatenate:
  153.                         if (curNode.ChildCount() > 0) {
  154.                             concatNode = curNode;
  155.                             nextChild = 0;
  156.                         }
  157.                         break;
  158.                     case RegexNode.Greedy:
  159.                     case RegexNode.Capture:
  160.                        
  161.                         curNode = curNode.Child(0);
  162.                         concatNode = null;
  163.                         continue;
  164.                     case RegexNode.Bol:
  165.                     case RegexNode.Eol:
  166.                     case RegexNode.Boundary:
  167.                     case RegexNode.ECMABoundary:
  168.                     case RegexNode.Beginning:
  169.                     case RegexNode.Start:
  170.                     case RegexNode.EndZ:
  171.                     case RegexNode.End:
  172.                        
  173.                         return result | AnchorFromType(curNode._type);
  174.                     case RegexNode.Empty:
  175.                     case RegexNode.Require:
  176.                     case RegexNode.Prevent:
  177.                        
  178.                         break;
  179.                     default:
  180.                        
  181.                         return result;
  182.                 }
  183.                
  184.                 if (concatNode == null || nextChild >= concatNode.ChildCount())
  185.                     return result;
  186.                
  187.                 curNode = concatNode.Child(nextChild++);
  188.             }
  189.         }
  190.        
  191. /*
  192.         * Convert anchor type to anchor bit.
  193.         */       
  194.         private static int AnchorFromType(int type)
  195.         {
  196.             switch (type) {
  197.                 case RegexNode.Bol:
  198.                     return Bol;
  199.                 case RegexNode.Eol:
  200.                     return Eol;
  201.                 case RegexNode.Boundary:
  202.                     return Boundary;
  203.                 case RegexNode.ECMABoundary:
  204.                     return ECMABoundary;
  205.                 case RegexNode.Beginning:
  206.                     return Beginning;
  207.                 case RegexNode.Start:
  208.                     return Start;
  209.                 case RegexNode.EndZ:
  210.                     return EndZ;
  211.                 case RegexNode.End:
  212.                     return End;
  213.                 default:
  214.                     return 0;
  215.             }
  216.         }
  217.        
  218.         #if DBG
  219.         static internal string AnchorDescription(int anchors)
  220.         {
  221.             StringBuilder sb = new StringBuilder();
  222.            
  223.             if (0 != (anchors & Beginning))
  224.                 sb.Append(", Beginning");
  225.             if (0 != (anchors & Start))
  226.                 sb.Append(", Start");
  227.             if (0 != (anchors & Bol))
  228.                 sb.Append(", Bol");
  229.             if (0 != (anchors & Boundary))
  230.                 sb.Append(", Boundary");
  231.             if (0 != (anchors & ECMABoundary))
  232.                 sb.Append(", ECMABoundary");
  233.             if (0 != (anchors & Eol))
  234.                 sb.Append(", Eol");
  235.             if (0 != (anchors & End))
  236.                 sb.Append(", End");
  237.             if (0 != (anchors & EndZ))
  238.                 sb.Append(", EndZ");
  239.            
  240.             if (sb.Length >= 2)
  241.                 return (sb.ToString(2, sb.Length - 2));
  242.            
  243.             return "None";
  244.         }
  245.         #endif
  246.        
  247. /*
  248.         * private constructor; can't be created outside
  249.         */       
  250.         private RegexFCD()
  251.         {
  252.             _fcStack = new RegexFC[32];
  253.             _intStack = new int[32];
  254.         }
  255.        
  256. /*
  257.         * To avoid recursion, we use a simple integer stack.
  258.         * This is the push.
  259.         */       
  260.         private void PushInt(int I)
  261.         {
  262.             if (_intDepth >= _intStack.Length) {
  263.                 int[] expanded = new int[_intDepth * 2];
  264.                
  265.                 System.Array.Copy(_intStack, 0, expanded, 0, _intDepth);
  266.                
  267.                 _intStack = expanded;
  268.             }
  269.            
  270.             _intStack[_intDepth++] = I;
  271.         }
  272.        
  273. /*
  274.         * True if the stack is empty.
  275.         */       
  276.         private bool IntIsEmpty()
  277.         {
  278.             return _intDepth == 0;
  279.         }
  280.        
  281. /*
  282.         * This is the pop.
  283.         */       
  284.         private int PopInt()
  285.         {
  286.             return _intStack[--_intDepth];
  287.         }
  288.        
  289. /*
  290.           * We also use a stack of RegexFC objects.
  291.           * This is the push.
  292.           */       
  293.         private void PushFC(RegexFC fc)
  294.         {
  295.             if (_fcDepth >= _fcStack.Length) {
  296.                 RegexFC[] expanded = new RegexFC[_fcDepth * 2];
  297.                
  298.                 System.Array.Copy(_fcStack, 0, expanded, 0, _fcDepth);
  299.                 _fcStack = expanded;
  300.             }
  301.            
  302.             _fcStack[_fcDepth++] = fc;
  303.         }
  304.        
  305. /*
  306.         * True if the stack is empty.
  307.         */       
  308.         private bool FCIsEmpty()
  309.         {
  310.             return _fcDepth == 0;
  311.         }
  312.        
  313. /*
  314.         * This is the pop.
  315.         */       
  316.         private RegexFC PopFC()
  317.         {
  318.             return _fcStack[--_fcDepth];
  319.         }
  320.        
  321. /*
  322.         * This is the top.
  323.         */       
  324.         private RegexFC TopFC()
  325.         {
  326.             return _fcStack[_fcDepth - 1];
  327.         }
  328.        
  329. /*
  330.         * The main FC computation. It does a shortcutted depth-first walk
  331.         * through the tree and calls CalculateFC to emits code before
  332.         * and after each child of an interior node, and at each leaf.
  333.         */       
  334.         private RegexFC RegexFCFromRegexTree(RegexTree tree)
  335.         {
  336.             RegexNode curNode;
  337.             int curChild;
  338.            
  339.             curNode = tree._root;
  340.             curChild = 0;
  341.            
  342.             for (;;) {
  343.                 if (curNode._children == null) {
  344.                     // This is a leaf node
  345.                     CalculateFC(curNode._type, curNode, 0);
  346.                 }
  347.                 else if (curChild < curNode._children.Count && !_skipAllChildren) {
  348.                     // This is an interior node, and we have more children to analyze
  349.                     CalculateFC(curNode._type | BeforeChild, curNode, curChild);
  350.                    
  351.                     if (!_skipchild) {
  352.                         curNode = (RegexNode)curNode._children[curChild];
  353.                         // this stack is how we get a depth first walk of the tree.
  354.                         PushInt(curChild);
  355.                         curChild = 0;
  356.                     }
  357.                     else {
  358.                         curChild++;
  359.                         _skipchild = false;
  360.                     }
  361.                     continue;
  362.                 }
  363.                
  364.                 // This is an interior node where we've finished analyzing all the children, or
  365.                 // the end of a leaf node.
  366.                 _skipAllChildren = false;
  367.                
  368.                 if (IntIsEmpty())
  369.                     break;
  370.                
  371.                 curChild = PopInt();
  372.                 curNode = curNode._next;
  373.                
  374.                 CalculateFC(curNode._type | AfterChild, curNode, curChild);
  375.                 if (_failed)
  376.                     return null;
  377.                
  378.                 curChild++;
  379.             }
  380.            
  381.             if (FCIsEmpty())
  382.                 return null;
  383.            
  384.             return PopFC();
  385.         }
  386.        
  387. /*
  388.         * Called in Beforechild to prevent further processing of the current child
  389.         */       
  390.         private void SkipChild()
  391.         {
  392.             _skipchild = true;
  393.         }
  394.        
  395. /*
  396.         * FC computation and shortcut cases for each node type
  397.         */       
  398.         private void CalculateFC(int NodeType, RegexNode node, int CurIndex)
  399.         {
  400.             bool ci = false;
  401.             bool rtl = false;
  402.            
  403.             if (NodeType <= RegexNode.Ref) {
  404.                 if ((node._options & RegexOptions.IgnoreCase) != 0)
  405.                     ci = true;
  406.                 if ((node._options & RegexOptions.RightToLeft) != 0)
  407.                     rtl = true;
  408.             }
  409.            
  410.             switch (NodeType) {
  411.                 case RegexNode.Concatenate | BeforeChild:
  412.                 case RegexNode.Alternate | BeforeChild:
  413.                 case RegexNode.Testref | BeforeChild:
  414.                 case RegexNode.Loop | BeforeChild:
  415.                 case RegexNode.Lazyloop | BeforeChild:
  416.                     break;
  417.                 case RegexNode.Testgroup | BeforeChild:
  418.                    
  419.                     if (CurIndex == 0)
  420.                         SkipChild();
  421.                     break;
  422.                 case RegexNode.Empty:
  423.                    
  424.                     PushFC(new RegexFC(true));
  425.                     break;
  426.                 case RegexNode.Concatenate | AfterChild:
  427.                    
  428.                     if (CurIndex != 0) {
  429.                         RegexFC child = PopFC();
  430.                         RegexFC cumul = TopFC();
  431.                        
  432.                         _failed = !cumul.AddFC(child, true);
  433.                     }
  434.                    
  435.                     if (!TopFC()._nullable)
  436.                         _skipAllChildren = true;
  437.                     break;
  438.                 case RegexNode.Testgroup | AfterChild:
  439.                    
  440.                     if (CurIndex > 1) {
  441.                         RegexFC child = PopFC();
  442.                         RegexFC cumul = TopFC();
  443.                        
  444.                         _failed = !cumul.AddFC(child, false);
  445.                     }
  446.                     break;
  447.                 case RegexNode.Alternate | AfterChild:
  448.                 case RegexNode.Testref | AfterChild:
  449.                    
  450.                     if (CurIndex != 0) {
  451.                         RegexFC child = PopFC();
  452.                         RegexFC cumul = TopFC();
  453.                        
  454.                         _failed = !cumul.AddFC(child, false);
  455.                     }
  456.                     break;
  457.                 case RegexNode.Loop | AfterChild:
  458.                 case RegexNode.Lazyloop | AfterChild:
  459.                    
  460.                     if (node._m == 0)
  461.                         TopFC()._nullable = true;
  462.                     break;
  463.                 case RegexNode.Group | BeforeChild:
  464.                 case RegexNode.Group | AfterChild:
  465.                 case RegexNode.Capture | BeforeChild:
  466.                 case RegexNode.Capture | AfterChild:
  467.                 case RegexNode.Greedy | BeforeChild:
  468.                 case RegexNode.Greedy | AfterChild:
  469.                    
  470.                     break;
  471.                 case RegexNode.Require | BeforeChild:
  472.                 case RegexNode.Prevent | BeforeChild:
  473.                    
  474.                     SkipChild();
  475.                     PushFC(new RegexFC(true));
  476.                     break;
  477.                 case RegexNode.Require | AfterChild:
  478.                 case RegexNode.Prevent | AfterChild:
  479.                    
  480.                     break;
  481.                 case RegexNode.One:
  482.                 case RegexNode.Notone:
  483.                    
  484.                     PushFC(new RegexFC(node._ch, NodeType == RegexNode.Notone, false, ci));
  485.                     break;
  486.                 case RegexNode.Oneloop:
  487.                 case RegexNode.Onelazy:
  488.                    
  489.                     PushFC(new RegexFC(node._ch, false, node._m == 0, ci));
  490.                     break;
  491.                 case RegexNode.Notoneloop:
  492.                 case RegexNode.Notonelazy:
  493.                    
  494.                     PushFC(new RegexFC(node._ch, true, node._m == 0, ci));
  495.                     break;
  496.                 case RegexNode.Multi:
  497.                    
  498.                     if (node._str.Length == 0)
  499.                         PushFC(new RegexFC(true));
  500.                     else if (!rtl)
  501.                         PushFC(new RegexFC(node._str[0], false, false, ci));
  502.                     else
  503.                         PushFC(new RegexFC(node._str[node._str.Length - 1], false, false, ci));
  504.                     break;
  505.                 case RegexNode.Set:
  506.                    
  507.                     PushFC(new RegexFC(node._str, false, ci));
  508.                     break;
  509.                 case RegexNode.Setloop:
  510.                 case RegexNode.Setlazy:
  511.                    
  512.                     PushFC(new RegexFC(node._str, node._m == 0, ci));
  513.                     break;
  514.                 case RegexNode.Ref:
  515.                    
  516.                     PushFC(new RegexFC(RegexCharClass.AnyClass, true, false));
  517.                     break;
  518.                 case RegexNode.Nothing:
  519.                 case RegexNode.Bol:
  520.                 case RegexNode.Eol:
  521.                 case RegexNode.Boundary:
  522.                 case RegexNode.Nonboundary:
  523.                 case RegexNode.ECMABoundary:
  524.                 case RegexNode.NonECMABoundary:
  525.                 case RegexNode.Beginning:
  526.                 case RegexNode.Start:
  527.                 case RegexNode.EndZ:
  528.                 case RegexNode.End:
  529.                    
  530.                     PushFC(new RegexFC(true));
  531.                     break;
  532.                 default:
  533.                    
  534.                     throw new ArgumentException(SR.GetString(SR.UnexpectedOpcode, NodeType.ToString(CultureInfo.CurrentCulture)));
  535.                     break;
  536.             }
  537.         }
  538.     }
  539.    
  540.     internal sealed class RegexFC
  541.     {
  542.         internal RegexCharClass _cc;
  543.         internal bool _nullable;
  544.         internal bool _caseInsensitive;
  545.        
  546.         internal RegexFC(bool nullable)
  547.         {
  548.             _cc = new RegexCharClass();
  549.             _nullable = nullable;
  550.         }
  551.        
  552.         internal RegexFC(char ch, bool not, bool nullable, bool caseInsensitive)
  553.         {
  554.             _cc = new RegexCharClass();
  555.            
  556.             if (not) {
  557.                 if (ch > 0)
  558.                     _cc.AddRange('\0', (char)(ch - 1));
  559.                 if (ch < 65535)
  560.                     _cc.AddRange((char)(ch + 1), '￿');
  561.             }
  562.             else {
  563.                 _cc.AddRange(ch, ch);
  564.             }
  565.            
  566.             _caseInsensitive = caseInsensitive;
  567.             _nullable = nullable;
  568.         }
  569.        
  570.         internal RegexFC(string charClass, bool nullable, bool caseInsensitive)
  571.         {
  572.             _cc = RegexCharClass.Parse(charClass);
  573.            
  574.             _nullable = nullable;
  575.             _caseInsensitive = caseInsensitive;
  576.         }
  577.        
  578.         internal bool AddFC(RegexFC fc, bool concatenate)
  579.         {
  580.             if (!_cc.CanMerge || !fc._cc.CanMerge) {
  581.                 return false;
  582.             }
  583.            
  584.             if (concatenate) {
  585.                 if (!_nullable)
  586.                     return true;
  587.                
  588.                 if (!fc._nullable)
  589.                     _nullable = false;
  590.             }
  591.             else {
  592.                 if (fc._nullable)
  593.                     _nullable = true;
  594.             }
  595.            
  596.             _caseInsensitive |= fc._caseInsensitive;
  597.             _cc.AddCharClass(fc._cc);
  598.             return true;
  599.         }
  600.        
  601.         internal string GetFirstChars(CultureInfo culture)
  602.         {
  603.             if (_caseInsensitive)
  604.                 _cc.AddLowercase(culture);
  605.            
  606.             return _cc.ToStringClass();
  607.         }
  608.        
  609.         internal bool IsCaseInsensitive()
  610.         {
  611.             return _caseInsensitive;
  612.         }
  613.     }
  614.    
  615.     internal sealed class RegexPrefix
  616.     {
  617.         internal string _prefix;
  618.         internal bool _caseInsensitive;
  619.        
  620.         static internal RegexPrefix _empty = new RegexPrefix(String.Empty, false);
  621.        
  622.         internal RegexPrefix(string prefix, bool ci)
  623.         {
  624.             _prefix = prefix;
  625.             _caseInsensitive = ci;
  626.         }
  627.        
  628.         internal string Prefix {
  629.             get { return _prefix; }
  630.         }
  631.        
  632.         internal bool CaseInsensitive {
  633.             get { return _caseInsensitive; }
  634.         }
  635.         static internal RegexPrefix Empty {
  636.             get { return _empty; }
  637.         }
  638.     }
  639. }

Developer Fusion