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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexNode.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 RegexNode class is internal to the Regex package.
  16. // It is built into a parsed tree for a regular expression.
  17. // Implementation notes:
  18. //
  19. // Since the node tree is a temporary data structure only used
  20. // during compilation of the regexp to integer codes, it's
  21. // designed for clarity and convenience rather than
  22. // space efficiency.
  23. //
  24. // RegexNodes are built into a tree, linked by the _children list.
  25. // Each node also has a _parent and _ichild member indicating
  26. // its parent and which child # it is in its parent's list.
  27. //
  28. // RegexNodes come in as many types as there are constructs in
  29. // a regular expression, for example, "concatenate", "alternate",
  30. // "one", "rept", "group". There are also node types for basic
  31. // peephole optimizations, e.g., "onerep", "notsetrep", etc.
  32. //
  33. // Because perl 5 allows "lookback" groups that scan backwards,
  34. // each node also gets a "direction". Normally the value of
  35. // boolean _backward = false.
  36. //
  37. // During parsing, top-level nodes are also stacked onto a parse
  38. // stack (a stack of trees). For this purpose we have a _next
  39. // pointer. [Note that to save a few bytes, we could overload the
  40. // _parent pointer instead.]
  41. //
  42. // On the parse stack, each tree has a "role" - basically, the
  43. // nonterminal in the grammar that the parser has currently
  44. // assigned to the tree. That code is stored in _role.
  45. //
  46. // Finally, some of the different kinds of nodes have data.
  47. // Two integers (for the looping constructs) are stored in
  48. // _operands, an an object (either a string or a set)
  49. // is stored in _data
  50. namespace System.Text.RegularExpressions
  51. {
  52.    
  53.     using System.Collections;
  54.     using System.Diagnostics;
  55.     using System.Globalization;
  56.    
  57.     internal sealed class RegexNode
  58.     {
  59. /*
  60.         * RegexNode types
  61.         */       
  62.        
  63.         // the following are leaves, and correspond to primitive operations
  64.        
  65.         // static final int Onerep = RegexCode.Onerep; // c,n a {n}
  66.         // static final int Notonerep = RegexCode.Notonerep; // c,n .{n}
  67.         // static final int Setrep = RegexCode.Setrep; // set,n \d {n}
  68.        
  69.         internal const int Oneloop = RegexCode.Oneloop;
  70.         // c,n a*
  71.         internal const int Notoneloop = RegexCode.Notoneloop;
  72.         // c,n .*
  73.         internal const int Setloop = RegexCode.Setloop;
  74.         // set,n \d*
  75.         internal const int Onelazy = RegexCode.Onelazy;
  76.         // c,n a*?
  77.         internal const int Notonelazy = RegexCode.Notonelazy;
  78.         // c,n .*?
  79.         internal const int Setlazy = RegexCode.Setlazy;
  80.         // set,n \d*?
  81.         internal const int One = RegexCode.One;
  82.         // char a
  83.         internal const int Notone = RegexCode.Notone;
  84.         // char . [^a]
  85.         internal const int Set = RegexCode.Set;
  86.         // set [a-z] \w \s \d
  87.         internal const int Multi = RegexCode.Multi;
  88.         // string abcdef
  89.         internal const int Ref = RegexCode.Ref;
  90.         // index \1
  91.         internal const int Bol = RegexCode.Bol;
  92.         // ^
  93.         internal const int Eol = RegexCode.Eol;
  94.         // $
  95.         internal const int Boundary = RegexCode.Boundary;
  96.         // \b
  97.         internal const int Nonboundary = RegexCode.Nonboundary;
  98.         // \B
  99.         internal const int ECMABoundary = RegexCode.ECMABoundary;
  100.         // \b
  101.         internal const int NonECMABoundary = RegexCode.NonECMABoundary;
  102.         // \B
  103.         internal const int Beginning = RegexCode.Beginning;
  104.         // \A
  105.         internal const int Start = RegexCode.Start;
  106.         // \G
  107.         internal const int EndZ = RegexCode.EndZ;
  108.         // \Z
  109.         internal const int End = RegexCode.End;
  110.         // \z
  111.         // (note: End = 21;)
  112.        
  113.         // interior nodes do not correpond to primitive operations, but
  114.         // control structures compositing other operations
  115.        
  116.         // concat and alternate take n children, and can run forward or backwards
  117.        
  118.         internal const int Nothing = 22;
  119.         // []
  120.         internal const int Empty = 23;
  121.         // ()
  122.         internal const int Alternate = 24;
  123.         // a|b
  124.         internal const int Concatenate = 25;
  125.         // ab
  126.         internal const int Loop = 26;
  127.         // m,x * + ? {,}
  128.         internal const int Lazyloop = 27;
  129.         // m,x *? +? ?? {,}?
  130.         internal const int Capture = 28;
  131.         // n ()
  132.         internal const int Group = 29;
  133.         // (?:)
  134.         internal const int Require = 30;
  135.         // (?=) (?<=)
  136.         internal const int Prevent = 31;
  137.         // (?!) (?<!)
  138.         internal const int Greedy = 32;
  139.         // (?>) (?<)
  140.         internal const int Testref = 33;
  141.         // (?(n) | )
  142.         internal const int Testgroup = 34;
  143.         // (?(...) | )
  144. /*
  145.         * RegexNode data members
  146.         *
  147.         */       
  148.        
  149.         internal int _type;
  150.        
  151.         internal ArrayList _children;
  152.        
  153.         internal string _str;
  154.         internal char _ch;
  155.         internal int _m;
  156.         internal int _n;
  157.         internal RegexOptions _options;
  158.        
  159.         internal RegexNode _next;
  160.        
  161.         internal RegexNode(int type, RegexOptions options)
  162.         {
  163.             _type = type;
  164.             _options = options;
  165.         }
  166.        
  167.         internal RegexNode(int type, RegexOptions options, char ch)
  168.         {
  169.             _type = type;
  170.             _options = options;
  171.             _ch = ch;
  172.         }
  173.        
  174.         internal RegexNode(int type, RegexOptions options, string str)
  175.         {
  176.             _type = type;
  177.             _options = options;
  178.             _str = str;
  179.         }
  180.        
  181.         internal RegexNode(int type, RegexOptions options, int m)
  182.         {
  183.             _type = type;
  184.             _options = options;
  185.             _m = m;
  186.         }
  187.        
  188.         internal RegexNode(int type, RegexOptions options, int m, int n)
  189.         {
  190.             _type = type;
  191.             _options = options;
  192.             _m = m;
  193.             _n = n;
  194.         }
  195.        
  196.         internal bool UseOptionR()
  197.         {
  198.             return (_options & RegexOptions.RightToLeft) != 0;
  199.         }
  200.        
  201.         internal RegexNode ReverseLeft()
  202.         {
  203.             if (UseOptionR() && _type == Concatenate && _children != null) {
  204.                 _children.Reverse(0, _children.Count);
  205.             }
  206.            
  207.             return this;
  208.         }
  209.        
  210.        
  211.         // Pass type as OneLazy or OneLoop
  212.         internal void MakeRep(int type, int min, int max)
  213.         {
  214.             _type += (type - One);
  215.             _m = min;
  216.             _n = max;
  217.         }
  218.        
  219. /*
  220.         * Reduce
  221.         *
  222.         * Removes redundant nodes from the subtree, and returns a reduced subtree.
  223.         */       
  224.         internal RegexNode Reduce()
  225.         {
  226.             RegexNode n;
  227.            
  228.             switch (Type()) {
  229.                 case Alternate:
  230.                     n = ReduceAlternation();
  231.                     break;
  232.                 case Concatenate:
  233.                    
  234.                     n = ReduceConcatenation();
  235.                     break;
  236.                 case Loop:
  237.                 case Lazyloop:
  238.                    
  239.                     n = ReduceRep();
  240.                     break;
  241.                 case Group:
  242.                    
  243.                     n = ReduceGroup();
  244.                     break;
  245.                 case Set:
  246.                 case Setloop:
  247.                    
  248.                     n = ReduceSet();
  249.                     break;
  250.                 default:
  251.                    
  252.                     n = this;
  253.                     break;
  254.             }
  255.            
  256.             return n;
  257.         }
  258.        
  259.        
  260. /*
  261.         * StripEnation:
  262.         *
  263.         * Simple optimization. If a concatenation or alternation has only
  264.         * one child strip out the intermediate node. If it has zero children,
  265.         * turn it into an empty.
  266.         *
  267.         */       
  268.        
  269.         internal RegexNode StripEnation(int emptyType)
  270.         {
  271.             switch (ChildCount()) {
  272.                 case 0:
  273.                     return new RegexNode(emptyType, _options);
  274.                 case 1:
  275.                     return Child(0);
  276.                 default:
  277.                     return this;
  278.             }
  279.         }
  280.        
  281. /*
  282.         * ReduceGroup:
  283.         *
  284.         * Simple optimization. Once parsed into a tree, noncapturing groups
  285.         * serve no function, so strip them out.
  286.         */       
  287.        
  288.         internal RegexNode ReduceGroup()
  289.         {
  290.             RegexNode u;
  291.            
  292.             for (u = this; u.Type() == Group;)
  293.                 u = u.Child(0);
  294.            
  295.             return u;
  296.         }
  297.        
  298. /*
  299.         * ReduceRep:
  300.         *
  301.         * Nested repeaters just get multiplied with each other if they're not
  302.         * too lumpy
  303.         */       
  304.        
  305.         internal RegexNode ReduceRep()
  306.         {
  307.             RegexNode u;
  308.             RegexNode child;
  309.             int type;
  310.             int min;
  311.             int max;
  312.            
  313.             u = this;
  314.             type = Type();
  315.             min = _m;
  316.             max = _n;
  317.            
  318.             for (;;) {
  319.                 if (u.ChildCount() == 0)
  320.                     break;
  321.                
  322.                 child = u.Child(0);
  323.                
  324.                 // multiply reps of the same type only
  325.                 if (child.Type() != type) {
  326.                     int childType = child.Type();
  327.                    
  328.                     if (!(childType >= Oneloop && childType <= Setloop && type == Loop || childType >= Onelazy && childType <= Setlazy && type == Lazyloop))
  329.                         break;
  330.                 }
  331.                
  332.                 // child can be too lumpy to blur, e.g., (a {100,105}) {3} or (a {2,})?
  333.                 // [but things like (a {2,})+ are not too lumpy...]
  334.                 if (u._m == 0 && child._m > 1 || child._n < child._m * 2)
  335.                     break;
  336.                
  337.                 u = child;
  338.                 if (u._m > 0)
  339.                     u._m = min = ((Int32.MaxValue - 1) / u._m < min) ? Int32.MaxValue : u._m * min;
  340.                 if (u._n > 0)
  341.                     u._n = max = ((Int32.MaxValue - 1) / u._n < max) ? Int32.MaxValue : u._n * max;
  342.             }
  343.            
  344.             return min == Int32.MaxValue ? new RegexNode(Nothing, _options) : u;
  345.         }
  346.        
  347. /*
  348.         * ReduceSet:
  349.         *
  350.         * Simple optimization. If a set is a singleton, an inverse singleton,
  351.         * or empty, it's transformed accordingly.
  352.         */       
  353.        
  354.         internal RegexNode ReduceSet()
  355.         {
  356.             // Extract empty-set, one and not-one case as special
  357.            
  358.             if (RegexCharClass.IsEmpty(_str)) {
  359.                 _type = Nothing;
  360.                 _str = null;
  361.             }
  362.             else if (RegexCharClass.IsSingleton(_str)) {
  363.                 _ch = RegexCharClass.SingletonChar(_str);
  364.                 _str = null;
  365.                 _type += (One - Set);
  366.             }
  367.             else if (RegexCharClass.IsSingletonInverse(_str)) {
  368.                 _ch = RegexCharClass.SingletonChar(_str);
  369.                 _str = null;
  370.                 _type += (Notone - Set);
  371.             }
  372.            
  373.             return this;
  374.         }
  375.        
  376. /*
  377.         * ReduceAlternation:
  378.         *
  379.         * Basic optimization. Single-letter alternations can be replaced
  380.         * by faster set specifications, and nested alternations with no
  381.         * intervening operators can be flattened:
  382.         *
  383.         * a|b|c|def|g|h -> [a-c]|def|[gh]
  384.         * apple|(?:orange|pear)|grape -> apple|orange|pear|grape
  385.         *
  386.         * <CONSIDER>common prefix reductions such as winner|windows -> win(?:ner|dows)</CONSIDER>
  387.         */       
  388.        
  389.         internal RegexNode ReduceAlternation()
  390.         {
  391.             // Combine adjacent sets/chars
  392.            
  393.             bool wasLastSet;
  394.             bool lastNodeCannotMerge;
  395.             RegexOptions optionsLast;
  396.             RegexOptions optionsAt;
  397.             int i;
  398.             int j;
  399.             RegexNode at;
  400.             RegexNode prev;
  401.            
  402.             if (_children == null)
  403.                 return new RegexNode(RegexNode.Nothing, _options);
  404.            
  405.             wasLastSet = false;
  406.             lastNodeCannotMerge = false;
  407.             optionsLast = 0;
  408.            
  409.             for (i = 0,j = 0; i < _children.Count; i++,j++) {
  410.                 at = (RegexNode)_children[i];
  411.                
  412.                 if (j < i)
  413.                     _children[j] = at;
  414.                
  415.                 for (;;) {
  416.                     if (at._type == Alternate) {
  417.                         for (int k = 0; k < at._children.Count; k++)
  418.                             ((RegexNode)at._children[k])._next = this;
  419.                        
  420.                         _children.InsertRange(i + 1, at._children);
  421.                         j--;
  422.                     }
  423.                     else if (at._type == Set || at._type == One) {
  424.                         // Cannot merge sets if L or I options differ, or if either are negated.
  425.                         optionsAt = at._options & (RegexOptions.RightToLeft | RegexOptions.IgnoreCase);
  426.                        
  427.                        
  428.                         if (at._type == Set) {
  429.                             if (!wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge || !RegexCharClass.IsMergeable(at._str)) {
  430.                                 wasLastSet = true;
  431.                                 lastNodeCannotMerge = !RegexCharClass.IsMergeable(at._str);
  432.                                 optionsLast = optionsAt;
  433.                                 break;
  434.                             }
  435.                         }
  436.                         else if (!wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge) {
  437.                             wasLastSet = true;
  438.                             lastNodeCannotMerge = false;
  439.                             optionsLast = optionsAt;
  440.                             break;
  441.                         }
  442.                        
  443.                        
  444.                         // The last node was a Set or a One, we're a Set or One and our options are the same.
  445.                         // Merge the two nodes.
  446.                         j--;
  447.                         prev = (RegexNode)_children[j];
  448.                        
  449.                         RegexCharClass prevCharClass;
  450.                         if (prev._type == RegexNode.One) {
  451.                             prevCharClass = new RegexCharClass();
  452.                             prevCharClass.AddChar(prev._ch);
  453.                         }
  454.                         else {
  455.                             prevCharClass = RegexCharClass.Parse(prev._str);
  456.                         }
  457.                        
  458.                         if (at._type == RegexNode.One) {
  459.                             prevCharClass.AddChar(at._ch);
  460.                         }
  461.                         else {
  462.                             RegexCharClass atCharClass = RegexCharClass.Parse(at._str);
  463.                             prevCharClass.AddCharClass(atCharClass);
  464.                         }
  465.                        
  466.                         prev._type = RegexNode.Set;
  467.                         prev._str = prevCharClass.ToStringClass();
  468.                        
  469.                     }
  470.                     else if (at._type == RegexNode.Nothing) {
  471.                         j--;
  472.                     }
  473.                     else {
  474.                         wasLastSet = false;
  475.                         lastNodeCannotMerge = false;
  476.                     }
  477.                     break;
  478.                 }
  479.             }
  480.            
  481.             if (j < i)
  482.                 _children.RemoveRange(j, i - j);
  483.            
  484.             return StripEnation(RegexNode.Nothing);
  485.         }
  486.        
  487. /*
  488.         * ReduceConcatenation:
  489.         *
  490.         * Basic optimization. Adjacent strings can be concatenated.
  491.         *
  492.         * (?:abc)(?:def) -> abcdef
  493.         */       
  494.        
  495.         internal RegexNode ReduceConcatenation()
  496.         {
  497.             // Eliminate empties and concat adjacent strings/chars
  498.            
  499.             bool wasLastString;
  500.             RegexOptions optionsLast;
  501.             RegexOptions optionsAt;
  502.             int i;
  503.             int j;
  504.            
  505.             if (_children == null)
  506.                 return new RegexNode(RegexNode.Empty, _options);
  507.            
  508.             wasLastString = false;
  509.             optionsLast = 0;
  510.            
  511.             for (i = 0,j = 0; i < _children.Count; i++,j++) {
  512.                 RegexNode at;
  513.                 RegexNode prev;
  514.                
  515.                 at = (RegexNode)_children[i];
  516.                
  517.                 if (j < i)
  518.                     _children[j] = at;
  519.                
  520.                 if (at._type == RegexNode.Concatenate && ((at._options & RegexOptions.RightToLeft) == (_options & RegexOptions.RightToLeft))) {
  521.                     for (int k = 0; k < at._children.Count; k++)
  522.                         ((RegexNode)at._children[k])._next = this;
  523.                    
  524.                     _children.InsertRange(i + 1, at._children);
  525.                     j--;
  526.                 }
  527.                 else if (at._type == RegexNode.Multi || at._type == RegexNode.One) {
  528.                     // Cannot merge strings if L or I options differ
  529.                     optionsAt = at._options & (RegexOptions.RightToLeft | RegexOptions.IgnoreCase);
  530.                    
  531.                     if (!wasLastString || optionsLast != optionsAt) {
  532.                         wasLastString = true;
  533.                         optionsLast = optionsAt;
  534.                         continue;
  535.                     }
  536.                    
  537.                     prev = (RegexNode)_children[--j];
  538.                    
  539.                     if (prev._type == RegexNode.One) {
  540.                         prev._type = RegexNode.Multi;
  541.                         prev._str = Convert.ToString(prev._ch, CultureInfo.InvariantCulture);
  542.                     }
  543.                    
  544.                     if ((optionsAt & RegexOptions.RightToLeft) == 0) {
  545.                         if (at._type == RegexNode.One)
  546.                             prev._str += at._ch.ToString();
  547.                         else
  548.                             prev._str += at._str;
  549.                     }
  550.                     else {
  551.                         if (at._type == RegexNode.One)
  552.                             prev._str = at._ch.ToString() + prev._str;
  553.                         else
  554.                             prev._str = at._str + prev._str;
  555.                     }
  556.                    
  557.                 }
  558.                 else if (at._type == RegexNode.Empty) {
  559.                     j--;
  560.                 }
  561.                 else {
  562.                     wasLastString = false;
  563.                 }
  564.             }
  565.            
  566.             if (j < i)
  567.                 _children.RemoveRange(j, i - j);
  568.            
  569.             return StripEnation(RegexNode.Empty);
  570.         }
  571.        
  572.         internal RegexNode MakeQuantifier(bool lazy, int min, int max)
  573.         {
  574.             RegexNode result;
  575.            
  576.             if (min == 0 && max == 0)
  577.                 return new RegexNode(RegexNode.Empty, _options);
  578.            
  579.             if (min == 1 && max == 1)
  580.                 return this;
  581.            
  582.             switch (_type) {
  583.                 case RegexNode.One:
  584.                 case RegexNode.Notone:
  585.                 case RegexNode.Set:
  586.                    
  587.                     MakeRep(lazy ? RegexNode.Onelazy : RegexNode.Oneloop, min, max);
  588.                     return this;
  589.                 default:
  590.                    
  591.                     result = new RegexNode(lazy ? RegexNode.Lazyloop : RegexNode.Loop, _options, min, max);
  592.                     result.AddChild(this);
  593.                     return result;
  594.             }
  595.         }
  596.        
  597.         internal void AddChild(RegexNode newChild)
  598.         {
  599.             RegexNode reducedChild;
  600.            
  601.             if (_children == null)
  602.                 _children = new ArrayList(4);
  603.            
  604.             reducedChild = newChild.Reduce();
  605.            
  606.             _children.Add(reducedChild);
  607.             reducedChild._next = this;
  608.         }
  609.         internal RegexNode Child(int i)
  610.         {
  611.             return (RegexNode)_children[i];
  612.         }
  613.        
  614.         internal int ChildCount()
  615.         {
  616.             return _children == null ? 0 : _children.Count;
  617.         }
  618.        
  619.         internal int Type()
  620.         {
  621.             return _type;
  622.         }
  623.        
  624.         #if DBG
  625.         static internal string[] TypeStr = new string[] {"Onerep", "Notonerep", "Setrep", "Oneloop", "Notoneloop", "Setloop", "Onelazy", "Notonelazy", "Setlazy", "One",
  626.         "Notone", "Set", "Multi", "Ref", "Bol", "Eol", "Boundary", "Nonboundary", "ECMABoundary", "NonECMABoundary",
  627.         "Beginning", "Start", "EndZ", "End", "Nothing", "Empty", "Alternate", "Concatenate", "Loop", "Lazyloop",
  628.         "Capture", "Group", "Require", "Prevent", "Greedy", "Testref", "Testgroup"};
  629.        
  630.         internal string Description()
  631.         {
  632.            
  633.             StringBuilder ArgSb = new StringBuilder();
  634.            
  635.             ArgSb.Append(TypeStr[_type]);
  636.            
  637.             if ((_options & RegexOptions.ExplicitCapture) != 0)
  638.                 ArgSb.Append("-C");
  639.             if ((_options & RegexOptions.IgnoreCase) != 0)
  640.                 ArgSb.Append("-I");
  641.             if ((_options & RegexOptions.RightToLeft) != 0)
  642.                 ArgSb.Append("-L");
  643.             if ((_options & RegexOptions.Multiline) != 0)
  644.                 ArgSb.Append("-M");
  645.             if ((_options & RegexOptions.Singleline) != 0)
  646.                 ArgSb.Append("-S");
  647.             if ((_options & RegexOptions.IgnorePatternWhitespace) != 0)
  648.                 ArgSb.Append("-X");
  649.             if ((_options & RegexOptions.ECMAScript) != 0)
  650.                 ArgSb.Append("-E");
  651.            
  652.             switch (_type) {
  653.                 case Oneloop:
  654.                 case Notoneloop:
  655.                 case Onelazy:
  656.                 case Notonelazy:
  657.                 case One:
  658.                 case Notone:
  659.                     ArgSb.Append("(Ch = " + RegexCharClass.CharDescription(_ch) + ")");
  660.                     break;
  661.                 case Capture:
  662.                     ArgSb.Append("(index = " + _m.ToString(CultureInfo.InvariantCulture) + ", unindex = " + _n.ToString(CultureInfo.InvariantCulture) + ")");
  663.                     break;
  664.                 case Ref:
  665.                 case Testref:
  666.                     ArgSb.Append("(index = " + _m.ToString(CultureInfo.InvariantCulture) + ")");
  667.                     break;
  668.                 case Multi:
  669.                     ArgSb.Append("(String = " + _str + ")");
  670.                     break;
  671.                 case Set:
  672.                 case Setloop:
  673.                 case Setlazy:
  674.                     ArgSb.Append("(Set = " + RegexCharClass.SetDescription(_str) + ")");
  675.                     break;
  676.             }
  677.            
  678.             switch (_type) {
  679.                 case Oneloop:
  680.                 case Notoneloop:
  681.                 case Onelazy:
  682.                 case Notonelazy:
  683.                 case Setloop:
  684.                 case Setlazy:
  685.                 case Loop:
  686.                 case Lazyloop:
  687.                     ArgSb.Append("(Min = " + _m.ToString(CultureInfo.InvariantCulture) + ", Max = " + (_n == Int32.MaxValue ? "inf" : Convert.ToString(_n, CultureInfo.InvariantCulture)) + ")");
  688.                     break;
  689.             }
  690.            
  691.             return ArgSb.ToString();
  692.         }
  693.        
  694.         internal const string Space = " ";
  695.        
  696.         internal void Dump()
  697.         {
  698.             ArrayList Stack = new ArrayList();
  699.             RegexNode CurNode;
  700.             int CurChild;
  701.            
  702.             CurNode = this;
  703.             CurChild = 0;
  704.            
  705.             Debug.WriteLine(CurNode.Description());
  706.            
  707.             for (;;) {
  708.                 if (CurNode._children != null && CurChild < CurNode._children.Count) {
  709.                     Stack.Add(CurChild + 1);
  710.                     CurNode = (RegexNode)CurNode._children[CurChild];
  711.                     CurChild = 0;
  712.                    
  713.                     int Depth = Stack.Count;
  714.                     if (Depth > 32)
  715.                         Depth = 32;
  716.                    
  717.                     Debug.WriteLine(Space.Substring(0, Depth) + CurNode.Description());
  718.                 }
  719.                 else {
  720.                     if (Stack.Count == 0)
  721.                         break;
  722.                    
  723.                     CurChild = (Int32)Stack[Stack.Count - 1];
  724.                     Stack.RemoveAt(Stack.Count - 1);
  725.                     CurNode = CurNode._next;
  726.                 }
  727.             }
  728.         }
  729.         #endif
  730.        
  731.     }
  732.    
  733. }

Developer Fusion