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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexBoyerMoore.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. // The RegexBoyerMoore object precomputes the Boyer-Moore
  16. // tables for fast string scanning. These tables allow
  17. // you to scan for the first occurance of a string within
  18. // a large body of text without examining every character.
  19. // The performance of the heuristic depends on the actual
  20. // string and the text being searched, but usually, the longer
  21. // the string that is being searched for, the fewer characters
  22. // need to be examined.
  23. namespace System.Text.RegularExpressions
  24. {
  25.    
  26.     using System.Collections;
  27.     using System.Diagnostics;
  28.     using System.Globalization;
  29.    
  30.     internal sealed class RegexBoyerMoore
  31.     {
  32.         internal int[] _positive;
  33.         internal int[] _negativeASCII;
  34.         internal int[][] _negativeUnicode;
  35.         internal string _pattern;
  36.         internal int _lowASCII;
  37.         internal int _highASCII;
  38.         internal bool _rightToLeft;
  39.         internal bool _caseInsensitive;
  40.         internal CultureInfo _culture;
  41.        
  42.         internal const int infinite = 2147483647;
  43.        
  44. /*
  45.         * Constructs a Boyer-Moore state machine for searching for the string
  46.         * pattern. The string must not be zero-length.
  47.         */       
  48.         internal RegexBoyerMoore(string pattern, bool caseInsensitive, bool rightToLeft, CultureInfo culture)
  49.         {
  50.             /*
  51.             * Sorry,  you just can't use Boyer-Moore to find an empty pattern.
  52.             * We're doing this for your own protection. (Really, for speed.)
  53.             */           
  54. Debug.Assert(pattern.Length != 0, "RegexBoyerMoore called with an empty string. This is bad for perf");
  55.            
  56.             int beforefirst;
  57.             int last;
  58.             int bump;
  59.             int examine;
  60.             int scan;
  61.             int match;
  62.             char ch;
  63.            
  64.             // We do the ToLower character by character for consistency. With surrogate chars, doing
  65.             // a ToLower on the entire string could actually change the surrogate pair. This is more correct
  66.             // linguistically, but since Regex doesn't support surrogates, it's more important to be
  67.             // consistent.
  68.             if (caseInsensitive) {
  69.                 StringBuilder sb = new StringBuilder(pattern.Length);
  70.                 for (int i = 0; i < pattern.Length; i++)
  71.                     sb.Append(Char.ToLower(pattern[i], culture));
  72.                 pattern = sb.ToString();
  73.             }
  74.            
  75.             _pattern = pattern;
  76.             _rightToLeft = rightToLeft;
  77.             _caseInsensitive = caseInsensitive;
  78.             _culture = culture;
  79.            
  80.             if (!rightToLeft) {
  81.                 beforefirst = -1;
  82.                 last = pattern.Length - 1;
  83.                 bump = 1;
  84.             }
  85.             else {
  86.                 beforefirst = pattern.Length;
  87.                 last = 0;
  88.                 bump = -1;
  89.             }
  90.            
  91.             /*
  92.             * PART I - the good-suffix shift table
  93.             *
  94.             * compute the positive requirement:
  95.             * if char "i" is the first one from the right that doesn't match,
  96.             * then we know the matcher can advance by _positive[i].
  97.             *
  98.             *                                                                 
  99.             * <CONSIDER>Maybe someday rewrite this with the real Boyer-Moore algorithm and split it
  100.             *          out into a separate piece of code in the BCL.
  101.             * </CONSIDER>
  102.             */           
  103. _positive = new int[pattern.Length];
  104.            
  105.             examine = last;
  106.             ch = pattern[examine];
  107.             _positive[examine] = bump;
  108.             examine -= bump;
  109.            
  110.             for (;;) {
  111.                 // find an internal char (examine) that matches the tail
  112.                
  113.                 for (;;) {
  114.                     if (examine == beforefirst)
  115.                         goto OuterloopBreak;
  116.                     if (pattern[examine] == ch)
  117.                         break;
  118.                     examine -= bump;
  119.                 }
  120.                
  121.                 match = last;
  122.                 scan = examine;
  123.                
  124.                 // find the length of the match
  125.                
  126.                 for (;;) {
  127.                     if (scan == beforefirst || pattern[match] != pattern[scan]) {
  128.                         // at the end of the match, note the difference in _positive
  129.                         // this is not the length of the match, but the distance from the internal match
  130.                         // to the tail suffix.
  131.                         if (_positive[match] == 0)
  132.                             _positive[match] = match - scan;
  133.                        
  134.                         // System.Diagnostics.Debug.WriteLine("Set positive[" + match + "] to " + (match - scan));
  135.                        
  136.                         break;
  137.                     }
  138.                    
  139.                     scan -= bump;
  140.                     match -= bump;
  141.                 }
  142.                
  143.                 examine -= bump;
  144.             }
  145.             OuterloopBreak:
  146.            
  147.            
  148.             match = last - bump;
  149.            
  150.             // scan for the chars for which there are no shifts that yield a different candidate
  151.            
  152.             /*       
  153.             */           
  154. while (match != beforefirst) {
  155.                 if (_positive[match] == 0)
  156.                     _positive[match] = bump;
  157.                
  158.                 match -= bump;
  159.             }
  160.            
  161.             //System.Diagnostics.Debug.WriteLine("good suffix shift table:");
  162.             //for (int i=0; i<_positive.Length; i++)
  163.             // System.Diagnostics.Debug.WriteLine("\t_positive[" + i + "] = " + _positive[i]);
  164.            
  165.            
  166.             /*
  167.             * PART II - the bad-character shift table
  168.             *
  169.             * compute the negative requirement:
  170.             * if char "ch" is the reject character when testing position "i",
  171.             * we can slide up by _negative[ch];
  172.             * (_negative[ch] = str.Length - 1 - str.LastIndexOf(ch))
  173.             *
  174.             * the lookup table is divided into ASCII and Unicode portions;
  175.             * only those parts of the Unicode 16-bit code set that actually
  176.             * appear in the string are in the table. (Maximum size with
  177.             * Unicode is 65K; ASCII only case is 512 bytes.)
  178.             */           
  179.            
  180. _negativeASCII = new int[128];
  181.            
  182.             for (int i = 0; i < 128; i++)
  183.                 _negativeASCII[i] = last - beforefirst;
  184.            
  185.             _lowASCII = 127;
  186.             _highASCII = 0;
  187.            
  188.             for (examine = last; examine != beforefirst; examine -= bump) {
  189.                 ch = pattern[examine];
  190.                
  191.                 if (ch < 128) {
  192.                     if (_lowASCII > ch)
  193.                         _lowASCII = ch;
  194.                    
  195.                     if (_highASCII < ch)
  196.                         _highASCII = ch;
  197.                    
  198.                     if (_negativeASCII[ch] == last - beforefirst)
  199.                         _negativeASCII[ch] = last - examine;
  200.                 }
  201.                 else {
  202.                     int i = ch >> 8;
  203.                     int j = ch & 255;
  204.                    
  205.                     if (_negativeUnicode == null) {
  206.                         _negativeUnicode = new int[256][];
  207.                     }
  208.                    
  209.                     if (_negativeUnicode[i] == null) {
  210.                         int[] newarray = new int[256];
  211.                        
  212.                         for (int k = 0; k < 256; k++)
  213.                             newarray[k] = last - beforefirst;
  214.                        
  215.                         if (i == 0) {
  216.                             System.Array.Copy(_negativeASCII, newarray, 128);
  217.                             _negativeASCII = newarray;
  218.                         }
  219.                        
  220.                         _negativeUnicode[i] = newarray;
  221.                     }
  222.                    
  223.                     if (_negativeUnicode[i][j] == last - beforefirst)
  224.                         _negativeUnicode[i][j] = last - examine;
  225.                 }
  226.             }
  227.         }
  228.        
  229.         private bool MatchPattern(string text, int index)
  230.         {
  231.             if (_caseInsensitive) {
  232.                 if (text.Length - index < _pattern.Length) {
  233.                     return false;
  234.                 }
  235.                
  236.                 TextInfo textinfo = _culture.TextInfo;
  237.                 for (int i = 0; i < _pattern.Length; i++) {
  238.                     Debug.Assert(textinfo.ToLower(_pattern[i]) == _pattern[i], "pattern should be converted to lower case in constructor!");
  239.                     if (textinfo.ToLower(text[index + i]) != _pattern[i]) {
  240.                         return false;
  241.                     }
  242.                 }
  243.                 return true;
  244.             }
  245.             else {
  246.                 return (0 == String.CompareOrdinal(_pattern, 0, text, index, _pattern.Length));
  247.             }
  248.         }
  249.        
  250. /*
  251.         * When a regex is anchored, we can do a quick IsMatch test instead of a Scan
  252.         */       
  253.         internal bool IsMatch(string text, int index, int beglimit, int endlimit)
  254.         {
  255.            
  256.             if (!_rightToLeft) {
  257.                 if (index < beglimit || endlimit - index < _pattern.Length)
  258.                     return false;
  259.                
  260.                 return MatchPattern(text, index);
  261.             }
  262.             else {
  263.                 if (index > endlimit || index - beglimit < _pattern.Length)
  264.                     return false;
  265.                
  266.                 return MatchPattern(text, index - _pattern.Length);
  267.             }
  268.         }
  269.        
  270.        
  271. /*
  272.         * Scan uses the Boyer-Moore algorithm to find the first occurrance
  273.         * of the specified string within text, beginning at index, and
  274.         * constrained within beglimit and endlimit.
  275.         *
  276.         * The direction and case-sensitivity of the match is determined
  277.         * by the arguments to the RegexBoyerMoore constructor.
  278.         */       
  279.         internal int Scan(string text, int index, int beglimit, int endlimit)
  280.         {
  281.             int test;
  282.             int test2;
  283.             int match;
  284.             int startmatch;
  285.             int endmatch;
  286.             int advance;
  287.             int defadv;
  288.             int bump;
  289.             char chMatch;
  290.             char chTest;
  291.             int[] unicodeLookup;
  292.            
  293.             if (!_rightToLeft) {
  294.                 defadv = _pattern.Length;
  295.                 startmatch = _pattern.Length - 1;
  296.                 endmatch = 0;
  297.                 test = index + defadv - 1;
  298.                 bump = 1;
  299.             }
  300.             else {
  301.                 defadv = -_pattern.Length;
  302.                 startmatch = 0;
  303.                 endmatch = -defadv - 1;
  304.                 test = index + defadv;
  305.                 bump = -1;
  306.             }
  307.            
  308.             chMatch = _pattern[startmatch];
  309.            
  310.             for (;;) {
  311.                 if (test >= endlimit || test < beglimit)
  312.                     return -1;
  313.                
  314.                 chTest = text[test];
  315.                
  316.                 if (_caseInsensitive)
  317.                     chTest = Char.ToLower(chTest, _culture);
  318.                
  319.                 if (chTest != chMatch) {
  320.                     if (chTest < 128)
  321.                         advance = _negativeASCII[chTest];
  322.                     else if (null != _negativeUnicode && (null != (unicodeLookup = _negativeUnicode[chTest >> 8])))
  323.                         advance = unicodeLookup[chTest & 255];
  324.                     else
  325.                         advance = defadv;
  326.                    
  327.                     test += advance;
  328.                 }
  329.                 else {
  330.                     // if (chTest == chMatch)
  331.                     test2 = test;
  332.                     match = startmatch;
  333.                    
  334.                     for (;;) {
  335.                         if (match == endmatch)
  336.                             return (_rightToLeft ? test2 + 1 : test2);
  337.                        
  338.                         match -= bump;
  339.                         test2 -= bump;
  340.                        
  341.                         chTest = text[test2];
  342.                        
  343.                         if (_caseInsensitive)
  344.                             chTest = Char.ToLower(chTest, _culture);
  345.                        
  346.                         if (chTest != _pattern[match]) {
  347.                             advance = _positive[match];
  348.                             if ((chTest & 65408) == 0)
  349.                                 test2 = (match - startmatch) + _negativeASCII[chTest];
  350.                             else if (null != _negativeUnicode && (null != (unicodeLookup = _negativeUnicode[chTest >> 8])))
  351.                                 test2 = (match - startmatch) + unicodeLookup[chTest & 255];
  352.                             else {
  353.                                 test += advance;
  354.                                 break;
  355.                             }
  356.                            
  357.                             if (_rightToLeft ? test2 < advance : test2 > advance)
  358.                                 advance = test2;
  359.                            
  360.                             test += advance;
  361.                             break;
  362.                         }
  363.                     }
  364.                 }
  365.             }
  366.         }
  367.        
  368. /*
  369.         * Used when dumping for debugging.
  370.         */       
  371.         public override string ToString()
  372.         {
  373.             return _pattern;
  374.         }
  375.        
  376.         #if DBG
  377.         public string Dump(string indent)
  378.         {
  379.             StringBuilder sb = new StringBuilder();
  380.            
  381.             sb.Append(indent + "BM Pattern: " + _pattern + "\n");
  382.             sb.Append(indent + "Positive: ");
  383.             for (int i = 0; i < _positive.Length; i++) {
  384.                 sb.Append(_positive[i].ToString(CultureInfo.InvariantCulture) + " ");
  385.             }
  386.             sb.Append("\n");
  387.            
  388.             if (_negativeASCII != null) {
  389.                 sb.Append(indent + "Negative table\n");
  390.                 for (int i = 0; i < _negativeASCII.Length; i++) {
  391.                     if (_negativeASCII[i] != _pattern.Length) {
  392.                         sb.Append(indent + " " + Regex.Escape(Convert.ToString((char)i, CultureInfo.InvariantCulture)) + " " + _negativeASCII[i].ToString(CultureInfo.InvariantCulture) + "\n");
  393.                     }
  394.                 }
  395.             }
  396.            
  397.             return sb.ToString();
  398.         }
  399.         #endif
  400.     }
  401. }

Developer Fusion