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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexCode.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 RegexCode class is internal to the regular expression package.
  16. // It provides operator constants for use by the Builder and the Machine.
  17. // Implementation notes:
  18. //
  19. // Regexps are built into RegexCodes, which contain an operation array,
  20. // a string table, and some constants.
  21. //
  22. // Each operation is one of the codes below, followed by the integer
  23. // operands specified for each op.
  24. //
  25. // Strings and sets are indices into a string table.
  26. namespace System.Text.RegularExpressions
  27. {
  28.    
  29.     using System.Collections;
  30.     using System.Diagnostics;
  31.     using System.Globalization;
  32.    
  33.     internal sealed class RegexCode
  34.     {
  35.         // the following primitive operations come directly from the parser
  36.        
  37.         // lef/back operands description
  38.        
  39.         internal const int Onerep = 0;
  40.         // lef,back char,min,max a {n}
  41.         internal const int Notonerep = 1;
  42.         // lef,back char,min,max .{n}
  43.         internal const int Setrep = 2;
  44.         // lef,back set,min,max [\d]{n}
  45.         internal const int Oneloop = 3;
  46.         // lef,back char,min,max a {,n}
  47.         internal const int Notoneloop = 4;
  48.         // lef,back char,min,max .{,n}
  49.         internal const int Setloop = 5;
  50.         // lef,back set,min,max [\d]{,n}
  51.         internal const int Onelazy = 6;
  52.         // lef,back char,min,max a {,n}?
  53.         internal const int Notonelazy = 7;
  54.         // lef,back char,min,max .{,n}?
  55.         internal const int Setlazy = 8;
  56.         // lef,back set,min,max [\d]{,n}?
  57.         internal const int One = 9;
  58.         // lef char a
  59.         internal const int Notone = 10;
  60.         // lef char [^a]
  61.         internal const int Set = 11;
  62.         // lef set [a-z\s] \w \s \d
  63.         internal const int Multi = 12;
  64.         // lef string abcd
  65.         internal const int Ref = 13;
  66.         // lef group \#
  67.         internal const int Bol = 14;
  68.         // ^
  69.         internal const int Eol = 15;
  70.         // $
  71.         internal const int Boundary = 16;
  72.         // \b
  73.         internal const int Nonboundary = 17;
  74.         // \B
  75.         internal const int Beginning = 18;
  76.         // \A
  77.         internal const int Start = 19;
  78.         // \G
  79.         internal const int EndZ = 20;
  80.         // \Z
  81.         internal const int End = 21;
  82.         // \Z
  83.         internal const int Nothing = 22;
  84.         // Reject!
  85.         // primitive control structures
  86.        
  87.         internal const int Lazybranch = 23;
  88.         // back jump straight first
  89.         internal const int Branchmark = 24;
  90.         // back jump branch first for loop
  91.         internal const int Lazybranchmark = 25;
  92.         // back jump straight first for loop
  93.         internal const int Nullcount = 26;
  94.         // back val set counter, null mark
  95.         internal const int Setcount = 27;
  96.         // back val set counter, make mark
  97.         internal const int Branchcount = 28;
  98.         // back jump,limit branch++ if zero<=c<limit
  99.         internal const int Lazybranchcount = 29;
  100.         // back jump,limit same, but straight first
  101.         internal const int Nullmark = 30;
  102.         // back save position
  103.         internal const int Setmark = 31;
  104.         // back save position
  105.         internal const int Capturemark = 32;
  106.         // back group define group
  107.         internal const int Getmark = 33;
  108.         // back recall position
  109.         internal const int Setjump = 34;
  110.         // back save backtrack state
  111.         internal const int Backjump = 35;
  112.         // zap back to saved state
  113.         internal const int Forejump = 36;
  114.         // zap backtracking state
  115.         internal const int Testref = 37;
  116.         // backtrack if ref undefined
  117.         internal const int Goto = 38;
  118.         // jump just go
  119.         internal const int Prune = 39;
  120.         // prune it baby
  121.         internal const int Stop = 40;
  122.         // done!
  123.         internal const int ECMABoundary = 41;
  124.         // \b
  125.         internal const int NonECMABoundary = 42;
  126.         // \B
  127.         // modifiers for alternate modes
  128.        
  129.         internal const int Mask = 63;
  130.         // Mask to get unmodified ordinary operator
  131.         internal const int Rtl = 64;
  132.         // bit to indicate that we're reverse scanning.
  133.         internal const int Back = 128;
  134.         // bit to indicate that we're backtracking.
  135.         internal const int Back2 = 256;
  136.         // bit to indicate that we're backtracking on a second branch.
  137.         internal const int Ci = 512;
  138.         // bit to indicate that we're case-insensitive.
  139.         // the code
  140.        
  141.         internal int[] _codes;
  142.         // the code
  143.         internal string[] _strings;
  144.         // the string/set table
  145.         // not used! internal int[] _sparseIndex; // a list of the groups that are used
  146.         internal int _trackcount;
  147.         // how many instructions use backtracking
  148.         internal Hashtable _caps;
  149.         // mapping of user group numbers -> impl group slots
  150.         internal int _capsize;
  151.         // number of impl group slots
  152.         internal RegexPrefix _fcPrefix;
  153.         // the set of candidate first characters (may be null)
  154.         internal RegexBoyerMoore _bmPrefix;
  155.         // the fixed prefix string as a Boyer-Moore machine (may be null)
  156.         internal int _anchors;
  157.         // the set of zero-length start anchors (RegexFCD.Bol, etc)
  158.         internal bool _rightToLeft;
  159.         // true if right to left
  160.         // optimizations
  161.        
  162.         // constructor
  163.        
  164.         internal RegexCode(int[] codes, ArrayList stringlist, int trackcount, Hashtable caps, int capsize, RegexBoyerMoore bmPrefix, RegexPrefix fcPrefix, int anchors, bool rightToLeft)
  165.         {
  166.             _codes = codes;
  167.             _strings = new string[stringlist.Count];
  168.             _trackcount = trackcount;
  169.             _caps = caps;
  170.             _capsize = capsize;
  171.             _bmPrefix = bmPrefix;
  172.             _fcPrefix = fcPrefix;
  173.             _anchors = anchors;
  174.             _rightToLeft = rightToLeft;
  175.             stringlist.CopyTo(0, _strings, 0, stringlist.Count);
  176.         }
  177.        
  178.         static internal bool OpcodeBacktracks(int Op)
  179.         {
  180.             Op &= Mask;
  181.            
  182.             switch (Op) {
  183.                 case Oneloop:
  184.                 case Notoneloop:
  185.                 case Setloop:
  186.                 case Onelazy:
  187.                 case Notonelazy:
  188.                 case Setlazy:
  189.                 case Lazybranch:
  190.                 case Branchmark:
  191.                 case Lazybranchmark:
  192.                 case Nullcount:
  193.                 case Setcount:
  194.                 case Branchcount:
  195.                 case Lazybranchcount:
  196.                 case Setmark:
  197.                 case Capturemark:
  198.                 case Getmark:
  199.                 case Setjump:
  200.                 case Backjump:
  201.                 case Forejump:
  202.                 case Goto:
  203.                     return true;
  204.                 default:
  205.                    
  206.                     return false;
  207.             }
  208.         }
  209.        
  210.         static internal int OpcodeSize(int Opcode)
  211.         {
  212.             Opcode &= Mask;
  213.            
  214.             switch (Opcode) {
  215.                 case Nothing:
  216.                 case Bol:
  217.                 case Eol:
  218.                 case Boundary:
  219.                 case Nonboundary:
  220.                 case ECMABoundary:
  221.                 case NonECMABoundary:
  222.                 case Beginning:
  223.                 case Start:
  224.                 case EndZ:
  225.                 case End:
  226.                 case Nullmark:
  227.                 case Setmark:
  228.                 case Getmark:
  229.                 case Setjump:
  230.                 case Backjump:
  231.                 case Forejump:
  232.                 case Stop:
  233.                    
  234.                    
  235.                     return 1;
  236.                 case One:
  237.                 case Notone:
  238.                 case Multi:
  239.                 case Ref:
  240.                 case Testref:
  241.                 case Goto:
  242.                 case Nullcount:
  243.                 case Setcount:
  244.                 case Lazybranch:
  245.                 case Branchmark:
  246.                 case Lazybranchmark:
  247.                 case Prune:
  248.                 case Set:
  249.                    
  250.                    
  251.                    
  252.                    
  253.                     return 2;
  254.                 case Capturemark:
  255.                 case Branchcount:
  256.                 case Lazybranchcount:
  257.                 case Onerep:
  258.                 case Notonerep:
  259.                 case Oneloop:
  260.                 case Notoneloop:
  261.                 case Onelazy:
  262.                 case Notonelazy:
  263.                 case Setlazy:
  264.                 case Setrep:
  265.                 case Setloop:
  266.                    
  267.                    
  268.                    
  269.                     return 3;
  270.                 default:
  271.                    
  272.                    
  273.                     throw MakeException(SR.GetString(SR.UnexpectedOpcode, Opcode.ToString(CultureInfo.CurrentCulture)));
  274.                     break;
  275.             }
  276.         }
  277.        
  278.         static internal ArgumentException MakeException(string message)
  279.         {
  280.             return new ArgumentException(message);
  281.         }
  282.        
  283.         // Debug only code below
  284.        
  285.         #if DBG
  286.         static internal string[] CodeStr = new string[] {"Onerep", "Notonerep", "Setrep", "Oneloop", "Notoneloop", "Setloop", "Onelazy", "Notonelazy", "Setlazy", "One",
  287.         "Notone", "Set", "Multi", "Ref", "Bol", "Eol", "Boundary", "Nonboundary", "Beginning", "Start",
  288.         "EndZ", "End", "Nothing", "Lazybranch", "Branchmark", "Lazybranchmark", "Nullcount", "Setcount", "Branchcount", "Lazybranchcount",
  289.         "Nullmark", "Setmark", "Capturemark", "Getmark", "Setjump", "Backjump", "Forejump", "Testref", "Goto", "Prune",
  290.         "Stop", "ECMABoundary", "NonECMABoundary"};
  291.        
  292.         static internal string OperatorDescription(int Opcode)
  293.         {
  294.             bool isCi = ((Opcode & Ci) != 0);
  295.             bool isRtl = ((Opcode & Rtl) != 0);
  296.             bool isBack = ((Opcode & Back) != 0);
  297.             bool isBack2 = ((Opcode & Back2) != 0);
  298.            
  299.             return CodeStr[Opcode & Mask] + (isCi ? "-Ci" : "") + (isRtl ? "-Rtl" : "") + (isBack ? "-Back" : "") + (isBack2 ? "-Back2" : "");
  300.         }
  301.        
  302.         internal string OpcodeDescription(int offset)
  303.         {
  304.             StringBuilder sb = new StringBuilder();
  305.             int opcode = _codes[offset];
  306.            
  307.             sb.AppendFormat("{0:D6} ", offset);
  308.             sb.Append(OpcodeBacktracks(opcode & Mask) ? '*' : ' ');
  309.             sb.Append(OperatorDescription(opcode));
  310.             sb.Append('(');
  311.            
  312.             opcode &= Mask;
  313.            
  314.             switch (opcode) {
  315.                 case One:
  316.                 case Notone:
  317.                 case Onerep:
  318.                 case Notonerep:
  319.                 case Oneloop:
  320.                 case Notoneloop:
  321.                 case Onelazy:
  322.                 case Notonelazy:
  323.                     sb.Append("Ch = ");
  324.                     sb.Append(RegexCharClass.CharDescription((char)_codes[offset + 1]));
  325.                     break;
  326.                 case Set:
  327.                 case Setrep:
  328.                 case Setloop:
  329.                 case Setlazy:
  330.                    
  331.                     sb.Append("Set = ");
  332.                     sb.Append(RegexCharClass.SetDescription(_strings[_codes[offset + 1]]));
  333.                     break;
  334.                 case Multi:
  335.                    
  336.                     sb.Append("String = ");
  337.                     sb.Append(_strings[_codes[offset + 1]]);
  338.                     break;
  339.                 case Ref:
  340.                 case Testref:
  341.                    
  342.                     sb.Append("Index = ");
  343.                     sb.Append(_codes[offset + 1]);
  344.                     break;
  345.                 case Capturemark:
  346.                    
  347.                     sb.Append("Index = ");
  348.                     sb.Append(_codes[offset + 1]);
  349.                     if (_codes[offset + 2] != -1) {
  350.                         sb.Append(", Unindex = ");
  351.                         sb.Append(_codes[offset + 2]);
  352.                     }
  353.                     break;
  354.                 case Nullcount:
  355.                 case Setcount:
  356.                    
  357.                     sb.Append("Value = ");
  358.                     sb.Append(_codes[offset + 1]);
  359.                     break;
  360.                 case Goto:
  361.                 case Lazybranch:
  362.                 case Branchmark:
  363.                 case Lazybranchmark:
  364.                 case Branchcount:
  365.                 case Lazybranchcount:
  366.                    
  367.                     sb.Append("Addr = ");
  368.                     sb.Append(_codes[offset + 1]);
  369.                     break;
  370.             }
  371.            
  372.             switch (opcode) {
  373.                 case Onerep:
  374.                 case Notonerep:
  375.                 case Oneloop:
  376.                 case Notoneloop:
  377.                 case Onelazy:
  378.                 case Notonelazy:
  379.                 case Setrep:
  380.                 case Setloop:
  381.                 case Setlazy:
  382.                     sb.Append(", Rep = ");
  383.                     if (_codes[offset + 2] == Int32.MaxValue)
  384.                         sb.Append("inf");
  385.                     else
  386.                         sb.Append(_codes[offset + 2]);
  387.                     break;
  388.                 case Branchcount:
  389.                 case Lazybranchcount:
  390.                    
  391.                     sb.Append(", Limit = ");
  392.                     if (_codes[offset + 2] == Int32.MaxValue)
  393.                         sb.Append("inf");
  394.                     else
  395.                         sb.Append(_codes[offset + 2]);
  396.                     break;
  397.             }
  398.            
  399.             sb.Append(")");
  400.            
  401.             return sb.ToString();
  402.         }
  403.        
  404.         internal void Dump()
  405.         {
  406.             int i;
  407.            
  408.             Debug.WriteLine("Direction: " + (_rightToLeft ? "right-to-left" : "left-to-right"));
  409.             Debug.WriteLine("Firstchars: " + (_fcPrefix == null ? "n/a" : RegexCharClass.SetDescription(_fcPrefix.Prefix)));
  410.             Debug.WriteLine("Prefix: " + (_bmPrefix == null ? "n/a" : Regex.Escape(_bmPrefix.ToString())));
  411.             Debug.WriteLine("Anchors: " + RegexFCD.AnchorDescription(_anchors));
  412.             Debug.WriteLine("");
  413.             if (_bmPrefix != null) {
  414.                 Debug.WriteLine("BoyerMoore:");
  415.                 Debug.WriteLine(_bmPrefix.Dump(" "));
  416.             }
  417.             for (i = 0; i < _codes.Length;) {
  418.                 Debug.WriteLine(OpcodeDescription(i));
  419.                 i += OpcodeSize(_codes[i]);
  420.             }
  421.            
  422.             Debug.WriteLine("");
  423.         }
  424.         #endif
  425.        
  426.     }
  427. }

Developer Fusion