We need you! We're working hard on the next version of Developer Fusion - Let us know what you think we should be up to!

The Labs \ Source Viewer \ SSCLI \ System.Security.Util \ TokenizerShortBlock

SSCLI
  1. // ==++==
  2. //
  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. //
  14. // ==--==
  15. /*============================================================
  16. **
  17. ** CLASS:    Tokenizer.cs
  18. **
  19. **
  20. ** PURPOSE:  Tokenize "Elementary XML", that is, XML without
  21. **          attributes or DTDs, in other words, XML with
  22. **          elements only.
  23. **
  24. **
  25. ===========================================================*/
  26. namespace System.Security.Util
  27. {
  28.     using System.Text;
  29.     using System;
  30.     using System.IO;
  31.     using System.Globalization;
  32.    
  33.     internal sealed class Tokenizer
  34.     {
  35.         // There are five externally knowable token types: bras, kets,
  36.         // slashes, cstrs, and equals.
  37.        
  38.         internal const byte bra = 0;
  39.         internal const byte ket = 1;
  40.         internal const byte slash = 2;
  41.         internal const byte cstr = 3;
  42.         internal const byte equals = 4;
  43.         internal const byte quest = 5;
  44.         internal const byte bang = 6;
  45.         internal const byte dash = 7;
  46.        
  47.         // these are the assorted text characters that the tokenizer must
  48.         // understand to do its job
  49.        
  50.         internal const int intOpenBracket = (int)'<';
  51.         internal const int intCloseBracket = (int)'>';
  52.         internal const int intSlash = (int)'/';
  53.         internal const int intEquals = (int)'=';
  54.         internal const int intQuote = (int)'"';
  55.         internal const int intQuest = (int)'?';
  56.         internal const int intBang = (int)'!';
  57.         internal const int intDash = (int)'-';
  58.         internal const int intTab = (int)'\t';
  59.         internal const int intCR = (int)'\r';
  60.         internal const int intLF = (int)'\n';
  61.         internal const int intSpace = (int)' ';
  62.        
  63.         // this tells us where we will be getting our input from
  64.         // and what the encoding is (if any)
  65.        
  66.         private enum TokenSource
  67.         {
  68.             UnicodeByteArray,
  69.             // this is little-endian unicode (there are other encodings)
  70.             UTF8ByteArray,
  71.             ASCIIByteArray,
  72.             CharArray,
  73.             String,
  74.             NestedStrings,
  75.             Other
  76.         }
  77.        
  78.         // byte streams can come in 3 different flavors
  79.        
  80.         internal enum ByteTokenEncoding
  81.         {
  82.             UnicodeTokens,
  83.             // this is little-endian unicode (there are other encodings)
  84.             UTF8Tokens,
  85.             ByteTokens
  86.         }
  87.        
  88.         public int LineNo;
  89.        
  90.         // these variables represent the input state of the of the tokenizer
  91.        
  92.         private int _inProcessingTag;
  93.         private byte[] _inBytes;
  94.         private char[] _inChars;
  95.         private string _inString;
  96.         private int _inIndex;
  97.         private int _inSize;
  98.         private int _inSavedCharacter;
  99.         private TokenSource _inTokenSource;
  100.         private ITokenReader _inTokenReader;
  101.        
  102.         // these variables are used to build and deliver tokenizer output strings
  103.        
  104.         private StringMaker _maker = null;
  105.        
  106.         private string[] _searchStrings;
  107.         private string[] _replaceStrings;
  108.        
  109.         private int _inNestedIndex;
  110.         private int _inNestedSize;
  111.         private string _inNestedString;
  112.        
  113.        
  114.         //================================================================
  115.         // Constructor uses given ICharInputStream
  116.         //
  117.        
  118.         internal void BasicInitialization()
  119.         {
  120.             LineNo = 1;
  121.             _inProcessingTag = 0;
  122.             _inSavedCharacter = -1;
  123.             _inIndex = 0;
  124.             _inSize = 0;
  125.             _inNestedSize = 0;
  126.             _inNestedIndex = 0;
  127.             _inTokenSource = TokenSource.Other;
  128.             _maker = System.SharedStatics.GetSharedStringMaker();
  129.         }
  130.        
  131.         public void Recycle()
  132.         {
  133.             System.SharedStatics.ReleaseSharedStringMaker(ref _maker);
  134.             // will set _maker to null
  135.         }
  136.        
  137.         internal Tokenizer(string input)
  138.         {
  139.             BasicInitialization();
  140.             _inString = input;
  141.             _inSize = input.Length;
  142.             _inTokenSource = TokenSource.String;
  143.         }
  144.        
  145.         internal Tokenizer(string input, string[] searchStrings, string[] replaceStrings)
  146.         {
  147.             BasicInitialization();
  148.             _inString = input;
  149.             _inSize = _inString.Length;
  150.             _inTokenSource = TokenSource.NestedStrings;
  151.             _searchStrings = searchStrings;
  152.             _replaceStrings = replaceStrings;
  153.            
  154.             #if DEBUG
  155.             BCLDebug.Assert(searchStrings.Length == replaceStrings.Length, "different number of search/replace strings");
  156.             BCLDebug.Assert(searchStrings.Length != 0, "no search replace strings, shouldn't be using this ctor");
  157.            
  158.             for (int istr = 0; istr < searchStrings.Length; istr++) {
  159.                 string str = searchStrings[istr];
  160.                 BCLDebug.Assert(str != null, "XML Slug null");
  161.                 BCLDebug.Assert(str.Length >= 3, "XML Slug too small");
  162.                 BCLDebug.Assert(str[0] == '{', "XML Slug doesn't start with '{'");
  163.                 BCLDebug.Assert(str[str.Length - 1] == '}', "XML Slug doesn't end with '}'");
  164.                
  165.                 str = replaceStrings[istr];
  166.                 BCLDebug.Assert(str != null, "XML Replacement null");
  167.                 BCLDebug.Assert(str.Length >= 1, "XML Replacement empty");
  168.             }
  169.             #endif
  170.         }
  171.        
  172.         internal Tokenizer(byte[] array, ByteTokenEncoding encoding, int startIndex)
  173.         {
  174.             BasicInitialization();
  175.             _inBytes = array;
  176.             _inSize = array.Length;
  177.             _inIndex = startIndex;
  178.            
  179.             switch (encoding) {
  180.                 case ByteTokenEncoding.UnicodeTokens:
  181.                     _inTokenSource = TokenSource.UnicodeByteArray;
  182.                     break;
  183.                 case ByteTokenEncoding.UTF8Tokens:
  184.                    
  185.                     _inTokenSource = TokenSource.UTF8ByteArray;
  186.                     break;
  187.                 case ByteTokenEncoding.ByteTokens:
  188.                    
  189.                     _inTokenSource = TokenSource.ASCIIByteArray;
  190.                     break;
  191.                 default:
  192.                    
  193.                     throw new ArgumentException(String.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("Arg_EnumIllegalVal"), (int)encoding));
  194.                     break;
  195.             }
  196.         }
  197.        
  198.         internal Tokenizer(char[] array)
  199.         {
  200.             BasicInitialization();
  201.             _inChars = array;
  202.             _inSize = array.Length;
  203.             _inTokenSource = TokenSource.CharArray;
  204.         }
  205.        
  206.         internal Tokenizer(StreamReader input)
  207.         {
  208.             BasicInitialization();
  209.             _inTokenReader = new StreamTokenReader(input);
  210.         }
  211.        
  212.         internal void ChangeFormat(System.Text.Encoding encoding)
  213.         {
  214.             if (encoding == null) {
  215.                 return;
  216.             }
  217.            
  218.             BCLDebug.Assert(_inSavedCharacter == -1, "There was a lookahead character at the stream change point, that means the parser is changing encodings too late");
  219.            
  220.             switch (_inTokenSource) {
  221.                 case TokenSource.UnicodeByteArray:
  222.                 case TokenSource.UTF8ByteArray:
  223.                 case TokenSource.ASCIIByteArray:
  224.                     // these are the ones we can change on the fly
  225.                    
  226.                     if (encoding == System.Text.Encoding.Unicode) {
  227.                         _inTokenSource = TokenSource.UnicodeByteArray;
  228.                         return;
  229.                     }
  231.                    
  232.                     if (encoding == System.Text.Encoding.UTF8) {
  233.                         _inTokenSource = TokenSource.UTF8ByteArray;
  234.                         return;
  235.                     }
  237.                    
  238.                     if (encoding == System.Text.Encoding.ASCII) {
  239.                         _inTokenSource = TokenSource.ASCIIByteArray;
  240.                         return;
  241.                     }
  243.                     break;
  244.                 case TokenSource.String:
  245.                 case TokenSource.CharArray:
  246.                 case TokenSource.NestedStrings:
  247.                    
  248.                     // these are already unicode and encoding changes are moot
  249.                     // they can't be further decoded
  250.                     return;
  251.             }
  252.            
  253.             // if we're here it means we don't know how to change
  254.             // to the desired encoding with the memory that we have
  255.             // we'll have to do this the hard way -- that means
  256.             // creating a suitable stream from what we've got
  257.            
  258.             // this is thankfully the rare case as UTF8 and unicode
  259.             // dominate the scene
  260.            
  261.             Stream stream = null;
  262.            
  263.             switch (_inTokenSource) {
  264.                 case TokenSource.UnicodeByteArray:
  265.                 case TokenSource.UTF8ByteArray:
  266.                 case TokenSource.ASCIIByteArray:
  267.                     stream = new MemoryStream(_inBytes, _inIndex, _inSize - _inIndex);
  268.                     break;
  269.                 case TokenSource.CharArray:
  270.                 case TokenSource.String:
  271.                 case TokenSource.NestedStrings:
  272.                    
  273.                     BCLDebug.Assert(false, "attempting to change encoding on a non-changable source, should have been prevented earlier");
  274.                     return;
  275.                 default:
  276.                    
  277.                     StreamTokenReader reader = _inTokenReader as StreamTokenReader;
  278.                    
  279.                     if (reader == null) {
  280.                         BCLDebug.Assert(false, "A new input source type has been added to the Tokenizer but it doesn't support encoding changes");
  281.                         return;
  282.                     }
  284.                    
  285.                     stream = reader._in.BaseStream;
  286.                    
  287.                     BCLDebug.Assert(reader._in.CurrentEncoding != null, "Tokenizer's StreamReader does not have an encoding");
  288.                    
  289.                     string fakeReadString = new string(' ', reader.NumCharEncountered);
  290.                     stream.Position = reader._in.CurrentEncoding.GetByteCount(fakeReadString);
  291.                     break;
  292.             }
  293.            
  294.             BCLDebug.Assert(stream != null, "The XML stream with new encoding was not properly initialized for kind of input we had");
  295.            
  296.             // we now have an initialized memory stream based on whatever source we had before
  297.             _inTokenReader = new StreamTokenReader(new StreamReader(stream, encoding));
  298.             _inTokenSource = TokenSource.Other;
  299.         }
  300.        
  301.         internal void GetTokens(TokenizerStream stream, int maxNum, bool endAfterKet)
  302.         {
  303.             while (maxNum == -1 || stream.GetTokenCount() < maxNum) {
  304.                 int i = -1;
  305.                 byte ch;
  306.                 int cb = 0;
  307.                 bool inLiteral = false;
  308.                 bool inQuotedString = false;
  309.                
  310.                 StringMaker m = _maker;
  311.                
  312.                 m._outStringBuilder = null;
  313.                 m._outIndex = 0;
  314.                 BEGINNING:
  315.                
  316.                
  317.                 if (_inSavedCharacter != -1) {
  318.                     i = _inSavedCharacter;
  319.                     _inSavedCharacter = -1;
  320.                 }
  321.                 else
  322.                     switch (_inTokenSource) {
  323.                         case TokenSource.UnicodeByteArray:
  324.                             if (_inIndex + 1 >= _inSize) {
  325.                                 stream.AddToken(-1);
  326.                                 return;
  327.                             }
  329.                            
  330.                             i = (int)((_inBytes[_inIndex + 1] << 8) + _inBytes[_inIndex]);
  331.                             _inIndex += 2;
  332.                             break;
  333.                         case TokenSource.UTF8ByteArray:
  334.                            
  335.                             if (_inIndex >= _inSize) {
  336.                                 stream.AddToken(-1);
  337.                                 return;
  338.                             }
  340.                            
  341.                             i = (int)(_inBytes[_inIndex++]);
  342.                            
  343.                             // single byte -- case, early out as we're done already
  344.                             if ((i & 128) == 0)
  345.                                 break;
  347.                            
  348.                             // to decode the lead byte switch on the high nibble
  349.                             // shifted down so the switch gets dense integers
  350.                             switch ((i & 240) >> 4) {
  351.                                 case 8:
  352.                                 case 9:
  353.                                 case 10:
  354.                                 case 11:
  355.                                     // 1000 (together these 4 make 10xxxxx)
  356.                                     // 1001
  357.                                     // 1010
  358.                                     // 1011
  359.                                     // trail byte is an error
  360.                                     throw new XmlSyntaxException(LineNo);
  361.                                     break;
  362.                                 case 12:
  363.                                 case 13:
  364.                                    
  365.                                     // 1100 (these two make 110xxxxx)
  366.                                     // 1101
  367.                                     // two byte encoding (1 trail byte)
  368.                                     i &= 31;
  369.                                     cb = 2;
  370.                                     break;
  371.                                 case 14:
  372.                                    
  373.                                     // 1110 (this gets us 1110xxxx)
  374.                                     // three byte encoding (2 trail bytes)
  375.                                     i &= 15;
  376.                                     cb = 3;
  377.                                     break;
  378.                                 case 15:
  379.                                    
  380.                                     // 1111 (and finally 1111xxxx)
  381.                                     // 4 byte encoding is an error
  382.                                     throw new XmlSyntaxException(LineNo);
  383.                                     break;
  384.                             }
  385.                            
  386.                             // at least one trail byte, fetch it
  387.                             if (_inIndex >= _inSize)
  388.                                 throw new XmlSyntaxException(LineNo, Environment.GetResourceString("XMLSyntax_UnexpectedEndOfFile"));
  390.                            
  391.                             ch = _inBytes[_inIndex++];
  392.                            
  393.                             // must be trail byte encoding
  394.                             if ((ch & 192) != 128)
  395.                                 throw new XmlSyntaxException(LineNo);
  397.                            
  398.                             i = (i << 6) | (ch & 63);
  399.                            
  400.                             // done now if 2 byte encoding, otherwise go for 3
  401.                             if (cb == 2)
  402.                                 break;
  404.                            
  405.                             if (_inIndex >= _inSize)
  406.                                 throw new XmlSyntaxException(LineNo, Environment.GetResourceString("XMLSyntax_UnexpectedEndOfFile"));
  408.                            
  409.                             ch = _inBytes[_inIndex++];
  410.                            
  411.                             // must be trail byte encoding
  412.                             if ((ch & 192) != 128)
  413.                                 throw new XmlSyntaxException(LineNo);
  415.                            
  416.                             i = (i << 6) | (ch & 63);
  417.                             break;
  418.                         case TokenSource.ASCIIByteArray:
  419.                            
  420.                             if (_inIndex >= _inSize) {
  421.                                 stream.AddToken(-1);
  422.                                 return;
  423.                             }
  425.                            
  426.                             i = (int)(_inBytes[_inIndex++]);
  427.                             break;
  428.                         case TokenSource.CharArray:
  429.                            
  430.                             if (_inIndex >= _inSize) {
  431.                                 stream.AddToken(-1);
  432.                                 return;
  433.                             }
  435.                            
  436.                             i = (int)(_inChars[_inIndex++]);
  437.                             break;
  438.                         case TokenSource.String:
  439.                            
  440.                             if (_inIndex >= _inSize) {
  441.                                 stream.AddToken(-1);
  442.                                 return;
  443.                             }
  445.                            
  446.                             i = (int)(_inString[_inIndex++]);
  447.                             break;
  448.                         case TokenSource.NestedStrings:
  449.                            
  450.                             if (_inNestedSize != 0) {
  451.                                 if (_inNestedIndex < _inNestedSize) {
  452.                                     i = _inNestedString[_inNestedIndex++];
  453.                                     break;
  454.                                 }
  455.                                
  456.                                 _inNestedSize = 0;
  457.                             }
  459.                            
  460.                             if (_inIndex >= _inSize) {
  461.                                 stream.AddToken(-1);
  462.                                 return;
  463.                             }
  465.                            
  466.                             i = (int)(_inString[_inIndex++]);
  467.                            
  468.                             if (i != '{')
  469.                                 break;
  471.                            
  472.                             for (int istr = 0; istr < _searchStrings.Length; istr++) {
  473.                                 if (0 == String.Compare(_searchStrings[istr], 0, _inString, _inIndex - 1, _searchStrings[istr].Length, StringComparison.Ordinal)) {
  474.                                     _inNestedString = _replaceStrings[istr];
  475.                                     _inNestedSize = _inNestedString.Length;
  476.                                     _inNestedIndex = 1;
  477.                                     i = _inNestedString[0];
  478.                                     _inIndex += _searchStrings[istr].Length - 1;
  479.                                     break;
  480.                                 }
  481.                             }
  483.                            
  484.                             break;
  485.                         default:
  486.                            
  487.                             i = _inTokenReader.Read();
  488.                             if (i == -1) {
  489.                                 stream.AddToken(-1);
  490.                                 return;
  491.                             }
  493.                             break;
  494.                     }
  495.                
  496.                 if (!inLiteral) {
  497.                     switch (i) {
  498.                         case intSpace:
  499.                         case intTab:
  500.                         case intCR:
  501.                             // skip whitespace
  502.                             goto BEGINNING;
  503.                             break;
  504.                         case intLF:
  505.                            
  506.                             // count linefeeds
  507.                             LineNo++;
  508.                             goto BEGINNING;
  509.                             break;
  510.                         case intOpenBracket:
  511.                            
  512.                             _inProcessingTag++;
  513.                             stream.AddToken(bra);
  514.                             continue;
  515.                         case intCloseBracket:
  516.                            
  517.                             _inProcessingTag--;
  518.                             stream.AddToken(ket);
  519.                             if (endAfterKet)
  520.                                 return;
  522.                             continue;
  523.                         case intEquals:
  524.                            
  525.                             stream.AddToken(equals);
  526.                             continue;
  527.                         case intSlash:
  528.                            
  529.                             if (_inProcessingTag != 0) {
  530.                                 stream.AddToken(slash);
  531.                                 continue;
  532.                             }
  534.                             break;
  535.                         case intQuest:
  536.                            
  537.                             if (_inProcessingTag != 0) {
  538.                                 stream.AddToken(quest);
  539.                                 continue;
  540.                             }
  542.                             break;
  543.                         case intBang:
  544.                            
  545.                             if (_inProcessingTag != 0) {
  546.                                 stream.AddToken(bang);
  547.                                 continue;
  548.                             }
  550.                             break;
  551.                         case intDash:
  552.                            
  553.                             if (_inProcessingTag != 0) {
  554.                                 stream.AddToken(dash);
  555.                                 continue;
  556.                             }
  558.                             break;
  559.                         case intQuote:
  560.                            
  561.                             inLiteral = true;
  562.                             inQuotedString = true;
  563.                             goto BEGINNING;
  564.                             break;
  565.                     }
  566.                 }
  567.                 else {
  568.                     switch (i) {
  569.                         case intOpenBracket:
  570.                             if (!inQuotedString) {
  571.                                 _inSavedCharacter = i;
  572.                                 stream.AddToken(cstr);
  573.                                 stream.AddString(this.GetStringToken());
  574.                                 continue;
  575.                             }
  577.                             break;
  578.                         case intCloseBracket:
  579.                         case intEquals:
  580.                         case intSlash:
  581.                            
  582.                             if (!inQuotedString && _inProcessingTag != 0) {
  583.                                 _inSavedCharacter = i;
  584.                                 stream.AddToken(cstr);
  585.                                 stream.AddString(this.GetStringToken());
  586.                                 continue;
  587.                             }
  589.                             break;
  590.                         case intQuote:
  591.                            
  592.                             if (inQuotedString) {
  593.                                 stream.AddToken(cstr);
  594.                                 stream.AddString(this.GetStringToken());
  595.                                 continue;
  596.                             }
  598.                             break;
  599.                         case intTab:
  600.                         case intCR:
  601.                         case intSpace:
  602.                            
  603.                             if (!inQuotedString) {
  604.                                 stream.AddToken(cstr);
  605.                                 stream.AddString(this.GetStringToken());
  606.                                 continue;
  607.                             }
  609.                             break;
  610.                         case intLF:
  611.                            
  612.                             // count linefeeds
  613.                             LineNo++;
  614.                            
  615.                             if (!inQuotedString) {
  616.                                 stream.AddToken(cstr);
  617.                                 stream.AddString(this.GetStringToken());
  618.                                 continue;
  619.                             }
  621.                             break;
  622.                     }
  623.                 }
  624.                
  625.                 inLiteral = true;
  626.                
  627.                 // add character to the string
  628.                 if (m._outIndex < StringMaker.outMaxSize) {
  629.                     // easy case
  630.                     m._outChars[m._outIndex++] = (char)i;
  631.                 }
  632.                 else {
  633.                     if (m._outStringBuilder == null) {
  634.                         // OK, first check if we have to init the StringBuilder
  635.                         m._outStringBuilder = new StringBuilder();
  636.                     }
  637.                    
  638.                     // OK, copy from _outChars to _outStringBuilder
  639.                     m._outStringBuilder.Append(m._outChars, 0, StringMaker.outMaxSize);
  640.                    
  641.                     // reset _outChars pointer
  642.                     m._outChars[0] = (char)i;
  643.                     m._outIndex = 1;
  644.                 }
  645.                
  646.                 goto BEGINNING;
  647.             }
  648.         }
  649.        
  650.         [Serializable()]
  651.         internal sealed class StringMaker
  652.         {
  653.             string[] aStrings;
  654.             uint cStringsMax;
  655.             uint cStringsUsed;
  656.            
  657.             public StringBuilder _outStringBuilder;
  658.             public char[] _outChars;
  659.             public int _outIndex;
  660.            
  661.             public const int outMaxSize = 512;
  662.            
  663.             static uint HashString(string str)
  664.             {
  665.                 uint hash = 0;
  666.                
  667.                 int l = str.Length;
  668.                
  669.                 // rotate in string character
  670.                 for (int i = 0; i < l; i++) {
  671.                     hash = (hash << 3) ^ (uint)str[i] ^ (hash >> 29);
  672.                 }
  673.                
  674.                 return hash;
  675.             }
  676.            
  677.             static uint HashCharArray(char[] a, int l)
  678.             {
  679.                 uint hash = 0;
  680.                
  681.                 // rotate in a character
  682.                 for (int i = 0; i < l; i++) {
  683.                     hash = (hash << 3) ^ (uint)a[i] ^ (hash >> 29);
  684.                 }
  685.                
  686.                 return hash;
  687.             }
  688.            
  689.             public StringMaker()
  690.             {
  691.                 cStringsMax = 2048;
  692.                 cStringsUsed = 0;
  693.                 aStrings = new string[cStringsMax];
  694.                 _outChars = new char[outMaxSize];
  695.             }
  696.            
  697.             bool CompareStringAndChars(string str, char[] a, int l)
  698.             {
  699.                 if (str.Length != l)
  700.                     return false;
  701.                
  702.                 for (int i = 0; i < l; i++)
  703.                     if (a[i] != str[i])
  704.                         return false;
  706.                
  707.                 return true;
  708.             }
  709.            
  710.             public string MakeString()
  711.             {
  712.                 uint hash;
  713.                 char[] a = _outChars;
  714.                 int l = _outIndex;
  715.                
  716.                 // if we have a stringbuilder then we have to append... slow case
  717.                 if (_outStringBuilder != null) {
  718.                     _outStringBuilder.Append(_outChars, 0, _outIndex);
  719.                     return _outStringBuilder.ToString();
  720.                 }
  721.                
  722.                 // no stringbuilder, fast case, shareable string
  723.                
  724.                 if (cStringsUsed > (cStringsMax / 4) * 3) {
  725.                     // we need to rehash
  726.                    
  727.                     uint cNewMax = cStringsMax * 2;
  728.                     string[] aStringsNew = new string[cNewMax];
  729.                    
  730.                     for (int i = 0; i < cStringsMax; i++) {
  731.                         if (aStrings[i] != null) {
  732.                             hash = HashString(aStrings[i]) % cNewMax;
  733.                            
  734.                             while (aStringsNew[hash] != null) {
  735.                                 // slot full, skip
  736.                                 if (++hash >= cNewMax)
  737.                                     hash = 0;
  738.                             }
  739.                            
  740.                             aStringsNew[hash] = aStrings[i];
  741.                         }
  742.                     }
  743.                    
  744.                     // all done, cutover to the new hash table
  745.                     cStringsMax = cNewMax;
  746.                     aStrings = aStringsNew;
  747.                 }
  748.                
  749.                 hash = HashCharArray(a, l) % cStringsMax;
  750.                
  751.                 string str;
  752.                
  753.                 while ((str = aStrings[hash]) != null) {
  754.                     if (CompareStringAndChars(str, a, l))
  755.                         return str;
  756.                    
  757.                     if (++hash >= cStringsMax)
  758.                         hash = 0;
  759.                 }
  760.                
  761.                 str = new string(a, 0, l);
  762.                 aStrings[hash] = str;
  763.                 cStringsUsed++;
  764.                
  765.                 return str;
  766.             }
  767.         }
  768.        
  769.         //================================================================
  770.         //
  771.         //
  772.        
  773.         private string GetStringToken()
  774.         {
  775.             return _maker.MakeString();
  776.         }
  777.        
  778.         internal interface ITokenReader
  779.         {
  780.             int Read();
  781.         }
  782.        
  783.         internal class StreamTokenReader : ITokenReader
  784.         {
  785.            
  786.             internal StreamReader _in;
  787.             internal int _numCharRead;
  788.            
  789.             internal StreamTokenReader(StreamReader input)
  790.             {
  791.                 _in = input;
  792.                 _numCharRead = 0;
  793.             }
  794.            
  795.             public virtual int Read()
  796.             {
  797.                 int value = _in.Read();
  798.                 if (value != -1)
  799.                     _numCharRead++;
  800.                 return value;
  801.             }
  802.            
  803.             internal int NumCharEncountered {
  804.                 get { return _numCharRead; }
  805.             }
  806.         }
  807.     }
  808.    
  809.     internal sealed class TokenizerShortBlock
  810.     {
  811.         internal short[] m_block = new short[16];
  812.         internal TokenizerShortBlock m_next = null;
  813.     }
  814.    
  815.     internal sealed class TokenizerStringBlock
  816.     {
  817.         internal string[] m_block = new string[16];
  818.         internal TokenizerStringBlock m_next = null;
  819.     }
  820.    
  821.    
  822.     internal sealed class TokenizerStream
  823.     {
  824.         private int m_countTokens;
  825.        
  826.         private TokenizerShortBlock m_headTokens;
  827.         private TokenizerShortBlock m_lastTokens;
  828.         private TokenizerShortBlock m_currentTokens;
  829.         private int m_indexTokens;
  830.        
  831.         private TokenizerStringBlock m_headStrings;
  832.         private TokenizerStringBlock m_currentStrings;
  833.         private int m_indexStrings;
  834.        
  835.         #if _DEBUG
  836.         private bool m_bLastWasCStr;
  837.         #endif
  838.        
  839.         internal TokenizerStream()
  840.         {
  841.             m_countTokens = 0;
  842.             m_headTokens = new TokenizerShortBlock();
  843.             m_headStrings = new TokenizerStringBlock();
  844.             Reset();
  845.         }
  846.        
  847.         internal void AddToken(short token)
  848.         {
  849.             if (m_currentTokens.m_block.Length <= m_indexTokens) {
  850.                 m_currentTokens.m_next = new TokenizerShortBlock();
  851.                 m_currentTokens = m_currentTokens.m_next;
  852.                 m_indexTokens = 0;
  853.             }
  854.            
  855.             m_countTokens++;
  856.             m_currentTokens.m_block[m_indexTokens++] = token;
  857.         }
  858.        
  859.         internal void AddString(string str)
  860.         {
  861.             if (m_currentStrings.m_block.Length <= m_indexStrings) {
  862.                 m_currentStrings.m_next = new TokenizerStringBlock();
  863.                 m_currentStrings = m_currentStrings.m_next;
  864.                 m_indexStrings = 0;
  865.             }
  866.            
  867.             m_currentStrings.m_block[m_indexStrings++] = str;
  868.         }
  869.        
  870.         internal void Reset()
  871.         {
  872.             m_lastTokens = null;
  873.             m_currentTokens = m_headTokens;
  874.             m_currentStrings = m_headStrings;
  875.             m_indexTokens = 0;
  876.             m_indexStrings = 0;
  877.             #if _DEBUG
  878.             m_bLastWasCStr = false;
  879.             #endif
  880.         }
  881.        
  882.         internal short GetNextFullToken()
  883.         {
  884.             if (m_currentTokens.m_block.Length <= m_indexTokens) {
  885.                 m_lastTokens = m_currentTokens;
  886.                 m_currentTokens = m_currentTokens.m_next;
  887.                 m_indexTokens = 0;
  888.             }
  889.            
  890.             return m_currentTokens.m_block[m_indexTokens++];
  891.         }
  892.        
  893.         internal short GetNextToken()
  894.         {
  895.             short retval = (short)(GetNextFullToken() & 255);
  896.             #if _DEBUG
  897.             BCLDebug.Assert(!m_bLastWasCStr, "CStr token not followed by GetNextString()");
  898.             m_bLastWasCStr = (retval == Tokenizer.cstr);
  899.             #endif
  900.             return retval;
  901.         }
  902.        
  903.         internal string GetNextString()
  904.         {
  905.             if (m_currentStrings.m_block.Length <= m_indexStrings) {
  906.                 m_currentStrings = m_currentStrings.m_next;
  907.                 m_indexStrings = 0;
  908.             }
  909.             #if _DEBUG
  910.             m_bLastWasCStr = false;
  911.             #endif
  912.             return m_currentStrings.m_block[m_indexStrings++];
  913.         }
  914.        
  915.         internal void ThrowAwayNextString()
  916.         {
  917.             GetNextString();
  918.         }
  919.        
  920.         internal void TagLastToken(short tag)
  921.         {
  922.             if (m_indexTokens == 0)
  923.                 m_lastTokens.m_block[m_lastTokens.m_block.Length - 1] = (