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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="RegexInterpreter.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 RegexInterpreter class is internal to the RegularExpression package.
  16. // It executes a block of regular expression codes while consuming
  17. // input.
  18. namespace System.Text.RegularExpressions
  19. {
  20.    
  21.     using System.Collections;
  22.     using System.Diagnostics;
  23.     using System.Globalization;
  24.    
  25.     internal sealed class RegexInterpreter : RegexRunner
  26.     {
  27.         internal int runoperator;
  28.         internal int[] runcodes;
  29.         internal int runcodepos;
  30.         internal string[] runstrings;
  31.         internal RegexCode runcode;
  32.         internal RegexPrefix runfcPrefix;
  33.         internal RegexBoyerMoore runbmPrefix;
  34.         internal int runanchors;
  35.         internal bool runrtl;
  36.         internal bool runci;
  37.         internal CultureInfo runculture;
  38.        
  39.         internal RegexInterpreter(RegexCode code, CultureInfo culture)
  40.         {
  41.             runcode = code;
  42.             runcodes = code._codes;
  43.             runstrings = code._strings;
  44.             runfcPrefix = code._fcPrefix;
  45.             runbmPrefix = code._bmPrefix;
  46.             runanchors = code._anchors;
  47.             runculture = culture;
  48.         }
  49.        
  50.         protected override void InitTrackCount()
  51.         {
  52.             runtrackcount = runcode._trackcount;
  53.         }
  54.        
  55.         private void Advance()
  56.         {
  57.             Advance(0);
  58.         }
  59.        
  60.         private void Advance(int i)
  61.         {
  62.             runcodepos += (i + 1);
  63.             SetOperator(runcodes[runcodepos]);
  64.         }
  65.        
  66.         private void Goto(int newpos)
  67.         {
  68.             // when branching backward, ensure storage
  69.             if (newpos < runcodepos)
  70.                 EnsureStorage();
  71.            
  72.             SetOperator(runcodes[newpos]);
  73.             runcodepos = newpos;
  74.         }
  75.        
  76.         private void Textto(int newpos)
  77.         {
  78.             runtextpos = newpos;
  79.         }
  80.        
  81.         private void Trackto(int newpos)
  82.         {
  83.             runtrackpos = runtrack.Length - newpos;
  84.         }
  85.        
  86.         private int Textstart()
  87.         {
  88.             return runtextstart;
  89.         }
  90.        
  91.         private int Textpos()
  92.         {
  93.             return runtextpos;
  94.         }
  95.        
  96.         // push onto the backtracking stack
  97.         private int Trackpos()
  98.         {
  99.             return runtrack.Length - runtrackpos;
  100.         }
  101.        
  102.         private void TrackPush()
  103.         {
  104.             runtrack[--runtrackpos] = runcodepos;
  105.         }
  106.        
  107.         private void TrackPush(int I1)
  108.         {
  109.             runtrack[--runtrackpos] = I1;
  110.             runtrack[--runtrackpos] = runcodepos;
  111.         }
  112.        
  113.         private void TrackPush(int I1, int I2)
  114.         {
  115.             runtrack[--runtrackpos] = I1;
  116.             runtrack[--runtrackpos] = I2;
  117.             runtrack[--runtrackpos] = runcodepos;
  118.         }
  119.        
  120.         private void TrackPush(int I1, int I2, int I3)
  121.         {
  122.             runtrack[--runtrackpos] = I1;
  123.             runtrack[--runtrackpos] = I2;
  124.             runtrack[--runtrackpos] = I3;
  125.             runtrack[--runtrackpos] = runcodepos;
  126.         }
  127.        
  128.         private void TrackPush2(int I1)
  129.         {
  130.             runtrack[--runtrackpos] = I1;
  131.             runtrack[--runtrackpos] = -runcodepos;
  132.         }
  133.        
  134.         private void TrackPush2(int I1, int I2)
  135.         {
  136.             runtrack[--runtrackpos] = I1;
  137.             runtrack[--runtrackpos] = I2;
  138.             runtrack[--runtrackpos] = -runcodepos;
  139.         }
  140.        
  141.         private void Backtrack()
  142.         {
  143.             int newpos = runtrack[runtrackpos++];
  144.             #if DBG
  145.             if (runmatch.Debug) {
  146.                 if (newpos < 0)
  147.                     Debug.WriteLine(" Backtracking (back2) to code position " + (-newpos));
  148.                 else
  149.                     Debug.WriteLine(" Backtracking to code position " + newpos);
  150.             }
  151.             #endif
  152.            
  153.             if (newpos < 0) {
  154.                 newpos = -newpos;
  155.                 SetOperator(runcodes[newpos] | RegexCode.Back2);
  156.             }
  157.             else {
  158.                 SetOperator(runcodes[newpos] | RegexCode.Back);
  159.             }
  160.            
  161.             // When branching backward, ensure storage
  162.             if (newpos < runcodepos)
  163.                 EnsureStorage();
  164.            
  165.             runcodepos = newpos;
  166.         }
  167.        
  168.         private void SetOperator(int op)
  169.         {
  170.             runci = (0 != (op & RegexCode.Ci));
  171.             runrtl = (0 != (op & RegexCode.Rtl));
  172.             runoperator = op & ~(RegexCode.Rtl | RegexCode.Ci);
  173.         }
  174.        
  175.         private void TrackPop()
  176.         {
  177.             runtrackpos++;
  178.         }
  179.        
  180.         // pop framesize items from the backtracking stack
  181.         private void TrackPop(int framesize)
  182.         {
  183.             runtrackpos += framesize;
  184.         }
  185.        
  186.         // Technically we are actually peeking at items already popped. So if you want to
  187.         // get and pop the top item from the stack, you do
  188.         // TrackPop();
  189.         // TrackPeek();
  190.         private int TrackPeek()
  191.         {
  192.             return runtrack[runtrackpos - 1];
  193.         }
  194.        
  195.         // get the ith element down on the backtracking stack
  196.         private int TrackPeek(int i)
  197.         {
  198.             return runtrack[runtrackpos - i - 1];
  199.         }
  200.        
  201.         // Push onto the grouping stack
  202.         private void StackPush(int I1)
  203.         {
  204.             runstack[--runstackpos] = I1;
  205.         }
  206.        
  207.         private void StackPush(int I1, int I2)
  208.         {
  209.             runstack[--runstackpos] = I1;
  210.             runstack[--runstackpos] = I2;
  211.         }
  212.        
  213.         private void StackPop()
  214.         {
  215.             runstackpos++;
  216.         }
  217.        
  218.         // pop framesize items from the grouping stack
  219.         private void StackPop(int framesize)
  220.         {
  221.             runstackpos += framesize;
  222.         }
  223.        
  224.         // Technically we are actually peeking at items already popped. So if you want to
  225.         // get and pop the top item from the stack, you do
  226.         // StackPop();
  227.         // StackPeek();
  228.         private int StackPeek()
  229.         {
  230.             return runstack[runstackpos - 1];
  231.         }
  232.        
  233.         // get the ith element down on the grouping stack
  234.         private int StackPeek(int i)
  235.         {
  236.             return runstack[runstackpos - i - 1];
  237.         }
  238.        
  239.         private int Operator()
  240.         {
  241.             return runoperator;
  242.         }
  243.        
  244.         private int Operand(int i)
  245.         {
  246.             return runcodes[runcodepos + i + 1];
  247.         }
  248.        
  249.         private int Leftchars()
  250.         {
  251.             return runtextpos - runtextbeg;
  252.         }
  253.        
  254.         private int Rightchars()
  255.         {
  256.             return runtextend - runtextpos;
  257.         }
  258.        
  259.         private int Bump()
  260.         {
  261.             return runrtl ? -1 : 1;
  262.         }
  263.        
  264.         private int Forwardchars()
  265.         {
  266.             return runrtl ? runtextpos - runtextbeg : runtextend - runtextpos;
  267.         }
  268.        
  269.         private char Forwardcharnext()
  270.         {
  271.             char ch = (runrtl ? runtext[--runtextpos] : runtext[runtextpos++]);
  272.            
  273.             return (runci ? Char.ToLower(ch, runculture) : ch);
  274.         }
  275.        
  276.         private bool Stringmatch(string str)
  277.         {
  278.             int c;
  279.             int pos;
  280.            
  281.             if (!runrtl) {
  282.                 if (runtextend - runtextpos < (c = str.Length))
  283.                     return false;
  284.                
  285.                 pos = runtextpos + c;
  286.             }
  287.             else {
  288.                 if (runtextpos - runtextbeg < (c = str.Length))
  289.                     return false;
  290.                
  291.                 pos = runtextpos;
  292.             }
  293.            
  294.             if (!runci) {
  295.                 while (c != 0)
  296.                     if (str[--c] != runtext[--pos])
  297.                         return false;
  298.             }
  299.             else {
  300.                 while (c != 0)
  301.                     if (str[--c] != Char.ToLower(runtext[--pos], runculture))
  302.                         return false;
  303.             }
  304.            
  305.             if (!runrtl) {
  306.                 pos += str.Length;
  307.             }
  308.            
  309.             runtextpos = pos;
  310.            
  311.             return true;
  312.         }
  313.        
  314.         private bool Refmatch(int index, int len)
  315.         {
  316.             int c;
  317.             int pos;
  318.             int cmpos;
  319.            
  320.             if (!runrtl) {
  321.                 if (runtextend - runtextpos < len)
  322.                     return false;
  323.                
  324.                 pos = runtextpos + len;
  325.             }
  326.             else {
  327.                 if (runtextpos - runtextbeg < len)
  328.                     return false;
  329.                
  330.                 pos = runtextpos;
  331.             }
  332.             cmpos = index + len;
  333.            
  334.             c = len;
  335.            
  336.             if (!runci) {
  337.                 while (c-- != 0)
  338.                     if (runtext[--cmpos] != runtext[--pos])
  339.                         return false;
  340.             }
  341.             else {
  342.                 while (c-- != 0)
  343.                     if (Char.ToLower(runtext[--cmpos], runculture) != Char.ToLower(runtext[--pos], runculture))
  344.                         return false;
  345.             }
  346.            
  347.             if (!runrtl) {
  348.                 pos += len;
  349.             }
  350.            
  351.             runtextpos = pos;
  352.            
  353.             return true;
  354.         }
  355.        
  356.         private void Backwardnext()
  357.         {
  358.             runtextpos += runrtl ? 1 : -1;
  359.         }
  360.        
  361.         private char CharAt(int j)
  362.         {
  363.             return runtext[j];
  364.         }
  365.        
  366.         protected override bool FindFirstChar()
  367.         {
  368.             int i;
  369.             string set;
  370.            
  371.             if (0 != (runanchors & (RegexFCD.Beginning | RegexFCD.Start | RegexFCD.EndZ | RegexFCD.End))) {
  372.                 if (!runcode._rightToLeft) {
  373.                     if ((0 != (runanchors & RegexFCD.Beginning) && runtextpos > runtextbeg) || (0 != (runanchors & RegexFCD.Start) && runtextpos > runtextstart)) {
  374.                         runtextpos = runtextend;
  375.                         return false;
  376.                     }
  377.                     if (0 != (runanchors & RegexFCD.EndZ) && runtextpos < runtextend - 1) {
  378.                         runtextpos = runtextend - 1;
  379.                     }
  380.                     else if (0 != (runanchors & RegexFCD.End) && runtextpos < runtextend) {
  381.                         runtextpos = runtextend;
  382.                     }
  383.                 }
  384.                 else {
  385.                     if ((0 != (runanchors & RegexFCD.End) && runtextpos < runtextend) || (0 != (runanchors & RegexFCD.EndZ) && (runtextpos < runtextend - 1 || (runtextpos == runtextend - 1 && CharAt(runtextpos) != '\n'))) || (0 != (runanchors & RegexFCD.Start) && runtextpos < runtextstart)) {
  386.                         runtextpos = runtextbeg;
  387.                         return false;
  388.                     }
  389.                     if (0 != (runanchors & RegexFCD.Beginning) && runtextpos > runtextbeg) {
  390.                         runtextpos = runtextbeg;
  391.                     }
  392.                 }
  393.                
  394.                 if (runbmPrefix != null) {
  395.                     return runbmPrefix.IsMatch(runtext, runtextpos, runtextbeg, runtextend);
  396.                 }
  397.             }
  398.             else if (runbmPrefix != null) {
  399.                 runtextpos = runbmPrefix.Scan(runtext, runtextpos, runtextbeg, runtextend);
  400.                
  401.                 if (runtextpos == -1) {
  402.                     runtextpos = (runcode._rightToLeft ? runtextbeg : runtextend);
  403.                     return false;
  404.                 }
  405.                
  406.                 return true;
  407.             }
  408.            
  409.             if (runfcPrefix == null)
  410.                 return true;
  411.            
  412.             runrtl = runcode._rightToLeft;
  413.             runci = runfcPrefix.CaseInsensitive;
  414.             set = runfcPrefix.Prefix;
  415.            
  416.             if (RegexCharClass.IsSingleton(set)) {
  417.                 char ch = RegexCharClass.SingletonChar(set);
  418.                
  419.                 for (i = Forwardchars(); i > 0; i--) {
  420.                     if (ch == Forwardcharnext()) {
  421.                         Backwardnext();
  422.                         return true;
  423.                     }
  424.                 }
  425.             }
  426.             else {
  427.                 for (i = Forwardchars(); i > 0; i--) {
  428.                     if (RegexCharClass.CharInClass(Forwardcharnext(), set)) {
  429.                         Backwardnext();
  430.                         return true;
  431.                     }
  432.                 }
  433.             }
  434.             return false;
  435.         }
  436.        
  437.         protected override void Go()
  438.         {
  439.             Goto(0);
  440.            
  441.             for (;;) {
  442.                 #if DBG
  443.                 if (runmatch.Debug) {
  444.                     DumpState();
  445.                 }
  446.                 #endif
  447.                
  448.                 switch (Operator()) {
  449.                     case RegexCode.Stop:
  450.                         return;
  451.                     case RegexCode.Nothing:
  452.                        
  453.                         break;
  454.                     case RegexCode.Goto:
  455.                        
  456.                         Goto(Operand(0));
  457.                         continue;
  458.                     case RegexCode.Testref:
  459.                        
  460.                         if (!IsMatched(Operand(0)))
  461.                             break;
  462.                         Advance(1);
  463.                         continue;
  464.                     case RegexCode.Lazybranch:
  465.                        
  466.                         TrackPush(Textpos());
  467.                         Advance(1);
  468.                         continue;
  469.                     case RegexCode.Lazybranch | RegexCode.Back:
  470.                        
  471.                         TrackPop();
  472.                         Textto(TrackPeek());
  473.                         Goto(Operand(0));
  474.                         continue;
  475.                     case RegexCode.Setmark:
  476.                        
  477.                         StackPush(Textpos());
  478.                         TrackPush();
  479.                         Advance();
  480.                         continue;
  481.                     case RegexCode.Nullmark:
  482.                        
  483.                         StackPush(-1);
  484.                         TrackPush();
  485.                         Advance();
  486.                         continue;
  487.                     case RegexCode.Setmark | RegexCode.Back:
  488.                     case RegexCode.Nullmark | RegexCode.Back:
  489.                        
  490.                         StackPop();
  491.                         break;
  492.                     case RegexCode.Getmark:
  493.                        
  494.                         StackPop();
  495.                         TrackPush(StackPeek());
  496.                         Textto(StackPeek());
  497.                         Advance();
  498.                         continue;
  499.                     case RegexCode.Getmark | RegexCode.Back:
  500.                        
  501.                         TrackPop();
  502.                         StackPush(TrackPeek());
  503.                         break;
  504.                     case RegexCode.Capturemark:
  505.                        
  506.                         if (Operand(1) != -1 && !IsMatched(Operand(1)))
  507.                             break;
  508.                         StackPop();
  509.                         if (Operand(1) != -1)
  510.                             TransferCapture(Operand(0), Operand(1), StackPeek(), Textpos());
  511.                         else
  512.                             Capture(Operand(0), StackPeek(), Textpos());
  513.                         TrackPush(StackPeek());
  514.                        
  515.                         Advance(2);
  516.                        
  517.                         continue;
  518.                     case RegexCode.Capturemark | RegexCode.Back:
  519.                        
  520.                         TrackPop();
  521.                         StackPush(TrackPeek());
  522.                         Uncapture();
  523.                         if (Operand(0) != -1 && Operand(1) != -1)
  524.                             Uncapture();
  525.                        
  526.                         break;
  527.                     case RegexCode.Branchmark:
  528.                        
  529.                        
  530.                         {
  531.                             int matched;
  532.                             StackPop();
  533.                            
  534.                             matched = Textpos() - StackPeek();
  535.                            
  536.                             if (matched != 0) {
  537.                                 // Nonempty match -> loop now
  538.                                 TrackPush(StackPeek(), Textpos());
  539.                                 // Save old mark, textpos
  540.                                 StackPush(Textpos());
  541.                                 // Make new mark
  542.                                 Goto(Operand(0));
  543.                                 // Loop
  544.                             }
  545.                             else {
  546.                                 // Empty match -> straight now
  547.                                 TrackPush2(StackPeek());
  548.                                 // Save old mark
  549.                                 Advance(1);
  550.                                 // Straight
  551.                             }
  552.                             continue;
  553.                         }
  554.                         break;
  555.                     case RegexCode.Branchmark | RegexCode.Back:
  556.                        
  557.                         TrackPop(2);
  558.                         StackPop();
  559.                         Textto(TrackPeek(1));
  560.                         // Recall position
  561.                         TrackPush2(TrackPeek());
  562.                         // Save old mark
  563.                         Advance(1);
  564.                         // Straight
  565.                         continue;
  566.                     case RegexCode.Branchmark | RegexCode.Back2:
  567.                        
  568.                         TrackPop();
  569.                         StackPush(TrackPeek());
  570.                         // Recall old mark
  571.                         break;
  572.                     case RegexCode.Lazybranchmark:
  573.                         // Backtrack
  574.                        
  575.                         {
  576.                             // We hit this the first time through a lazy loop and after each
  577.                             // successful match of the inner expression. It simply continues
  578.                             // on and doesn't loop.
  579.                             StackPop();
  580.                            
  581.                             int oldMarkPos = StackPeek();
  582.                            
  583.                             if (Textpos() != oldMarkPos) {
  584.                                 // Nonempty match -> try to loop again by going to 'back' state
  585.                                 if (oldMarkPos != -1)
  586.                                     TrackPush(oldMarkPos, Textpos());
  587.                                 else
  588.                                     // Save old mark, textpos
  589.                                     TrackPush(Textpos(), Textpos());
  590.                             }
  591.                             else {
  592.                                 // The inner expression found an empty match, so we'll go directly to 'back2' if we
  593.                                 // backtrack. In this case, we need to push something on the stack, since back2 pops.
  594.                                 // However, in the case of ()+? or similar, this empty match may be legitimate, so push the text
  595.                                 // position associated with that empty match.
  596.                                 StackPush(oldMarkPos);
  597.                                
  598.                                 TrackPush2(StackPeek());
  599.                                 // Save old mark
  600.                             }
  601.                             Advance(1);
  602.                             continue;
  603.                         }
  604.                         break;
  605.                     case RegexCode.Lazybranchmark | RegexCode.Back:
  606.                        
  607.                        
  608.                         {
  609.                             // After the first time, Lazybranchmark | RegexCode.Back occurs
  610.                             // with each iteration of the loop, and therefore with every attempted
  611.                             // match of the inner expression. We'll try to match the inner expression,
  612.                             // then go back to Lazybranchmark if successful. If the inner expression
  613.                             // failes, we go to Lazybranchmark | RegexCode.Back2
  614.                             int pos;
  615.                            
  616.                             TrackPop(2);
  617.                             pos = TrackPeek(1);
  618.                             TrackPush2(TrackPeek());
  619.                             // Save old mark
  620.                             StackPush(pos);
  621.                             // Make new mark
  622.                             Textto(pos);
  623.                             // Recall position
  624.                             Goto(Operand(0));
  625.                             // Loop
  626.                             continue;
  627.                         }
  628.                         break;
  629.                     case RegexCode.Lazybranchmark | RegexCode.Back2:
  630.                        
  631.                         // The lazy loop has failed. We'll do a true backtrack and
  632.                         // start over before the lazy loop.
  633.                         StackPop();
  634.                         TrackPop();
  635.                         StackPush(TrackPeek());
  636.                         // Recall old mark
  637.                         break;
  638.                     case RegexCode.Setcount:
  639.                        
  640.                         StackPush(Textpos(), Operand(0));
  641.                         TrackPush();
  642.                         Advance(1);
  643.                         continue;
  644.                     case RegexCode.Nullcount:
  645.                        
  646.                         StackPush(-1, Operand(0));
  647.                         TrackPush();
  648.                         Advance(1);
  649.                         continue;
  650.                     case RegexCode.Setcount | RegexCode.Back:
  651.                        
  652.                         StackPop(2);
  653.                         break;
  654.                     case RegexCode.Nullcount | RegexCode.Back:
  655.                        
  656.                         StackPop(2);
  657.                         break;
  658.                     case RegexCode.Branchcount:
  659.                        
  660.                         // StackPush:
  661.                         // 0: Mark
  662.                         // 1: Count
  663.                        
  664.                         {
  665.                             StackPop(2);
  666.                             int mark = StackPeek();
  667.                             int count = StackPeek(1);
  668.                             int matched = Textpos() - mark;
  669.                            
  670.                             if (count >= Operand(1) || (matched == 0 && count >= 0)) {
  671.                                 // Max loops or empty match -> straight now
  672.                                 TrackPush2(mark, count);
  673.                                 // Save old mark, count
  674.                                 Advance(2);
  675.                                 // Straight
  676.                             }
  677.                             else {
  678.                                 // Nonempty match -> count+loop now
  679.                                 TrackPush(mark);
  680.                                 // remember mark
  681.                                 StackPush(Textpos(), count + 1);
  682.                                 // Make new mark, incr count
  683.                                 Goto(Operand(0));
  684.                                 // Loop
  685.                             }
  686.                             continue;
  687.                         }
  688.                         break;
  689.                     case RegexCode.Branchcount | RegexCode.Back:
  690.                        
  691.                         // TrackPush:
  692.                         // 0: Previous mark
  693.                         // StackPush:
  694.                         // 0: Mark (= current pos, discarded)
  695.                         // 1: Count
  696.                         TrackPop();
  697.                         StackPop(2);
  698.                         if (StackPeek(1) > 0) {
  699.                             // Positive -> can go straight
  700.                             Textto(StackPeek());
  701.                             // Zap to mark
  702.                             TrackPush2(TrackPeek(), StackPeek(1) - 1);
  703.                             // Save old mark, old count
  704.                             Advance(2);
  705.                             // Straight
  706.                             continue;
  707.                         }
  708.                         StackPush(TrackPeek(), StackPeek(1) - 1);
  709.                         // recall old mark, old count
  710.                         break;
  711.                     case RegexCode.Branchcount | RegexCode.Back2:
  712.                        
  713.                         // TrackPush:
  714.                         // 0: Previous mark
  715.                         // 1: Previous count
  716.                         TrackPop(2);
  717.                         StackPush(TrackPeek(), TrackPeek(1));
  718.                         // Recall old mark, old count
  719.                         break;
  720.                     case RegexCode.Lazybranchcount:
  721.                         // Backtrack
  722.                        
  723.                         // StackPush:
  724.                         // 0: Mark
  725.                         // 1: Count
  726.                        
  727.                         {
  728.                             StackPop(2);
  729.                             int mark = StackPeek();
  730.                             int count = StackPeek(1);
  731.                            
  732.                             if (count < 0) {
  733.                                 // Negative count -> loop now
  734.                                 TrackPush2(mark);
  735.                                 // Save old mark
  736.                                 StackPush(Textpos(), count + 1);
  737.                                 // Make new mark, incr count
  738.                                 Goto(Operand(0));
  739.                                 // Loop
  740.                             }
  741.                             else {
  742.                                 // Nonneg count -> straight now
  743.                                 TrackPush(mark, count, Textpos());
  744.                                 // Save mark, count, position
  745.                                 Advance(2);
  746.                                 // Straight
  747.                             }
  748.                             continue;
  749.                         }
  750.                         break;
  751.                     case RegexCode.Lazybranchcount | RegexCode.Back:
  752.                        
  753.                         // TrackPush:
  754.                         // 0: Mark
  755.                         // 1: Count
  756.                         // 2: Textpos
  757.                        
  758.                         {
  759.                             TrackPop(3);
  760.                             int mark = TrackPeek();
  761.                             int textpos = TrackPeek(2);
  762.                             if (TrackPeek(1) <= Operand(1) && textpos != mark) {
  763.                                 // Under limit and not empty match -> loop
  764.                                 Textto(textpos);
  765.                                 // Recall position
  766.                                 StackPush(textpos, TrackPeek(1) + 1);
  767.                                 // Make new mark, incr count
  768.                                 TrackPush2(mark);
  769.                                 // Save old mark
  770.                                 Goto(Operand(0));
  771.                                 // Loop
  772.                                 continue;
  773.                             }
  774.                             else {
  775.                                 // Max loops or empty match -> backtrack
  776.                                 StackPush(TrackPeek(), TrackPeek(1));
  777.                                 // Recall old mark, count
  778.                                 break;
  779.                                 // backtrack
  780.                             }
  781.                         }
  782.                         break;
  783.                     case RegexCode.Lazybranchcount | RegexCode.Back2:
  784.                        
  785.                         // TrackPush:
  786.                         // 0: Previous mark
  787.                         // StackPush:
  788.                         // 0: Mark (== current pos, discarded)
  789.                         // 1: Count
  790.                         TrackPop();
  791.                         StackPop(2);
  792.                         StackPush(TrackPeek(), StackPeek(1) - 1);
  793.                         // Recall old mark, count
  794.                         break;
  795.                     case RegexCode.Setjump:
  796.                         // Backtrack
  797.                         StackPush(Trackpos(), Crawlpos());
  798.                         TrackPush();
  799.                         Advance();
  800.                         continue;
  801.                     case RegexCode.Setjump | RegexCode.Back:
  802.                        
  803.                         StackPop(2);
  804.                         break;
  805.                     case RegexCode.Backjump:
  806.                        
  807.                         // StackPush:
  808.                         // 0: Saved trackpos
  809.                         // 1: Crawlpos
  810.                         StackPop(2);
  811.                         Trackto(StackPeek());
  812.                        
  813.                         while (Crawlpos() != StackPeek(1))
  814.                             Uncapture();
  815.                        
  816.                         break;
  817.                     case RegexCode.Forejump:
  818.                        
  819.                         // StackPush:
  820.                         // 0: Saved trackpos
  821.                         // 1: Crawlpos
  822.                         StackPop(2);
  823.                         Trackto(StackPeek());
  824.                         TrackPush(StackPeek(1));
  825.                         Advance();
  826.                         continue;
  827.                     case RegexCode.Forejump | RegexCode.Back:
  828.                        
  829.                         // TrackPush:
  830.                         // 0: Crawlpos
  831.                         TrackPop();
  832.                        
  833.                         while (Crawlpos() != TrackPeek())
  834.                             Uncapture();
  835.                        
  836.                         break;
  837.                     case RegexCode.Bol:
  838.                        
  839.                         if (Leftchars() > 0 && CharAt(Textpos() - 1) != '\n')
  840.                             break;
  841.                         Advance();
  842.                         continue;
  843.                     case RegexCode.Eol:
  844.                        
  845.                         if (Rightchars() > 0 && CharAt(Textpos()) != '\n')
  846.                             break;
  847.                         Advance();
  848.                         continue;
  849.                     case RegexCode.Boundary:
  850.                        
  851.                         if (!IsBoundary(Textpos(), runtextbeg, runtextend))
  852.                             break;
  853.                         Advance();
  854.                         continue;
  855.                     case RegexCode.Nonboundary:
  856.                        
  857.                         if (IsBoundary(Textpos(), runtextbeg, runtextend))
  858.                             break;
  859.                         Advance();
  860.                         continue;
  861.                     case RegexCode.ECMABoundary:
  862.                        
  863.                         if (!IsECMABoundary(Textpos(), runtextbeg, runtextend))
  864.                             break;
  865.                         Advance();
  866.                         continue;
  867.                     case RegexCode.NonECMABoundary:
  868.                        
  869.                         if (IsECMABoundary(Textpos(), runtextbeg, runtextend))
  870.                             break;
  871.                         Advance();
  872.                         continue;
  873.                     case RegexCode.Beginning:
  874.                        
  875.                         if (Leftchars() > 0)
  876.                             break;
  877.                         Advance();
  878.                         continue;
  879.                     case RegexCode.Start:
  880.                        
  881.                         if (Textpos() != Textstart())
  882.                             break;
  883.                         Advance();
  884.                         continue;
  885.                     case RegexCode.EndZ:
  886.                        
  887.                         if (Rightchars() > 1 || Rightchars() == 1 && CharAt(Textpos()) != '\n')
  888.                             break;
  889.                         Advance();
  890.                         continue;
  891.                     case RegexCode.End:
  892.                        
  893.                         if (Rightchars() > 0)
  894.                             break;
  895.                         Advance();
  896.                         continue;
  897.                     case RegexCode.One:
  898.                        
  899.                         if (Forwardchars() < 1 || Forwardcharnext() != (char)Operand(0))
  900.                             break;
  901.                        
  902.                         Advance(1);
  903.                         continue;
  904.                     case RegexCode.Notone:
  905.                        
  906.                         if (Forwardchars() < 1 || Forwardcharnext() == (char)Operand(0))
  907.                             break;
  908.                        
  909.                         Advance(1);
  910.                         continue;
  911.                     case RegexCode.Set:
  912.                        
  913.                         if (Forwardchars() < 1 || !RegexCharClass.CharInClass(Forwardcharnext(), runstrings[Operand(0)]))
  914.                             break;
  915.                        
  916.                         Advance(1);
  917.                         continue;
  918.                     case RegexCode.Multi:
  919.                        
  920.                        
  921.                         {
  922.                             if (!Stringmatch(runstrings[Operand(0)]))
  923.                                 break;
  924.                            
  925.                             Advance(1);
  926.                             continue;
  927.                         }
  928.                         break;
  929.                     case RegexCode.Ref:
  930.                        
  931.                        
  932.                         {
  933.                             int capnum = Operand(0);
  934.                            
  935.                             if (IsMatched(capnum)) {
  936.                                 if (!Refmatch(MatchIndex(capnum), MatchLength(capnum)))
  937.                                     break;
  938.                             }
  939.                             else {
  940.                                 if ((runregex.roptions & RegexOptions.ECMAScript) == 0)
  941.                                     break;
  942.                             }
  943.                            
  944.                             Advance(1);
  945.                             continue;
  946.                         }
  947.                         break;
  948.                     case RegexCode.Onerep:
  949.                        
  950.                        
  951.                         {
  952.                             int c = Operand(1);
  953.                            
  954.                             if (Forwardchars() < c)
  955.                                 break;
  956.                            
  957.                             char ch = (char)Operand(0);
  958.                            
  959.                             while (c-- > 0)
  960.                                 if (Forwardcharnext() != ch)
  961.                                     goto BreakBackward;
  962.                            
  963.                             Advance(2);
  964.                             continue;
  965.                         }
  966.                         break;
  967.                     case RegexCode.Notonerep:
  968.                        
  969.                        
  970.                         {
  971.                             int c = Operand(1);
  972.                            
  973.                             if (Forwardchars() < c)
  974.                                 break;
  975.                            
  976.                             char ch = (char)Operand(0);
  977.                            
  978.                             while (c-- > 0)
  979.                                 if (Forwardcharnext() == ch)
  980.                                     goto BreakBackward;
  981.                            
  982.                             Advance(2);
  983.                             continue;
  984.                         }
  985.                         break;
  986.                     case RegexCode.Setrep:
  987.                        
  988.                        
  989.                         {
  990.                             int c = Operand(1);
  991.                            
  992.                             if (Forwardchars() < c)
  993.                                 break;
  994.                            
  995.                             string set = runstrings[Operand(0)];
  996.                            
  997.                             while (c-- > 0)
  998.                                 if (!RegexCharClass.CharInClass(Forwardcharnext(), set))
  999.                                     goto BreakBackward;
  1000.                            
  1001.                             Advance(2);
  1002.                             continue;
  1003.                         }
  1004.                         break;
  1005.                     case RegexCode.Oneloop:
  1006.                        
  1007.                        
  1008.                         {
  1009.                             int c = Operand(1);
  1010.                            
  1011.                             if (c > Forwardchars())
  1012.                                 c = Forwardchars();
  1013.                            
  1014.                             char ch = (char)Operand(0);
  1015.                             int i;
  1016.                            
  1017.                             for (i = c; i > 0; i--) {
  1018.                                 if (Forwardcharnext() != ch) {
  1019.                                     Backwardnext();
  1020.                                     break;
  1021.                                 }
  1022.                             }
  1023.                            
  1024.                             if (c > i)
  1025.                                 TrackPush(c - i - 1, Textpos() - Bump());
  1026.                            
  1027.                             Advance(2);
  1028.                             continue;
  1029.                         }
  1030.                         break;
  1031.                     case RegexCode.Notoneloop:
  1032.                        
  1033.                        
  1034.                         {
  1035.                             int c = Operand(1);
  1036.                            
  1037.                             if (c > Forwardchars())
  1038.                                 c = Forwardchars();
  1039.                            
  1040.                             char ch = (char)Operand(0);
  1041.                             int i;
  1042.                            
  1043.                             for (i = c; i > 0; i--) {
  1044.                                 if (Forwardcharnext() == ch) {
  1045.                                     Backwardnext();
  1046.                                     break;
  1047.                                 }
  1048.                             }
  1049.                            
  1050.                             if (c > i)
  1051.                                 TrackPush(c - i - 1, Textpos() - Bump());
  1052.                            
  1053.                             Advance(2);
  1054.                             continue;
  1055.                         }
  1056.                         break;
  1057.                     case RegexCode.Setloop:
  1058.                        
  1059.                        
  1060.                         {
  1061.                             int c = Operand(1);
  1062.                            
  1063.                             if (c > Forwardchars())
  1064.                                 c = Forwardchars();
  1065.                            
  1066.                             string set = runstrings[Operand(0)];
  1067.                             int i;
  1068.                            
  1069.                             for (i = c; i > 0; i--) {
  1070.                                 if (!RegexCharClass.CharInClass(Forwardcharnext(), set)) {
  1071.                                     Backwardnext();
  1072.                                     break;
  1073.                                 }
  1074.                             }
  1075.                            
  1076.                             if (c > i)
  1077.                                 TrackPush(c - i - 1, Textpos() - Bump());
  1078.                            
  1079.                             Advance(2);
  1080.                             continue;
  1081.                         }
  1082.                         break;
  1083.                     case RegexCode.Oneloop | RegexCode.Back:
  1084.                     case RegexCode.Notoneloop | RegexCode.Back:
  1085.                        
  1086.                        
  1087.                         {
  1088.                             TrackPop(2);
  1089.                             int i = TrackPeek();
  1090.                             int pos = TrackPeek(1);
  1091.                            
  1092.                             Textto(pos);
  1093.                            
  1094.                             if (i > 0)
  1095.                                 TrackPush(i - 1, pos - Bump());
  1096.                            
  1097.                             Advance(2);
  1098.                             continue;
  1099.                         }
  1100.                         break;
  1101.                     case RegexCode.Setloop | RegexCode.Back:
  1102.                        
  1103.                        
  1104.                         {
  1105.                             TrackPop(2);
  1106.                             int i = TrackPeek();
  1107.                             int pos = TrackPeek(1);
  1108.                            
  1109.                             Textto(pos);
  1110.                            
  1111.                             if (i > 0)
  1112.                                 TrackPush(i - 1, pos - Bump());
  1113.                            
  1114.                             Advance(2);
  1115.                             continue;
  1116.                         }
  1117.                         break;
  1118.                     case RegexCode.Onelazy:
  1119.                     case RegexCode.Notonelazy:
  1120.                        
  1121.                        
  1122.                         {
  1123.                             int c = Operand(1);
  1124.                            
  1125.                             if (c > Forwardchars())
  1126.                                 c = Forwardchars();
  1127.                            
  1128.                             if (c > 0)
  1129.                                 TrackPush(c - 1, Textpos());
  1130.                            
  1131.                             Advance(2);
  1132.                             continue;
  1133.                         }
  1134.                         break;
  1135.                     case RegexCode.Setlazy:
  1136.                        
  1137.                        
  1138.                         {
  1139.                             int c = Operand(1);
  1140.                            
  1141.                             if (c > Forwardchars())
  1142.                                 c = Forwardchars();
  1143.                            
  1144.                             if (c > 0)
  1145.                                 TrackPush(c - 1, Textpos());
  1146.                            
  1147.                             Advance(2);
  1148.                             continue;
  1149.                         }
  1150.                         break;
  1151.                     case RegexCode.Onelazy | RegexCode.Back:
  1152.                        
  1153.                        
  1154.                         {
  1155.                             TrackPop(2);
  1156.                             int pos = TrackPeek(1);
  1157.                             Textto(pos);
  1158.                            
  1159.                             if (Forwardcharnext() != (char)Operand(0))
  1160.                                 break;
  1161.                            
  1162.                             int i = TrackPeek();
  1163.                            
  1164.                             if (i > 0)
  1165.                                 TrackPush(i - 1, pos + Bump());
  1166.                            
  1167.                             Advance(2);
  1168.                             continue;
  1169.                         }
  1170.                         break;
  1171.                     case RegexCode.Notonelazy | RegexCode.Back:
  1172.                        
  1173.                        
  1174.                         {
  1175.                             TrackPop(2);
  1176.                             int pos = TrackPeek(1);
  1177.                             Textto(pos);
  1178.                            
  1179.                             if (Forwardcharnext() == (char)Operand(0))
  1180.                                 break;
  1181.                            
  1182.                             int i = TrackPeek();
  1183.                            
  1184.                             if (i > 0)
  1185.                                 TrackPush(i - 1, pos + Bump());
  1186.                            
  1187.                             Advance(2);
  1188.                             continue;
  1189.                         }
  1190.                         break;
  1191.                     case RegexCode.Setlazy | RegexCode.Back:
  1192.                        
  1193.                        
  1194.                         {
  1195.                             TrackPop(2);
  1196.                             int pos = TrackPeek(1);
  1197.                             Textto(pos);
  1198.                            
  1199.                             if (!RegexCharClass.CharInClass(Forwardcharnext(), runstrings[Operand(0)]))
  1200.                                 break;
  1201.                            
  1202.                             int i = TrackPeek();
  1203.                            
  1204.                             if (i > 0)
  1205.                                 TrackPush(i - 1, pos + Bump());
  1206.                            
  1207.                             Advance(2);
  1208.                             continue;
  1209.                         }
  1210.                         break;
  1211.                     default:
  1212.                        
  1213.                         throw new NotImplementedException(SR.GetString(SR.UnimplementedState));
  1214.                         break;
  1215.                 }
  1216.                 BreakBackward:
  1217.                
  1218.                 ;
  1219.                
  1220.                 // "break Backward" comes here:
  1221.                 Backtrack();
  1222.             }
  1223.            
  1224.         }
  1225.        
  1226.         #if DBG
  1227.         internal override void DumpState()
  1228.         {
  1229.             base.DumpState();
  1230.             Debug.WriteLine(" " + runcode.OpcodeDescription(runcodepos) + ((runoperator & RegexCode.Back) != 0 ? " Back" : "") + ((runoperator & RegexCode.Back2) != 0 ? " Back2" : ""));
  1231.             Debug.WriteLine("");
  1232.         }
  1233.         #endif
  1234.        
  1235.     }
  1236.    
  1237.    
  1238.    
  1239. }

Developer Fusion