root/trunk/scregexp.d

// scregexp
// Statically compiled /Compile-time regular expression Perl-compatible parser, version 1.0
// Author: Marton Papp, borrowing heavily from the regexp 2.0 parser written by Don Clugston.
// This version uses CTFE for simplicity, flexibility, higher performance and easy debugging
//
// It is a top/down recursive descent regexp parser with backtracking.
// The license is bsd-like, see the end of this file.
//
// 
// Terminology:
// a regex "sequence" is a set of consecutive "term"s, 
// each of which consists of a "naked term", optionally followed by
// a "quantifier" (*,+,?, {m}, {m,} or {m,n}).
// A "naked term" is either a "sequence" or an "atom".

/*
Regular expression formats:
"/regex/options" e.g. "/.+/s"
"regex/options" e.g. ".+/s"
"/regex/" e.g. "/.+/"
"regex" e.g. ".+"
possible options: m s x i (they behave as in Perl)
x is now implemented fully. # comments out one line

Features currently supported:
   it matches as if /../sm were used in Perl.
   * match previous expression 0 or more times
   + match previous expression 1 or more times
   ? match previous expression 0 or 1 times
   {m,n}  match previous expression between m and n times
   {m,} match previous expression m or more times
   {,n} match previous expression between 0 and m times
   {n} match previous expression exactly n times.
   . match any character if s option is used.
   . match any non-\n character if s is not set.
   other characters match themselves
   a|b   match regular expression a or b
   (?: ) uncaptured grouping 
   ( ) captured grouping 
   (?> ) independent subexpression
   (?= ) lookahead subexpression
   (?! ) negative lookahead subexpression
   (?<name>) or (?'name') named captured grouping 
   \k<name> or \k'name'  insert previously captured named group  
   ^  anchor,start of line if m option is used
   ^  anchor,start of string if no option is used
   $  anchor,end of line (at \n and the end of string) if m option is used
   $  anchor,the end of string or before \n at the end of string if no m is used
   \A start of string
   \z end of string
   [abc]  match any character in character class abc
   [^abc] match any character not in character class abc
   @n  match string variables passed into the functions as extra parameters. (this is a non-standard extension).
   escape characters
   \d,\s,\w,\D,\S,\W
   [\d\s\w\D\S\W] in character classes too
   All matches are greedy except if an additional ? used.
   Use ? after quantifiers (*,+,{n,m},?) to make matches non-greedy/lazy.
   Use + after quantifiers (*,+,{n,m},?) to make matches possessive.
   \1..\9 to match previously captured subsequences
   These characters have to be escaped to match them: ()[]?*+.{}^$|@
   / needs to escaped if it is used at the start or at the end of regex
   
Compile time error handling:
   redundant ) is found 
   redundant ] is found
   Regexp must not end with \\
   Unmatched parenthesis
   unsupported quantifier
   unmatched { in regular expression
   if \1..\9 references a group not accessable or not defined
   use of + or {m,n} on any and this capturing group is not supported
   use of * or {0,} on any and this capturing group is not supported
   start of range of a character range is bigger than ending range
   \k must be followed by 'name' or <name>
   Closing > missing
   Closing ' missing
   unmatched [ in regular expression
   
Run time error handling:
   if \1..\9 references a group not captured
   
Limits:
   length of input string : max of int
   number of groups: max of int
   regular expression size: limited by char[] size and stack
   number of 's : 9 (\1..\9)
   
Functions:

   bool test!(char[] regexp)(char[] stringtosearch)
   short form: t
   returns true if regexp matches the beginning of stringtosearch  

   char[] search!(char[] regexp)(char[] stringtosearch)
   short form: s
   finds the first match of regexp
   returns the substring found
   returns null if nothing found
   
   int index!(char[] regexp)(char[] stringtosearch, int indextostartat)
   short form: i
   finds the first match of regexp
   returns its starting index in stringtosearch
   returns -1 if nothing found
   
   indexrec index2!(char[] regexp)(char[] stringtosearch, int indextostartat)
   short form: i2
   finds the first match of regexp
   returns its start and end (last char+1) in stringtosearch
   returns indexrec(-1,-1) if nothing found
   
   indexrec[] indexall!(char[] regexp)(char[] stringtosearch, int indextostartat,..)
   short form: ia
   finds all occurances of the regexp in stringtosearch from left to right
   Matches follow each other. No overlaps are possible. in Perl:/ /g
   returns the start and end (last char+1) of found strings in stringtosearch
   returns an an empty array if nothing found
   
   char[][] searchall!(char[] regexp)(char[] stringtosearch,..)
   short form: sa
   finds all occurances of the regexp in stringtosearch from left to right
   Matches follow each other. No overlaps are possible. It is similar to Perl:/ /g
   returns found strings 
   returns an an empty array if nothing found
   
   grouprec [] indexgroups!(char[] regexp)(char[] stringtosearch,..)
   short form: ig
   finds the first match of regexp, the captured groups are returned
   returns the start/end indexes of captured groups and the whole string matched(at index 0)
   returns null if nothing found
   grouprec(something,-1) means that given group was not captured
   
   grouprec [][] indexgroupsall!(char[] regexp)(char[] stringtosearch,..)
   short form: iga
   finds all occurances of the regexp in stringtosearch from left to right
   Matches follow each other. No overlaps are possible. in Perl:/ /g
   returns the start and end (last char+1) of found groups of all matches
   returns an an empty array if nothing found
   
   char [] group(char[] stringtosearch,grouprec g,int groupno)
   can be used to have access to the results of searchgroups in an easier way 
   g should come from searchgroups
   returns groupno-th captured group
   if groupno is 0, returns the whole match 
   returns []/null if no match for given group
   
   void searchgroupstest(char[]reg)(char[]input)
   for testing, prints found matches,groups 
   reg regular expression to use
   input input string to parse
   
   void searchgroupsalltest(char[]reg)(char[]input)
   for testing,prints all solutions found
   reg regular expression to use
   input input string to parse
   
   void searchgroupstest2(char[]reg)(char[]input, char[][] target)
   for testing,compares found matches with target, it stops the program in case of failure
   reg regular expression to use
   input input string to parse
   target expected matches/groups
   
   void printcode(char[] reg)
   prints the generated D code from reg
   char[] tr(char[]reg)(char[] convertable)   -fast transliteration throught switches
        e.g. tr!("/12345/abced/")(str)
        
   void printclasscode(char [] reg)
   prints screg class as it should look after mixins are processed   
   
   void getclasscode(char [] reg)
   returns a string containing screg class as it should look after mixins are processed       

Class:
  screg - another way to search in strings
  bool match(char[] searchstrin); - match searchstrin , returns true if match is found
                                    if it is called again, it finds the next match
                                    It is similar to search without using anchors
  bool gmatch(char[] searchstrin); - match as if \G(?:searchstrin) , returns true if match is found
                                    if it is called again, it finds the next match
                                    
  char[] _(int groupno) - returns given group matched (_(0) returns the whole string matched
  char[] [int groupno] - used as an array 
                           returns given group matched ([0] returns the whole string matched
  char[] ismatched(int groupno) - returns if the given group matched 
  char[] exists(int groupno) - returns if the given group exists, not necessarily matched 
  int pos() - return current position from where matching is attempted (as in Perl)   
  void pos(int pin) - set current position where matching is attempted
  void restart() - restart, set position to 0 
Example:
  auto reg1=new screg!("/ab/"); // regular expression to use
  while (reg1.match("abxabxab"))
  {
    writefln(reg1._(0));
  }   
  
  auto reg3=new screg!("/(?<day>monday)|(?<day>tuesday)|(?<day>wednesday)/");
  if (reg3.match("wednesday"))
  {
     // reg3.groupname.day gives back the group number
     writefln(reg3._(reg3.groupname.day)); //prints the matched day
     writefln(reg3.getday());//prints the matched day in another way
  }
*/

// Points of interest:
// * The parser is able to treat all 'quantifier's in a single mixin function, while still applying
//   optimisations (eg, there's absolutely no difference between {1,} and "+").
// * There is absolutely no parameter passing inside the regexp engine. Even functions which
//   can't be inlined will have very low calling cost.
// * Consequently, the speed is excellent. The main unnecessary operations are the checks to see whether we
//   are at the end of the string.
//   This could be greatly improved by precalculating the minimum length required for a match,
//   at least for subsequences of fixed length.
// * Since each mixin can be given access to any desired runtime or compile-time parameters,
//   the scheme is extremely flexible.

module scregexp;
version(Tango)
{}
else
{ version = Phobos;}
version(Phobos)
import std.string;
version(Tango)
{
  import tango.text.Ascii;
  alias toUpper toupper;
  alias toLower tolower;
  alias icompare icmp;
  import tango.io.Stdout;
}
//---------------------------------------------------------------------
// Part 0 : Functions from the meta library
//---------------------------------------------------------------------

/******************************************************
 *  ulong atoui!(char [] s);
 *
 *  Converts an ASCII string to an uint.
 */
uint atoui(char [] s, uint result = 0, int indx = 0)
{
  if (s.length == indx)
    return result;
  else if (s[indx]<'0' || s[indx]>'9')
      return result;
    else 
      return atoui(s, result * 10 + s[indx] - '0', indx + 1);
}
char[] tostring(uint i)
{
  uint i2 = i / 10;
  uint digit = i - i2 * 10;
  if (i >= 10)
  {
    char[] s;
    s = tostring(i2)~cast(char)(digit + 48);
    return s;
  } 
  else
  {
    char[] s;
    s = ""~cast(char)(digit + 48);
    return s;
  } 
} 

//---------------------------------------------------------------------
// Part I : Functions for parsing a regular expression string literal.
//---------------------------------------------------------------------
// None of these generate any code.

// retuns index of first char in regstr which equals ch, or -1 if not found
// escaped chars are ignored
int unescapedFindFirst(char [] regstr, char ch, int indx = 0)
{
  if (regstr.length <= indx)
    return - 1; // not found
  else if (regstr[indx] == ch) return indx;
    else if (regstr[indx] == '\\')
        // if it's escaped, prevent it from matching.
        return unescapedFindFirst(regstr, ch, indx + 2);
      else return unescapedFindFirst(regstr, ch, indx + 1);
}

int sizeOfComment(char [] regstr)
{
  int indx;
  if (regstr.length <= indx)
    return - 1;
  while (regstr.length > indx )
  {
    if (regstr[indx] == 13)
    {
      indx++;
      if (regstr.length>indx && regstr[indx] == 10)
        return indx;
      return indx;
    }
    if (regstr[indx] == 10) 
    return indx; 
    indx++; 
  }
  return indx;
} 

// Returns the number of chars at the start of regstr which are made up by
// a repetition expression (+, *, ?, {,} )
int quantifierConsumed(char [] regstr)
{
  if (regstr.length == 0) return 0;
  else if (regstr[0] == '+' || regstr[0] == '*' || regstr[0] == '?') return 1; 
    else if (regstr[0] == '{') {
        if (unescapedFindFirst(regstr, '}') ==  - 1) {
          assert(0, "\nError: unmatched { in regular expression");
            //writefln("Error: unmatched { in regular expression");
            //assert(0);
        } else return 1 + unescapedFindFirst(regstr, '}');
      } else return 0;
}

int quantifiergreedinessConsumed(char [] regstr)
{
  if (regstr.length == 0) return 0;
  else if (regstr[0] == '?') return 1; 
    else return 0;
}

int quantifierpossessivenessConsumed(char [] regstr)
{
  if (regstr.length == 0) return 0;
  else if (regstr[0] == '+') return 1; 
    else return 0;
}

// The minimum allowable number of repetitions for this quantifier
uint quantifierMin(char [] regstr)
{
  if (regstr[0] == '*' || regstr[0] == '?') return 0;
  else if (regstr[0] == '+') return 1;
    else { 
      assert (regstr[0] == '{') ;
      return atoui(regstr[1..$]);
  }
}

// The maximum allowable number of repetitions for this quantifier
uint quantifierMax(char [] regstr)
{
  if (regstr[0] == '*' || regstr[0] == '+') return uint.max;
  else if (regstr[0] == '?') return 1;
    else if (regstr[0] == '{') {
        if (unescapedFindFirst(regstr, ',') ==  - 1) // "{n}"
          return quantifierMin(regstr);
        else if (regstr[$ - 2] == ',') // "{n,}"
            return uint.max;
          else // "{n,m}" 
            return atoui(regstr[ 1 + unescapedFindFirst(regstr, ',') .. $]);
      } else {
        assert(0, "\nError: unsupported quantifier " ~ regstr);
        
  }
}

bool quantifierGreediness(char [] regstr)
{
  if (regstr.length == 0) { 
    return true; 
  }
  else if (regstr[0] == '?') {
      return false; 
    } else {
      return true; 
  }
}

bool quantifierPossessiveness(char [] regstr)
{
  if (regstr.length == 0) { 
    return false; 
  }
  else if (regstr[0] == '+') {
      return true; 
    } else {
      return false; 
  }
}

// find the index of the first |, or -1 if not found.
// ignores escaped items, and anything in parentheses.
int findUnion(char [] regstr, bool isx, int indx = 0, int numopenparens = 0)
{
  int findUnionc;
  if (indx >= regstr.length)
    findUnionc =  - 1;
  else if (numopenparens == 0 && regstr[indx] == '|')
      findUnionc = indx;
    else if (regstr[indx] == ')')
        findUnionc = findUnion(regstr, isx, indx + 1, numopenparens - 1);
      else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?:")
          findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
        else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?>")
            findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
          else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?=")
              findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
            else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?!")
                findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
              else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?<")
                  findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
                else if (indx + 2<regstr.length && regstr[indx..indx + 3] == "(?'")
                    findUnionc = findUnion(regstr, isx, indx + 3, numopenparens + 1);
  //      else if (indx + 2<regstr.length && regstr[indx..indx + 2] == "(?"
        //         && regstr[3]>="1" && regstr[3]<="9")
      //      findUnionc = findUnion(regstr, indx + 3, numopenparens + 1);
                  else if (regstr[indx] == '(')
                      findUnionc = findUnion(regstr, isx, indx + 1, numopenparens + 1);
                    else if (regstr[indx] == '\\') // skip the escaped character
                        findUnionc = findUnion(regstr, isx, indx + 2, numopenparens);
                      else 
                      {
                        if (regstr[indx] == '[') 
                        {
                          int brsize = unescapedFindFirst(regstr[indx..$], ']');
                          if (brsize == - 1)
                            assert(0, "\nError: unmatched [ in regular expression:"~regstr);
                          findUnionc = findUnion(regstr, isx, indx + 1 + brsize, numopenparens);
                        }
                        else
                          if (isx && regstr[indx] == '#')
                            findUnionc = findUnion(regstr, isx, indx + 1 + sizeOfComment(regstr[indx..$]), numopenparens);
                          else 
                            findUnionc = findUnion(regstr, isx, indx + 1, numopenparens);
  }
  return findUnionc;
}

// keeps going until the number of ) parens equals the number of ( parens.
// All escaped characters are ignored.
// BUG: what about inside [-] ?
int parenConsumed(char [] regstr, int numopenparens = 0)
{
  if (regstr.length == 0) {
       // pragma(msg, "Unmatched parenthesis");
    assert(0,"\nUnmatched parenthesis");
       // assert(0);
  } else if (regstr[0] == ')') {
      if (numopenparens == 1) return 1; // finished!
      else return 1 + parenConsumed(regstr[1..$], numopenparens - 1);
    } else if (regstr.length>2 && regstr[0..3] == "(?:") {
        return 3 + parenConsumed(regstr[3..$], numopenparens + 1);
      } else if (regstr.length>2 && regstr[0..3] == "(?>") {
          return 3 + parenConsumed(regstr[3..$], numopenparens + 1);
        } else if (regstr.length>2 && regstr[0..3] == "(?=") {
            return 3 + parenConsumed(regstr[3..$], numopenparens + 1);
          } else if (regstr.length>2 && regstr[0..3] == "(?!") {
              return 3 + parenConsumed(regstr[3..$], numopenparens + 1);
            } else if (regstr.length>2 && (regstr[0..3] == "(?<" || regstr[0..3] == "(?'") ) {
                uint namesize = groupnameConsumed(regstr[3..$]);
                if (regstr.length == 3 + namesize || regstr[0..3] == "(?<" && regstr[3 + namesize] != '>'
                    || regstr[0..3] == "(?'" && regstr[3 + namesize] != '\'')
                {
                  if (regstr[0..3] == "(?<")
                    assert(0,"\nClosing > missing in regular expression:"~regstr);
                  else
                    assert(0,"\nClosing ' missing in regular expression:"~regstr); 
                } 
                uint start = 3 + namesize + 1;
                return start + parenConsumed(regstr[start..$], numopenparens + 1);
              } else if (regstr[0] == '(') {
                  return 1 + parenConsumed(regstr[1..$], numopenparens + 1);
                } else if (regstr[0] == '[') {
                    uint brsize = 1 + unescapedFindFirst(regstr, ']');
                    return brsize + parenConsumed(regstr[brsize..$], numopenparens);;
                  } else if (regstr[0] == '\\' && regstr.length>1)
        // ignore \(, \).
                      return 2 + parenConsumed(regstr[2..$], numopenparens);
                    else 
                      return 1 + parenConsumed(regstr[1..$], numopenparens); 
}

// the naked term, with no quantifier. Either an atom, or a subsequence.
int atomConsumed(char [] regstr)
{
  int atomConsumedc;
   //pragma(msg,"atom consumed " ~ regstr);
  if (regstr.length>2 && regstr[0..3] == "(?:") atomConsumedc = parenConsumed(regstr);
  else if (regstr.length>2 && regstr[0..3] == "(?>") atomConsumedc = parenConsumed(regstr);
    else if (regstr.length>2 && regstr[0..3] == "(?=") atomConsumedc = parenConsumed(regstr);
      else if (regstr.length>2 && regstr[0..3] == "(?!") atomConsumedc = parenConsumed(regstr);
        else if (regstr.length>2 && regstr[0..3] == "(?<") atomConsumedc = parenConsumed(regstr);
          else if (regstr.length>2 && regstr[0..3] == "(?'") atomConsumedc = parenConsumed(regstr);
            else if (regstr[0] == '(') atomConsumedc = parenConsumed(regstr);
              else if (regstr[0] == '[') atomConsumedc = 1 + unescapedFindFirst(regstr, ']');
                else if (regstr[0] == ')') {assert(0, "\nError: ) encountered without an opening ( in regular expression"~regstr);}
                  else if (regstr[0] == ']') {assert(0, "\nError: ] encountered without an opening [ in regular expression"~regstr);}
                    else if (regstr[0] == '\\') { // escape character
                        if (regstr.length>1) {
                          if (regstr[1] == 'k')
                          {
                            if (regstr.length>2)
                            {
                              if (regstr[2] == '<')
                              {
                                uint namesize = groupnameConsumed(regstr[3..$]);
                                if (regstr.length == 3 + namesize || regstr[3 + namesize] != '>')
                                {
                                  assert(0,"\nClosing > missing in regular expression"~regstr); 
                                } 
                                return atomConsumedc = 3 + namesize + 1;
                              } 
                              if (regstr[2] == '\'')
                              {
                                uint namesize = groupnameConsumed(regstr[3..$]);
                                if (regstr.length == 3 + namesize || regstr[3 + namesize] != '>')
                                {
                                  assert(0,"\nClosing ' missing in regular expression"~regstr); 
                                } 
                                return atomConsumedc = 3 + namesize + 1;
                              } 
                              assert(0,"\nError: \\k must be followed by 'name' or <name> in regular expression"~regstr); 
                            }
                            else
                              assert(0, "\nError: \\k must be followed by 'name' or <name> in regular expression"~regstr);
                          }
                          else 
                            atomConsumedc = 2;
                        } else {
                          assert(0, "\nError: Regexp must not end with \\ in regular expression"~regstr);
           // writefln("Error: Regexp must not end with \\ ");
           // assert(0);
                        }
                      } else if (regstr[0] == '@') { // NONSTANDARD: referenced parameter
                          atomConsumedc = 2;
                        } else atomConsumedc = 1; // match single char
  return atomConsumedc;
}

int groupnameConsumed(char [] regstr)
{
  int pp = 0;
  if (regstr.length>0 && (
                          regstr[pp] >= 'a' && regstr[pp] <= 'z' || regstr[pp] >= 'A' && regstr[pp] <= 'Z'))
  {
    while (regstr.length>0 && (regstr[pp] >= 'a' && regstr[pp] <= 'z' 
                               || regstr[pp] >= 'A' && regstr[pp] <= 'Z'
                               || regstr[pp] >= '0' && regstr[pp] <= '9'
                               ))
    {
      pp++;
      
    }
    return pp;
  }
  else
    assert(0, "\nError: Name of the group is missing after (?< in regular expression"~regstr);
  return 0;
}

int atomCharacterConsumed(char [] regstr, bool isx, out int whitespaceno)
{
  int atomConsumedc;
 // if (options["x"])
 // {
  whitespaceno = 0;
  
  if (regstr[0] ==' ' || regstr[0] == '\t' || regstr[0] == '\n')
  {
    whitespaceno = 1;
  } 
  if (isx && regstr[0] == '#')
  return 0;
 // } 
   //pragma(msg,"atom consumed " ~ regstr);
  if (regstr[0] == '\\') { // escape character
    if (regstr.length>1) {
      if (!((regstr[1] >= '0' && regstr[1] <= '9') || regstr[1] == 's'
            || regstr[1] == 'd' || regstr[1] == 'w'
            || regstr[1] == 'S' || regstr[1] == 'k'
            || regstr[1] == 'D' || regstr[1] == 'W'
            || regstr[1] == 'A' || regstr[1] == 'z' ))
        atomConsumedc = 2;
      else
        atomConsumedc = 0;
    } else {
      assert(0, "\nError: Regexp must not end with \\");
           // writefln("Error: Regexp must not end with \\ ");
           // assert(0);
    }
  } else if (regstr[0] == '@' || regstr[0] == '$' || regstr[0] == '^' 
             || regstr[0] == '.' || regstr[0] == '[' || regstr[0] == '(' ) { // NONSTANDARD: referenced parameter
      atomConsumedc = 0;
    } else 
      atomConsumedc = 1; // match single char
  return atomConsumedc;
}

// parses a term from the front of regstr (which must not be empty).
// consisting of an atom, optionally followed by a quantifier.
int termConsumed(char [] regstr)
{
 /*   int atomC = atomConsumed(regstr);
    int quantifierC= quantifierConsumed(regstr[atomC..$]);
    int quantifiergreedinessC=quantifiergreedinessConsumed(regstr[atomC + quantifierC ..$]);
    int termConsumed = atomC + quantifierC+quantifiergreedinessC;
    return termConsumed;*/
  uint ac = atomConsumed(regstr);
  return ac +
  quantifierConsumed(regstr[ac..$]) +
  quantifiergreedinessConsumed(regstr[ac + quantifierConsumed(regstr[ac..$]) ..$]) +
  quantifierpossessivenessConsumed(regstr[ac + quantifierConsumed(regstr[ac..$]) ..$]);
}

//parses a character sequence without quantifiers
int characterSequenceConsumed(char []regstr, bool [char[]] options, out int realchars)
{
  realchars = 0;
  if (regstr.length == 0)
  {
    return 0; 
  } 
  int whitespaceno;
  int atomC = atomCharacterConsumed(regstr, options["x"], whitespaceno);
  if (atomC>0)
  {
    int quantifierC = quantifierConsumed(regstr[atomC..$]);
    if (quantifierC == 0)
    {
      if (options["x"] && whitespaceno>0)
      {
      } 
      else
      {
        realchars = 1; 
      } 
      int crealchars;
      atomC += characterSequenceConsumed(regstr[atomC..$], options, crealchars);
      realchars += crealchars; 
    }
    else
    {
      atomC = 0;
    }
  }
  return atomC;
}

//---------------------------------------------------------------------
// Part II: mixins which generate the final code
//---------------------------------------------------------------------
// Unlike most regexp engines, which turn the pattern string into a table-based state machine,
// this one generates a binary tree of nested functions. Each node in the tree corresponds to
// a D template, and is generated as a mixin.

// At compile time, each ctfe is passed a subset of a regexp string.
// It generates a member function bool aname(), which updates a pointer p,
// and returns true if a match was found.

// Each ctfe has access to the following values:
// At compile time: 
//     fullpattern -- the complete, unparsed regular expression string
// At run time:
//     searchstr (read only) -- the string being searched
//     p --- the first character in searchstr which is not yet matched.
//     param[0..8] -- the quasi-static parameter strings @1..@9 to match.

// Additional variables or constants can be added as desired.

// Most of the complexity in the regexp engine comes from the optional quantifiers.
// In general, they can only determine how far to match by testing if the entire remainder
// of the pattern can be matched.
//
// Each ctfe also recieves a function 'next'. This has a member bool fn() which
// returns true if the remainder of the regexp match is successful.
// All regexps must ensure that next is called.

// Note that unless p is reset to 0, it will automatically behave as a global search,
// continuing from the last place it left off.


int findOptions(char [] pattern)
{
  for (int i = 0;i<pattern.length;i++)
  {
    if (pattern[pattern.length - 1 - i..pattern.length - i] == "/" )
    {
      if (pattern.length - 2 - i >= 0 && pattern[pattern.length - 2 - i] == '\\')
      {
        return pattern.length;
      }
      return pattern.length - i - 1;
    }
  }
  return pattern.length;
}
char[] removeGroupCode(char[] code)
{
  char[] code2;
  for (int p = 0;p<code.length - 10;p++)
  {
    if (code[p..p + 9] == "//Regexp:")
    {
      while (code[p] != 10 && code[p] != 13)
      {
        code2~=code[p];
        p++; 
      } 
    } 
    if (code[p..p + 10] == "/*gstart*/")
    {
      p += 10;
      while (code[p..p + 8] != "/*gend*/")
      { 
        p++;
      } 
      p += 7;
    } 
    else
      code2~=code[p];
  } 
  code2~=code[code.length - 10..code.length]; 
  return code2;
}

char[] parseRegexp(char [] pattern, bool getcode = false)
{
  char[] endSequence = alwaysTrue() ;
  int groupno = 0; 
  char[] pattern2;
  if (pattern.length>0 && pattern[0] == '/' )
  {
    pattern2 = pattern[1..$];
  } 
  else
  {
    pattern2 = pattern;
  } 
  int opt = findOptions(pattern2);
  bool [char[]] options = ["i":false, "x":false, "s":false, "m":false];
   // options["i"]=false;
  
  if (opt != pattern2.length)
  {
    foreach(c;pattern2[opt + 1..$])
    {
      options[""~c] = true;
    } 
    //opt--;
//      assert(0,pattern~tostring(opt));
  } 
  int globalfuncno;
  char[][] groupnames;
  char[] groupdcl;
  char[] code = "//Regexp:"~toLiteralString(pattern2)~ "\n"~
  endSequence~regSequence("engine", groupno, pattern2[0..opt], 
                          options, "next_alwaystrue", groupnames, groupdcl, globalfuncno);
  char[] decl;
  /*for (int i = 1;i <= groupno;i++)
  {
    decl~="int bracketend"~tostring(i)~"=-1;\n";
  }*/
  if (groupno >= 1)
    decl~="int bracketend["~tostring(groupno + 1)~"]=-1;\n";
  
  
 // if (groupnames.length>0)
  {
    decl~="struct groupnamerec {\n"~groupdcl;
 /* foreach (gname; groupnames.keys)
  {
    
  }*/ 
  /*foreach (gname,gno; groupnames)
  {
    decl~="uint "~gname~"="~tostring(gno)~";\n";
  }*/
    decl~="}\ngroupnamerec groupname;\n";
  }
  if (getcode && groupdcl.length>5)
  for (int i = 0;i<groupdcl.length - 5;i++)
  {
    if (groupdcl[i..i + 5] =="uint ")
    {
      
      for (int j = i + 5;j<groupdcl.length;j++)
      {
        if (groupdcl[j] == '=')
        {
          decl~="char[] get"~
          groupdcl[i + 5..j]~"(){ return _(groupname."~groupdcl[i + 5..j]~");}\n";
          
        } 
      } 
    }
  } 
  //assert(0,"at the end , the groupno is "~tostring(groupno));
  if (groupno == 0) //remove group related code
  {
    code = removeGroupCode(code);
  }
  return decl~code;
}

char[] alwaysTrue() // used to mark the end of a sequence
{
  return "bool next_alwaystrue () { return true; }\n";
}
private struct retSequence
{
  char[] code; 
  int groupno; 
} 

bool getFirstChar(char [] regstr,char c)
{
 return false;  
}   


// regstr is a sequence of productions, possibly containing a union
char[] regSequence(char fnname[], ref int groupno, char [] regstr, 
                   bool[char[]] options, char[] next, 
                   ref char[][] groupnames, ref char[] groupdcl, ref int globalfuncno)
{
  char [] code = "";
  int fu = findUnion(regstr, options["x"]);
   //Stdout("regSequence:"~regstr).newline;
  if (fu ==  - 1) {
        // No unions to worry about
    
    code = regNoUnions(fnname, groupno, regstr, options, next, groupnames, groupdcl, globalfuncno);
  } else {
    int[][] cases;
    bool[] validcase;
    for (int j=0;j<256;j++)
    {
   validcase~=false;
   cases~=[];
 }
    int[] altgroupno;
    int altno = 1;
    int tofu;
    tofu = - 1;
    int newfu = fu;
    char[] controllercode;
    int nocases = 0;
    altgroupno~=0;//dummy
       controllercode~= "
            int oldp = p;\n";
              code ~="
        bool "~ fnname~ "() { //regSequence options
           
          "; 
    do
    {
      fu = tofu + 1;
      tofu = newfu+tofu + 1;
      char c;
      bool firstchar = false; 
      nocases++;
      altgroupno~=groupno;
     // Stdout.format("{} {}\n",fu,tofu);
      if (getFirstChar(regstr[fu..tofu], c)) 
      {
        cases[c]~=altno; 
        validcase[c] = true;
      }
      else
      { // wrap it up
        if (nocases<4) // 2+ 1
        {
          for (int j = nocases - 1;j >= 1 ;j--)
          {
            controllercode~= "
            if (option"~tostring(altno - j)~"()) return true;
            p = oldp;/*gstart*/
            group.length="~tostring(altgroupno[altno - j] + 1)~";/*gend*/
                 "; 
          } 
        } 
        else //more than 2 consecutive cases go into a switch
        {
          controllercode~="
                        if (searchstr.length>p)
                        switch(searchstr[p]) {";
          for (int cc = 0;cc<256 ;cc++)
          {
            if (validcase[cc])
            {
              controllercode~="case '"~"':";
              for (int j = 0;j<cases[cc].length;j++)
              {
                controllercode~= "
            if (option"~tostring(cases[cc][j])~"()) return true;
            p = oldp;/*gstart*/
            group.length="~tostring(altgroupno[cases[cc][j]] + 1)~";/*gend*/
                 "; 
                
              } 
              controllercode~="break;\n";
              
             validcase[cc]=false;
                         cases[cc]=[];  
            }
          } 
          controllercode~="default;\n";
        } ;
        nocases=0;
        controllercode~= "
            if (option"~tostring(altno)~"()) return true;
            p = oldp;/*gstart*/
            group.length="~tostring(altgroupno[altno] + 1)~";/*gend*/
                 ";
                
      } 
      
      
      code ~=regSequence("option"~tostring(altno), groupno, regstr[fu..tofu], 
                         options, next, groupnames, groupdcl, globalfuncno);
      
      altno++;
      
      newfu = findUnion(regstr[tofu + 1..$], options["x"]);
    } while (newfu != - 1);
    
    code~=
    regSequence("option"~tostring(altno), groupno, regstr[tofu + 1..$], options, next, groupnames, groupdcl, globalfuncno) ;
        controllercode~=" 
            if (option"~tostring(altno)~"()) return true;
            p = oldp;/*gstart*/
            group.length="~tostring(groupno + 1)~";/*gend*/
           // writefln(\"regSequence\",~"~toLiteralString(regstr)~");
            return false;
        }";
    code~=controllercode;
  }
  return code;
}

int countGroups(char [] regstr)
{
  if (regstr.length == 0)
  {
    return 0;
  } 
  else if (regstr.length >2 && regstr[0..3] == "(?:")
    {
      return 0;
    }
    else if (regstr.length >2 && regstr[0..3] == "(?>")
      {
        return 0;
      }
      else if (regstr.length >2 && regstr[0..3] == "(?=")
        {
          return 0;
        }
        else if (regstr.length >2 && regstr[0..3] == "(?!")
          {
            return 0;
          }
          else if (regstr[0] == '(')
            {
              return 1; 
            }
            else
            {
              return 0; 
  }
}

int findLastLetter(char[] fnname)
{
  int i = 0; 
  foreach (c;fnname)
  {
    if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')))
    {
      return i; 
    } 
    i++;
  } 
  return i;
} 

// regstr is a sequence of terms, all of which must be matched
// Does not contain any unions
char[] regNoUnions(char[] fnname, ref int groupno, char [] regstr, 
                   bool [char []] options, char[] next, 
                   ref char[][] groupnames, ref char[] groupdcl, ref int globalfuncno)
{
  char[] code;
  int skipcs;
  int skip;
   // assert(0,"no way "~regstr);
  //  writefln("regNoUnions "~regstr);
  //if (regstr.length>0)
 // {
  if (regstr == "")
  {
    return "bool "~fnname~"(){ return "~next~"();}";
  } 
  code =
  "//regNoUnions "~toLiteralString(regstr[0..termConsumed(regstr)]) ~"\n";
 // }
  if (options["x"])
  {
    int i = 0;
    while (i<regstr.length && (regstr[i] ==' ' || regstr[i] == '\t' || regstr[i] == '\n'))
    {
      i += 1; 
    }
    if (i<regstr.length && regstr[i] == '#')
    {
      int soc = sizeOfComment(regstr[i..$]);
      if (soc>0)
        i += 1 + soc;
    } 
    if (i>0)
    {
      if (i<regstr.length)
      {
        return regNoUnions(fnname, groupno, regstr[i..$], options, next, groupnames, groupdcl, globalfuncno);
      }
      else
      {
        return "bool "~fnname~"(){ return "~next~"();}";
      }
    } 
  } 
 //assert((regstr.length ==0),"regstr.length cannot be zero " ~ regstr );
  if (regstr.length == termConsumed(regstr)) {
        // there's only a single item (possibly including a quantifier)
       // pragma(msg, "\nhere at the moment3");
    code~= regTerm(fnname, groupno, regstr, options, next, groupnames, groupdcl, globalfuncno);
    //  pragma(msg, "\nhere at the moment4");
  } else {
    int realskipcs;
    skipcs = characterSequenceConsumed(regstr, options, realskipcs);
    if (regstr.length == skipcs)
    {
      code~= regCharacterSequence(fnname, groupno, regstr, options, next);
    } 
    else
    {
   // writefln(skipcs);
    //int skip;
      char[] second;
      if (realskipcs>1)
      {
        skip = skipcs;
        
      }
      else
      {
        skip = termConsumed(regstr);
      }
//    int g=groupno+countGroups(regstr);
      int g = groupno;
      char[] newnextname = "next"~tostring(globalfuncno);
      globalfuncno++;
      if (realskipcs>1)
      {
    //   assert(0,"hi"~tostring(skip)~regstr);
        second = regSequence(newnextname, groupno, regstr[skip..$], 
                             options, next, groupnames, groupdcl, globalfuncno);
        code~= "bool "~fnname~"() {  
                      
            "~second~regCharacterSequence("first", g, regstr[0..skip], options, newnextname)~" // regTerm 
            return first();
        }
      ";
      }
      else 
      { 
        int oldgroupno = groupno;
        int glfno = 0;
        char[][] groupnamesdummy;
        char[] groupdcldummy;
        //regTerm("", groupno, regstr[0..skip], options, "", groupnames,groupdcl,glfno); //just to get groupno
        char[] first = regTerm("first", groupno, regstr[0..skip], options, newnextname, groupnames, groupdcl, globalfuncno);
        second = regSequence(newnextname, groupno, regstr[skip..$], 
                             options, next, groupnames, groupdcl, globalfuncno);
        code~="
        bool "~fnname~"() {            
            "~second~first~" // regTerm 
            return first();
        }
      ";
      }
    }
  }
  return code;
}
char[] regStop(char[] fnname, int groupno, char[] next)
{ 
  return "
     bool "~fnname~"() { //regStop
     ""bracketend["~tostring(groupno)~"]=p;
     return "~next~"();   
     }";
}

char[] regCharacterSequence(char[] fnname, int groupno, char [] regstr, bool [char []] options, char[] next)
{
  int i = 0;
  int matchsize = 0;
  char [] match = "";
  char[] code;
  while (i<regstr.length)
  {
    if (regstr.length + i>1 && regstr[i] == '\\') { 
      match~=toLiteralString(regstr[i + 1]);
      i += 2;
      matchsize++; 
    } else {
      if (options["x"] && (regstr[i] ==' ' || regstr[i] == '\t' || regstr[i] == '\n'))
      {
      } 
      else
      {
        match~=toLiteralString(regstr[i]);
        matchsize++; 
      } 
      i++;
        // match single character
    }
    
  }
  if (!options["i"])
  {
  // writefln("match "~match);
    code ="bool "~fnname~"() {              
                if (p+"~tostring(matchsize)~">searchstr.length || searchstr[p..p+"~tostring(matchsize)~"]!=\""~match~"\") return false;
                p+="~tostring(matchsize)~";
                return "~next~"();
            }
          ";
  }
  else
  {
    code ="bool "~fnname~"() {
                if (p+"~tostring(matchsize)~">searchstr.length || icmp(searchstr[p..p+"~tostring(matchsize)~"],\""~match~"\")!=0) return false;
                p+="~tostring(matchsize)~";
                return "~next~"();
            }
          "; 
  } 
  return code;
}


// the term without a quantifier. Here we deal with embedded subsequences.
char[] regSingleTerm(char[] fnname, ref int groupno, char [] regstr, bool [char []] options,
                     char[] next, ref char[][] groupnames, ref char[] groupdcl, int globalfuncno)
{
  char[] code;
  
  if (regstr.length>2 && regstr[0..3] == "(?:") {
            // A sequence always calls next.
    code = regSequence(fnname, groupno, regstr[3..$ - 1], options, next, groupnames, groupdcl, globalfuncno);
  } 
  else if (regstr.length>2 && regstr[0..3] == "(?>") {
            // A sequence always calls next.
      code = regSequence("independent", groupno, regstr[3..$ - 1], 
                         options, "next_alwaystrue",
                         groupnames, groupdcl, globalfuncno);
      code ="bool "~fnname~"() {\n"~code ;
      code~="return independent() && "~next~"();}\n"; 
    }
    else if (regstr.length>2 && regstr[0..3] == "(?=") {
            // A sequence always calls next.
        code = regSequence("lookahead", groupno, regstr[3..$ - 1], options, 
                           "next_alwaystrue", groupnames, groupdcl, globalfuncno);
        code ="bool "~fnname~"() {\n"~code ;
        code~=" int oldp=p;
              if (!lookahead()) return false;
              p=oldp;
                      return "~next~"();            
            }\n"; 
      } 
      else if (regstr.length>2 && regstr[0..3] == "(?!") {
            // A sequence always calls next.
          code = regSequence("negativelookahead", groupno, regstr[3..$ - 1], options, 
                             "next_alwaystrue", groupnames, groupdcl, globalfuncno);
          code ="bool "~fnname~"() {\n"~code ;
          code~="   int oldp=p;
              if (negativelookahead()) return false;
              p=oldp;
                      return "~next~"();            
            }\n"; 
        } 
        else if (regstr[0] == '(' || regstr.length>2 && (regstr[0..3] == "(?<" || regstr[0..3] == "(?'")) {
            // A sequence always calls next.
            groupno++;
            char[] stop = regStop("stop"~tostring(groupno), groupno, next);
            char[] bracketvar = "bracketend["~tostring(groupno)~"]";
            int cgroupno = groupno;
            uint seqstart = 1;
            char [] setgroupname;
            char[] savegroupnamevalue;
            char[] restoregroupnamevalue;
            if (regstr.length>2 && (regstr[0..3] == "(?<" || regstr[0..3] == "(?'"))
            {
              char[] name = regstr[3..3 + groupnameConsumed(regstr[3..$])];
         //groupnames[name]=groupno; does not work as ctfe
              int groupexists;
              groupexists = getGroupno(groupnames, name);
              
         /*if (groupdcl.length>5)
         for (int i=0;i<groupdcl.length-5;i++)
         {
             if (groupdcl[i..i+5]=="uint ")
             {
                 
                 for (int j=i+5;j<groupdcl.length;j++)
                 {
                     if (groupdcl[j]=='=')
                     {
                        if (groupdcl[i+5..j]==name)
                        {
                          groupexists=true;
                          break;
                        }  
                     }  
                    }   
             }
         }*/ 
              seqstart = 3 + groupnameConsumed(regstr[3..$]) + 1; 
              setgroupname = "groupname."~name~"="~tostring(groupno)~";\n";
              savegroupnamevalue ="int tempgroupname=groupname."~name~";\n";
              restoregroupnamevalue = "groupname."~name~"=tempgroupname;\n";
              if (groupexists == - 1) 
              {groupdcl~="uint "~name~"="~tostring(groupno)~";\n";
                  //if (groupnames.length<=groupno)
                  //  groupnames.length= groupno;
                  //groupnames[groupno]=name;
                groupnames~=name~"="~tostring(groupno);
              }
            } 
            
            
            code =" //single term
            bool "~fnname~"() { // (
             "~stop~"
              //int "~bracketvar~";
            "~regSequence("a", groupno, regstr[seqstart..$ - 1], options, "stop"~tostring(groupno), groupnames, groupdcl, globalfuncno)~ "
              int oldp=p; 
              if (group.length<="~tostring(cgroupno)~")
              {
                 group.length="~tostring(cgroupno + 1)~";
              }           
              group["~tostring(cgroupno)~"]=grouprec(oldp,-1);
              "~savegroupnamevalue~"
              "~setgroupname~"
              bool r=a(); 
              if (r)  
              {             
              group["~tostring(cgroupno)~"]=grouprec(oldp,"~bracketvar~");
           //   writefln(\"grouprec1 \",oldp,\" \",p);
              }
              else
              {
              "~restoregroupnamevalue~"
              group.length="~tostring(cgroupno)~";  
              }  
             return r;
              }
            ";
          } else {
            // A simple atom doesn't call next, so we need to do it here.
            code ="bool "~fnname~"() {
                "~regAtom(groupno, regstr, groupnames, options) ~ "
                return fn() && "~next~"();
            }
          ";
  }
  return code;
}

// Evaluate one term (without quantifier).
// This helper class has two purposes:
// (1) to restore the 'p' pointer when we return.
// (2) ensure that at least one character was consumed
char[] regSequenceDontUpdateP(char[] fnname, int groupno, char [] regstr, bool [char [] ] options, ref int globalfuncno)
{
  //int globalfuncno=0;
  char[][] groupnames; //dummy
  char[] groupdcl;
  return "bool "~fnname~"() { //regSequenceDontUpdateP
        " ~regSequence("x", groupno, regstr, options, "next_alwaystrue",
                       groupnames, groupdcl, globalfuncno)~"
        // It's only a successful match if _something_ was consumed
        if (p==theinitialp) return false;      
        int oldp = p;
        if (!x()) return false;
        p = oldp;  
        return true;                
    }
  ";
}

//  Calls the naked term twice, but only updates 'p' after the first one.
// Evaluate the term, knowing that what comes after will be the same as this.
char[] regTermTwice(char[] fnname, int groupno, char [] regstr, bool [char[]] options, int t, ref int globalfuncno)
{
  char[] code;
  char[] groupdcl;
  char[][] groupnames; //dummy
  if (regstr.length>2 && (regstr[0..3] == "(?:" || regstr[0..3] == "(?>" 
                          || regstr[0..3] == "(?=" || regstr[0..3] == "(?!")) {
    
    char [] suddendeath = regSequenceDontUpdateP("suddendeath", groupno, regstr[3..t - 1], 
                                                 options, globalfuncno); //groupno may be incorrect but does not matter
    
    code ="
        bool "~fnname~"()
        {
            // While evaluating this first sequence, if this is a sequence
            // that potentially has zero length (ie, everything is a *, ? or {m,} term),
            // each term should attempt to consume at least one character if possible.
            int theinitialp = p;  
         " ~suddendeath ~regSequence("a", groupno, regstr[3..t - 1], options, "suddendeath",
                                     groupnames, groupdcl, globalfuncno)~
    "return a();
       }
       ";
  } 
  else if (regstr[0] == '(') {
      char []suddendeath = regSequenceDontUpdateP("suddendeath", groupno + 1, regstr[1..t - 1], options, globalfuncno);
      int g = groupno + 1;
      code ="
        bool "~fnname~"()
        {
            // While evaluating this first sequence, if this is a sequence
            // that potentially has zero length (ie, everything is a *, ? or {m,} term),
            // each term should attempt to consume at least one character if possible.
            int theinitialp = p;
           "~suddendeath~ regSequence("a", g, regstr[1..t - 1], options, "suddendeath",
                                      groupnames, groupdcl, globalfuncno)~ "
             int oldp=p;              
              bool r=a(); /*gstart*/
              if (group.length<="~tostring(groupno + 1)~")
              {
                 group.length="~tostring(groupno + 2)~";
              }
              group["~tostring(groupno + 1)~"]=grouprec(oldp,-1); 
              if (r)
              {
          //    writefln(\"grouprec \",oldp,\" \",p);
              }
              else
              {
              group.length="~tostring(groupno + 1)~";  
              } /*gend*/
             return r;
            //return a.fn();
       }
       ";
    } else {
      code ="
            bool "~fnname~"() {
                // It's easy with atoms, because we know they always eat something.
                // BUG: Maybe this will fail when null @n strings are passed in?                
                "~regAtom(groupno, regstr, groupnames, options)~"
                return fn();
            } 
    "; 
  }
  return code;
}


// the atom, optionally followed by a quantifier.
// Here we deal with all kinds of repitition,
// but we make different optimisations depending on the allowable repeats.
char[] regTerm(char[] fnname, ref int groupno, char [] regstr, bool [char []] options,
               char[] next, ref char[][] groupnames, ref char[] groupdcl, ref int globalfuncno)
{
  char [] code;
  if (atomConsumed(regstr) == regstr.length) {
    
            // there is no quantifier, just use the naked term
    code = regSingleTerm(fnname, groupno, regstr, options, next, groupnames, groupdcl, globalfuncno);
  } else {
    int t = atomConsumed(regstr);
    uint qc = quantifierConsumed(regstr[t..$]);
    uint repmin = quantifierMin(regstr[t..$]);
    uint repmax = quantifierMax(regstr[t..$]);
    uint greedy = quantifierGreediness(regstr[t + qc..$]);
    uint possess = quantifierPossessiveness(regstr[t + qc..$]); 
    uint cg = countGroups(regstr);
    
    code ="
        bool "~fnname~"(){
           
            
            // HORRENDOUSLY inefficient! In some cases, we generate the quantified term THREE TIMES!
            // The first one contains the rest of the search tree.
            // This is used when we think we can do (atom).(next) for an early exit
            "~regTerm("atomAndNext", groupno, regstr[0..t], options, next, groupnames, groupdcl, globalfuncno) ~ "

        //    debug writefln(fullpattern, \" Quantifier \",regstr ,  \" starting at \", searchstr[p..$]);
            ";
    if (possess)
    {
      code~=regTerm("atom", groupno, regstr[0..t], options, "next_alwaystrue", groupnames, groupdcl, globalfuncno);
    }
    if (repmin == 0 && repmax == 1) { 
      code~="
                // \"?\", or \"{0,1}\". Worth optimising seperately
                int oldp = p;
                ";
      if (possess)
      {
        code~=" // possesive
                if (atom())
                  {
                  if (!"~next~"())
                    return false;
                   return true;
                  } 
                p = oldp;
                if ("~next~"())
                {
                  return true;       
                }  
                p = oldp;
                return false;  
                }";
      }
      else
        if (!greedy)
        {
          if (next == "next_alwaystrue")
          {
            code~="return true;}";
          }
          else 
            code~="if ("~next~"()) { return true; }
                p = oldp;
                return atomAndNext();
                }";
        }
        else //greedy
        {
          if (next == "next_alwaystrue")
          {
            code~="// pragma(msg, \"?greedy\");
                if (atomAndNext())
                  {
                    return true;
                  } 
                p = oldp;
                return true;                      
                }";
          }
          else 
            code~=" // pragma(msg, \"?greedy\");
                if (atomAndNext())
                  {
                    return true;
                  } 
                p = oldp;
                if ("~next~"())
                {
                  return true;       
                }  
                p = oldp;
                return false;  
                }
              ";
      }
    } else {
      code~="
                // Here's where we generate the redundant term.
                // If we can't do (atom).(next), we must be able to do
                // (atom).(atom) to stay in the game.                       
                  "~regTermTwice("atomonly", groupno, regstr[0..t], options, t, globalfuncno) ;
      if (repmin == 0 && repmax == uint.max) {
                    // optimise for \"*\", \"{0,}\"
        if (cg>0)
        {
          assert(0,"\nError:use of * or {0,} on any and this capturing group "~regstr[0..t]~" is not supported in regular expression"~regstr); 
        } 
        if (possess) // * or {0,}
        {
          code~=" // possessive
                     int oldp;
                     int veryoldp=p; 
                     int newp=-1;            
                   // p=oldp;
                    do {
                      // Can we do (atom)?
                      oldp = p;
                      if (atom()) 
                      { newp=p; 
                      }         
                     } while (p != oldp);
                     if (newp!=-1)
                     {
                      p=newp; 
                             
                      return "~next~"();
                     } //nothing is matched
                    p = veryoldp; 
                    if ("~next~"()) return true; // success but we want longer ones
                    return false;
                    }";
        }
        else if (!greedy) 
          {
            
            if (next == "next_alwaystrue")
              code~=" // optimise for non-greedy\"*\", \"{0,}\"                  
                    return true; // We can finish right now.                  
                   }
                     ";
            else
              code~=" // optimise for non-greedy\"*\", \"{0,}\"
                    int oldp=p;
                    if ("~next~"()) return true; // We can finish right now.
                    p=oldp;
                    do {
                      // Can we do (atom).(next) ?
                      oldp = p;
                      if (atomAndNext()) { return true; }
                      p = oldp;
                      // We need to do (atom).(atom) to have any chance of continuing.                  
                      // also, it must have consumed at least one character, or there is no hope.                 
                    } while (atomonly() && p != oldp);
                    return false;
                    }
                     ";
          }
          else // optimise for greedy\"*\", \"{0,}\"
          {
            //atom cannot contain capturing groups
            
            if (next == "next_alwaystrue")
              code~=" // greedy
                     int oldp;
                     int veryoldp=p; 
                     int newp=-1;            
                   // p=oldp;
                    do {
                      // Can we do (atom).(next) ?
                      oldp = p;
                      if (atomAndNext()) 
                      { newp=p;
                      }
                      p = oldp;
                      // We need to do (atom).(atom) to have any chance of continuing.                  
                      // also, it must have consumed at least one character, or there is no hope.                 
                    } while (atomonly() && p != oldp);
                     if (newp!=-1)
                     {
                      p=newp; 
                             
                      return true;
                     }
                    p = veryoldp; 
                    return true; // success but we want longer ones                
                    }"; 
            else
              code~=" // greedy
                     int oldp;
                     int veryoldp=p; /*gstart*/   
                     grouprec [] savegroups; /*gend*/
                     int newp=-1;            
                   // p=oldp;
                    do {
                      // Can we do (atom).(next) ?
                      oldp = p;
                      if (atomAndNext()) 
                      { newp=p; /*gstart*/
                        int sl=group.length-("~tostring(groupno + 1)~");
                        if (sl>0)
                        {
                        savegroups.length=sl;  
                        savegroups[0..$]=group["~tostring(groupno + 1)~"..$];
                        }    
                        group.length="~tostring(groupno + 1)~"; /*gend*/ 
                      }
                      p = oldp;
                      // We need to do (atom).(atom) to have any chance of continuing.                  
                      // also, it must have consumed at least one character, or there is no hope.                 
                    } while (atomonly() && p != oldp);
                     if (newp!=-1)
                     {
                      p=newp; /*gstart*/
                      group.length="~tostring(groupno + 1)~"+savegroups.length;
                      if (savegroups.length>0)
                      {
                        group["~tostring(groupno + 1)~"..$]=savegroups[0..$];
                      }  /*gend*/ 
                             
                      return true;
                     }
                    p = veryoldp; /*gstart*/ 
                    group.length="~tostring(groupno + 1)~"; /*gend*/
                    if ("~next~"()) return true; // success but we want longer ones
                    return false;
                    }";
        }
      } else { // \"+\", or \"{m,n}\"
        if (cg>0)
        {
          assert(0,"\nError:use of + or {m,n} on any and this capturing group "~regstr[0..t]~" is not supported in regular expression"~regstr); 
        } 
        if (possess) 
        {
  // possessive start
          code~="//possessive\"+\", or \"{m,n}\"
                    int numreps=0; // how many repeats have we found?
                    int oldp;
                    int newp=-1; \n";
          if (repmin == 0)
          {
            code~=" newp=p;                 
                    "; 
          }
          code~="
                    do {
                        oldp = p;
                        numreps++;
                        if (numreps>="~tostring(repmin)~" && atom()) {
                          newp=p;                         
                        } 
                      
                        ";
          if (repmax<uint.max) {
            code~=" // optimise for \"+\", \"{n,}\"
                            if (numreps == "~tostring(repmax)~") break;
                            ";
          }
          code~="
                     } while (p!=oldp);
                     if (newp!=-1)
                     {
                      p=newp; 
                      return "~next~"();
                     }
                    return false;
                  }
                ";
          
    // possessive end       
        } 
        else
          if (!greedy) 
          {
            code~="// non-greedy\"+\", or \"{m,n}\"
                    int numreps=0; // how many repeats have we found?
                    int oldp;\n";
            if (repmin == 0)
            {
              if (next == "next_alwaystrue")
                code~=" return true;
                    "; 
              else
                code~="
                    oldp=p;
                    if ("~next~"()) return true;
                    p = oldp;
                    "; 
            } 
            code~="
                    do {
                        oldp = p;
                        numreps++;
                        if (numreps>="~tostring(repmin)~" && atomAndNext()) return true;
                        p = oldp;
                    ";
            if (repmax<uint.max) {
              code~=" // optimise for \"+\", \"{n,}\"
                            if (numreps == "~tostring(repmax)~") return false;
                            ";
            }
            code~="
                     } while (atomonly() && p!=oldp);
                    return false;
                    }
";
          }
          else // greedy
          {
            code~="//greedy\"+\", or \"{m,n}\"
                    int numreps=0; // how many repeats have we found?
                    int oldp;
                    int newp=-1; /*gstart*/
                    grouprec [] savegroups;/*gend*/\n";
            if (repmin == 0)
            {
              code~="
                    oldp=p;
                    if ("~next~"()) 
                    {
                      newp=p; /*gstart*/                    
                        int sl=group.length-"~tostring(groupno + 1)~";
                        if (sl>0)
                        {
                        savegroups.length=sl;
                        savegroups[0..$]=group["~tostring(groupno + 1)~"..$];
                        }  
                        group.length="~tostring(groupno + 1)~";  /*gend*/           
                    }
                    p = oldp;
                    "; 
            }
            code~="
                    do {
                        oldp = p;
                        numreps++;
                        if (numreps>="~tostring(repmin)~" && atomAndNext()) {
                          newp=p;
                        /*gstart*/ 
                        int sl=group.length-("~tostring(groupno + 1)~");
                        if (sl>0)
                        {
                        savegroups.length=sl;
                        savegroups[0..$]=group["~tostring(groupno + 1)~"..$];
                        }  
                        group.length="~tostring(groupno + 1)~"; /*gend*/      
                        } 
                        p = oldp;
                        ";
            if (repmax<uint.max) {
              code~=" // optimise for \"+\", \"{n,}\"
                            if (numreps == "~tostring(repmax)~") break;
                            ";
            }
            code~="
                     } while (atomonly() && p!=oldp);
                     if (newp!=-1)
                     {
                      p=newp; /*gstart*/
                      group.length="~tostring(groupno + 1)~"+savegroups.length;
                      if (savegroups.length>0)
                      {
                        group["~tostring(groupno + 1)~"..$]=savegroups[0..$];
                      } /*gend*/
                      return true;
                     }
                    return false;
                  }
                ";
        }
      }
    }
    
  }
  return code;
}
char[] slashimp(char[] abbr, bool[char[]] options)
{
  return "
        bool fn() { // character class
                if (p<searchstr.length && ("~charMatches(abbr, "searchstr[p]", options)~"))
                {
                  p++; 
                  return true;
                }  
                return false;
            }
          "; 
} 
char [] Backreference(int maxgroupno, int groupno, char[] groupname)
{
  
  if (groupno>maxgroupno)
  {
    assert(0,"\nmax group number at this point:"~
           tostring(maxgroupno) ~ " bad \\"~tostring(groupno)~
           ":group "~tostring(groupno)
           ~" cannot be referenced as it is not available at this point"); 
  } 
       // assert(0,"bad \\"~regstr[1]~ ":group "~regstr[1]~" cannot be referenced as it is not captured");
  char[] groupcode;
  char[] groupid;
  if (groupname != "")
  {
    groupcode = "groupname."~groupname; 
    groupid = groupname;
  } 
  else 
  {
    groupcode = tostring(groupno); 
    groupid = groupcode; 
  }
  return " bool fn() {   
       int gs=group["~ groupcode~"].start;
       int ge=bracketend["~ groupcode~"];
       int gsize=ge-gs;
       // writefln(`backref group `,gs,\" \",ge,`searchstr `,\" \",p,\" \",p+gsize,\""~ groupcode~"\","~ groupcode~");
        //writefln(`backref group `,searchstr[gs..ge],`searchstr `,searchstr[p..p+gsize]);
       if (gsize<0)
       {
         throw new Exception(\"bad \\\\"~groupid~ ":group "~groupid~" cannot be referenced as it is not captured\"); 
          // assert(0,\"bad \\\\"~tostring(groupno)~ ":group "~tostring(groupno)~" cannot be referenced as it is not captured\"); 
      }
       if (p+gsize<=searchstr.length && searchstr[gs..ge]==searchstr[p..p+gsize])
               {
                 p+=gsize;
                 return true;
                }
             return false; 
            } 
          ";
  
} 

int getGroupno(ref char[][] groupnames, ref char[] nametofind)
{
  int f = - 1;
  
  for (int i = 0;i<groupnames.length;i++)
  {
    char[] findthis = nametofind;
    findthis~="=";
    if (groupnames[i].length>nametofind.length
        && 
        groupnames[i][0..nametofind.length + 1] == findthis)
    {
      f = atoui(groupnames[i][nametofind.length + 1..$]);
      break;
    }
  }
  return f;
  
} 
// generate a parser for an atom
// IN: regstr is a valid atom, without a repeat
// OUT: if atom is matched, return true, and update p.
//      if atom is not matched, return false, and leave p unchanged.
char[] regAtom(int groupno, char [] regstr, char[][] groupnames, bool[char[]] options)
{ 
  if (regstr[0] == '[') {
    if (regstr[1] == '^')
    { 
      return "
        bool fn() { // inverse character class  
              if (p<searchstr.length && (!"~charMatches(regstr[2..$ - 1], "searchstr[p]", options)~"))
                {
                  p++; 
                  return true;
                }  
                return false;
         } "; 
    } else {
      return "
        bool fn() { // character class
                if (p<searchstr.length && ("~charMatches(regstr[1..$ - 1], "searchstr[p]", options)~"))
                {
                  p++; 
                  return true;
                }  
                return false;
            }
          ";
    } 
  } else if (regstr[0] == '.') { // match any
      if (options["s"])
      {
        return "
        bool fn() { //.
            if (p==searchstr.length) return false;
            p++;
            return true;
        }
      ";
      } 
      else
      {
        return "
        bool fn() { //.
            if (p==searchstr.length || searchstr[p]=='\\n' ) return false;
            p++;
            return true;
        }
      ";
        
      }
    } else if (regstr.length>1 && regstr[0..2] == "\\w") { // match a word letter
        bool [char[]] toptions = ["i":false];
        return slashimp("\\w", toptions);
      }
      else if (regstr.length>1 && regstr[0..2] == "\\s") // match whitespace
          return slashimp("\\s", options); 
        else if (regstr.length>1 && regstr[0..2] == "\\d") // match numbers
            return slashimp("\\d", options); 
          else if (regstr.length>1 && regstr[0..2] == "\\D") // match numbers
              return slashimp("\\D", options); 
            else if (regstr.length>1 && regstr[0..2] == "\\W") // match numbers
                return slashimp("\\W", options); 
              else if (regstr.length>1 && regstr[0..2] == "\\S") // match numbers
                  return slashimp("\\S", options);
                else if (regstr.length>1 && regstr[0] == '\\' && (regstr[1] == 'k' ))
                  {
                    if (regstr[2] == '<' || regstr[2] == '\'')
                    {
                      uint namesize = groupnameConsumed(regstr[3..$]);
                      char[] name = regstr[3..3 + namesize];
                      int f = getGroupno(groupnames, name);
                      if (f == - 1)
                        assert(0,"\nError:bad group name "~regstr[3..3 + namesize]~ ":it does not exist");
                      return Backreference(groupno, f, name); 
                    }
                    assert(0, "\nError:internal");
                    
                  } 
                  else if (regstr.length>1 && regstr[0] == '\\' && (regstr[1] >= '1' && regstr[1] <= '9' )) {
                      return Backreference(groupno, atoui(""~regstr[1]), "");
                    }
                    else if (regstr[0] == '@') { // NONSTANDARD: referenced parameter
                        return regParameter(atoui(regstr[1..$]) - 1, options);
                      } else if (regstr[0] == '^') { // start of line
                          if (options["m"])
                          {
                            return "
        bool fn() {
            return (p==0 || searchstr[p-1]=='\\n');
        } 
        ";
                          }
                          else
                          {
                            return "
        bool fn() {
            return (p==0);
        } 
        "; 
                          } 
                        } else if (regstr[0] == '$') { // end of line
                            if (options["m"])
                            {
                              return "
        bool fn() {
            return (p==searchstr.length || searchstr[p+1]=='\\n');
        }    
        ";
                            }
                            else
                            {
                              return "
        bool fn() {
            return (p==searchstr.length || (p==searchstr.length-1 && searchstr[p]=='\\n'));
        }    
        ";
                            } 
                          } else if (regstr.length>1 && regstr[0] == '\\' && regstr[1] == 'A') { // end of line
                              return "
        bool fn() {
            return (p==0);
        }    
        ";
                            } else if (regstr.length>1 && regstr[0] == '\\' && regstr[1] == 'z') { // end of line
                                return "
        bool fn() {
            return (p==searchstr.length);
        }    
        ";
                              } else if (regstr.length>1 && regstr[0] == '\\') { // escaped char
                                  char[] regstr1 = toLiteralChar(regstr[1]);
                                  if (!options["i"])
                                  {
                                    return "
         bool fn() {
            if (p==searchstr.length || searchstr[p]!="~regstr1~") return false;
            p++;
            return true;
        }
      ";
                                  }
                                  else
                                  {
                                    return "
         bool fn() {
            if (p==searchstr.length || icmp([searchstr[p]],["~regstr1~"])!=0) return false;
            p++;
            return true;
        }
      ";
                                    
                                    
                                  } 
                                } else {
        // match single character
                                  char[] regstr0 = toLiteralChar(regstr[0]);
                                  if (!options["i"])
                                  {
                                    return "
        bool fn() {
            if (p==searchstr.length || searchstr[p]!="~regstr0~") return false;
            p++;
            return true;
        }
      ";
                                  }
                                  else
                                  {
                                    return "
         bool fn() {
            if (p==searchstr.length || icmp([searchstr[p]],["~regstr0~"])!=0) return false;
            p++;
            return true;
        }
      ";
                                  } 
  }
}

// match a variable string, which will be passed as a parameter.
char[] regParameter(int parmnum, bool [char[]]options)
{
  if (!options["i"])
  {
    return "
    bool fn() {
        if (p + param["~tostring(parmnum)~"].length > searchstr.length) return false;
        if (searchstr[p..p+param["~tostring(parmnum)~"].length] != param["~tostring(parmnum)~"]) return false;
        p+=param["~tostring(parmnum)~"].length;
        return true;
    }
  ";
  }
  else
  {
    return "
    bool fn() {
        if (p + param["~tostring(parmnum)~"].length > searchstr.length) return false;
        if (icmp(searchstr[p..p+param["~tostring(parmnum)~"].length],param["~tostring(parmnum)~"])!=0) return false;
        p+=param["~tostring(parmnum)~"].length;
        return true;
    }
  ";
    
  }
}

//"a-zA-Z0-9_"

char[] toLiteralString(char[] s)
{
  char[] sout;
  foreach(c;s)
  {
    sout~=toLiteralString(c);
  } 
  return sout; 
}

char[] toLiteralString(char c)
{
  if (c == '\'')
  {
    return "\\\'"; 
  } 
  else if (c == '\"')
    {
      return "\\\""; 
    } 
    else if (c == '\\')
      {
        return "\\\\"; 
      }
      else if (c == '\n')
        {
          return "\\n"; 
        }
        else if (c == '\r')
          {
            return "\\r"; 
          }
          else if (c == '\t')
            {
              return "\\t"; 
            }
            else
            {
              return ""~c; 
  } 
}


char[] toLiteralChar(char c)
{
  return "\'"~toLiteralString(c)~"\'"; 
  
}
// ps1<=pe1 and ps2<=pe2
bool intersectPeriods(int ps1, int pe1, int ps2, int pe2, out int is1, out int ie1)
{
  if (pe1<ps2) 
  {
    return false;
  } 
  if (pe2<ps1) 
  {
    return false;
  } 
  if (pe1 <= pe2)
  {
    if (ps1 <= ps2)
    {
      is1 = ps2;
      ie1 = pe1; 
      return true; 
    } 
    else
    {
      is1 = ps1;
      ie1 = pe1; 
      return true; 
    } 
  } 
  else
  {
    if (ps1 <= ps2)
    {
      is1 = ps2;
      ie1 = pe2; 
      return true; 
    } 
    else
    {
      is1 = ps1;
      ie1 = pe2; 
      return true; 
    } 
    
  } 
}


// return true if char ch is matched by the character class regstr.
char[] charMatches(char [] regstr, char []ch, bool [char[]] options)
{
  char[] code; 
  if (regstr.length == 0) return "false";
  else if (regstr.length >= 3 && regstr[1] == '-' && regstr[0] != '\\' ) {
      if (regstr[0]>regstr[2])
      {
        assert(0, "Error:>"~regstr[0..3]~"< start of range of a character range is bigger than ending range"); 
      } 
      if (!options["i"])
      { 
        char[] regstr0 = toLiteralChar(regstr[0]);
        char[] regstr2 = toLiteralChar(regstr[2]);
        return "("~ch~">="~regstr0~" && "~ch~"<="~regstr2~") || "~charMatches(regstr[3..$], ch, options);
      }
      else
      {
        int is1, ie1;
        char is2, ie2;
        bool i1, i2;
        char[] code1, code2;
        i1 = intersectPeriods('a', 'z', regstr[0], regstr[2], is1, ie1);
        if (i1)
        {
          int isi, iei;
          char uis, uie;
          uis = toupper([is1])[0] ; uie = toupper([ie1])[0] ;
          code1 = "("~ch~">="~toLiteralChar(uis)~" && "~ch~"<="~toLiteralChar(uie)~") || ";
          if (intersectPeriods(uis, uie, regstr[0], regstr[2], isi, iei))
          {
            if (isi == uis && iei == uie) //UPPER-UPPER is in regstr[0]-regstr[2]
            {
              code1 = "";
            } 
          } 
        } 
        i1 = intersectPeriods('A', 'Z', regstr[0], regstr[2], is1, ie1);
        if (i1)
        {
          int isi, iei;
          char lis, lie;
          lis = tolower([is1])[0] ; lie = tolower([ie1])[0] ;
          code2 = "("~ch~">="~toLiteralChar(lis)~" && "~ch~"<="~toLiteralChar(lie)~") || ";
          if (intersectPeriods(lis, lie, regstr[0], regstr[2], isi, iei))
          {
            if (isi == lis && iei == lie) //UPPER-UPPER is in regstr[0]-regstr[2]
            {
              code2 = "";
            } 
          } 
        }
        char[] regstr0 = toLiteralChar(regstr[0]);
        char[] regstr2 = toLiteralChar(regstr[2]);
        return code1~ code2~ "("~ch~">="~regstr0~" && "~ch~"<="~regstr2~") || "~charMatches(regstr[3..$], ch, options); 
      } 
    } 
    else if (regstr.length >= 2 && regstr[0..2] == "\\w") {
        return charMatches("a-zA-Z0-9_", ch, options) ~ " || "~charMatches(regstr[2..$], ch, options);
      }
      else if (regstr.length >= 2 && regstr[0..2] == "\\d") { 
          return charMatches("0-9", ch, options)~" || "~charMatches(regstr[2..$], ch, options); 
        }
        else if (regstr.length >= 2 && regstr[0..2] == "\\s") { 
            return charMatches(" \t\n\r", ch, options)~" || "~charMatches(regstr[2..$], ch, options); 
          }
          else if (regstr.length >= 2 && regstr[0..2] == "\\W") {
              return "!("~charMatches("a-zA-Z0-9_", ch, options) ~ ") || "~charMatches(regstr[2..$], ch, options);
            }
            else if (regstr.length >= 2 && regstr[0..2] == "\\D") { 
                return "!("~charMatches("0-9", ch, options)~") || "~charMatches(regstr[2..$], ch, options); 
              }
              else if (regstr.length >= 2 && regstr[0..2] == "\\S") { 
                  return "!("~charMatches(" \t\n\r", ch, options)~") || "~charMatches(regstr[2..$], ch, options); 
                }
                else if (regstr[0] == '\\')
                  {
                    if (regstr.length == 1)
                    {
                      assert(0,"\nError:a character is missing after \\");
                    }
                    char[] regstr0 = toLiteralChar(regstr[1]);
                    return "("~ch~"=="~regstr0~") || "~charMatches(regstr[2..$], ch, options);
                  } 
                  else
                  { 
                    char[] regstr0 = toLiteralChar(regstr[0]);
                    return "("~ch~"=="~regstr0~") || "~charMatches(regstr[1..$], ch, options);}
}


//---------------------------------------------------------------------
// Part III: the public interface of the regexp engine
//---------------------------------------------------------------------

// Does the regexp match the pattern?
template test(char [] fullpattern)
{
  
  bool test(char [] searchstr, char [][] param...) {
    int p = 0; // start at the beginning of the string
    grouprec [] group;
    mixin (parseRegexp(fullpattern));
    return engine();
  }
}

class screg(char [] fullpattern)
{
  private:
  int p; // next index to test
        //int groupno=0;
  int x;
  
  char[] searchstr;
  char[][9] param;
  public:
  grouprec [] group;
  this()
  { 
    p = 0; 
  } 
  this(int startp, char[][]parameters...)
  { 
    p = startp; 
    int i;
    foreach(par;parameters)
    param[i++] = par; 
  } 
  mixin (parseRegexp(fullpattern, true));
  alias match matches;
  bool match(char[] searchstrin)
  {
    group.length = 0;
    searchstr = searchstrin;
    //pragma(msg,"screg.match:"~fullpattern);
    for (int x = p; x<searchstr.length;++x) {
      p = x; 
      if (engine()) {
        if (group.length == 0)
        {
          group.length = 1;
        } 
        group[0] = grouprec(x, p);
        return true;
      }
    }
    return false;
  }
  bool gmatch(char[] searchstrin)
  {
    group.length = 0;
    searchstr = searchstrin; 
    if (engine()) {
      if (group.length == 0)
      {
        group.length = 1;
      } 
      group[0] = grouprec(x, p);
      return true;
    } 
    return false;
  }
  char[] _(int groupno)
  {
    return .group(searchstr, group, groupno); 
  }
  
  char[] opIndex(int groupno)
  {
    return .group(searchstr, group, groupno); 
  }
  bool exists(int groupno)
  {
    if (group.length >= groupno)
      return false;
    if (groupno<0)
      return false;
  } 
  alias ismatched defined;
  bool ismatched(int groupno)
  {
    if (groupno >= group.length)
      return false;
    return (group[groupno].end !=  - 1);
  }
  int pos()
  {
    return p;
  } 
  void pos(int pin)
  {
    p = pin;
  } 
  void restart()
  {
    p = 0;
  } 
}

/// Return first substring which matches the pattern.
/// Note that some patterns will return an empty string as a valid result.
//template search
//{
char [] search(char [] fullpattern)(char [] searchstr, char [][] param...) {
  int p; // next index to test
        //int groupno=0;
  grouprec [] group;
  //pragma(msg,parseRegexp(fullpattern));
  mixin (parseRegexp(fullpattern));
  for (int x = 0; x<searchstr.length;++x) {
    p = x;
    if (engine()) return searchstr[x..p];
  }
  return null; // no match
}
//}

//simple version, escapes not supported
char [] parsetr(char[] fullpattern)
{
  if (fullpattern.length<3 || fullpattern[0..1] != "/")
    assert(0,"tr has syntax error");
  int i;
  char[] code ="char c2;\nswitch(c){";
  int s1, e1, s2, e2;
  s1 = 1;
  for (i = s1;i<fullpattern.length;i++)
  {
    if (fullpattern[i] == '/')
    {
      e1 = i;
      break; 
    } 
  } 
  if (e1 == 0)
  assert(0,"tr has syntax error,/ missing");
  s2 = e1 + 1;
  
  for (i = s2;i<fullpattern.length;i++)
  {
    if (fullpattern[i] == '/')
    {
      e2 = i;
      break; 
    } 
  } 
  
  if (e2 == 0)
  assert(0,"tr has syntax error,last / missing");
  if (e2 - s2 != e1 - s1)
    assert(0,"input character set is not the same as output character set"); 
  for (i = s1;i<e1;i++)
  {
    char[] c = fullpattern[i..i + 1];
    if (c == "'")
      c = "\\'";
    char[] c2 = fullpattern[s2..s2 + 1];
    s2++;
    if (c2 == "'")
      c2 = "\\'"; 
    code~="case '"~c~"': c2='"~c2~"';break;\n"; 
  } 
  
  code~="default: c2=c;}";
  
  char[]code2 = "char[] convert(){
        char[] outstr;
        foreach(c;convertable)
        {
      "~code~"
        outstr~=c2;
        }
    return outstr;}
    ";
    //assert(0,code2);
  return code2;
}

char [] parselistofwords(char[] list)
{
  
  int i;
  char[] code = "switch(str){";
  int s1, e1, s2, e2;
  s1 = 1;
  char[][] strs;
  while (i<list.length)
  {
    int j = i;
    while (list[j] >= '0' && list[j] <= '9' || 
           list[j] >= 'a' && list[j] <= 'z' || 
           list[j] >= 'A' && list[j] <= 'Z' || list[j] == '_' )
    {
      j++;
      if (j >= list.length)
        break;
    } 
    if (i != j)
    {
            //str[list[i..j]]=true;
      code~="case \""~list[i..j]~"\": found=true;break;\n"; 
      i = j;
    } 
    else
      i++;
  } 
  
  code~="default: found=false;}";
  
  char[]code2 = "bool ismatched(){
        bool found;
      "~code~"
    return found;}
    ";
    //assert(0,code2);
  return code2;
}

bool matchlist(char [] list)(char [] str) {
 // int something;
  //pragma(msg,parseRegexp(fullpattern));
  mixin (parselistofwords(list));
  //char[] o;//=convert_();
  return ismatched; 
}



// usage: tr!("/a/b/")(str)
char [] tr(char [] fullpattern)(char [] convertable) {
 // int something;
  //pragma(msg,parseRegexp(fullpattern));
  mixin (parsetr(fullpattern));
  //char[] o;//=convert_();
  return convert; // no match
}






//template searchgroups(char [] fullpattern)
//{
grouprec [] indexgroups(char [] fullpattern)(char [] searchstr, char [][] param...) {
  int p; // next index to test
        //int groupno=0;
  grouprec [] group;
         // pragma(msg,"here 3");
  mixin (parseRegexp(fullpattern));// engine;
  
  for (int x = 0; x<searchstr.length;++x) {
    p = x; 
    if (engine()) {
      if (group.length == 0)
      {
        group.length = 1;
      } 
      group[0] = grouprec(x, p);
      return group;
    }
  }
  return null; // no match
}
//}
grouprec [][] indexgroupsall(char [] fullpattern)(char [] searchstr, int startindex = 0, char [][] param = []) {
  int p; // next index to test
  grouprec [] group;
  mixin (parseRegexp(fullpattern));
  grouprec [][] solutions;
  int soli = 0;
  for (int x = startindex; x<searchstr.length;++x) {
    p = x;
    if (engine()) 
    { 
      if (group.length == 0)
      {
        group.length = 1;
      } 
      group[0] = grouprec(x, p);
      solutions.length = soli + 1;
      solutions[soli] = group;
      soli++;
      x = p - 1;
    }
  }
  return solutions; // return all
}

char [] group(char[] str, grouprec [] g, int groupno)
{
  if (g[groupno].end ==  - 1)
  {
    return []; 
  } 
  return str[g[groupno].start..g[groupno].end]; 
} 



template index(char [] fullpattern)
{
  int index(char [] searchstr, int startindex, char [][] param...) {
    int p; // next index to test
    grouprec [] group;
    int rp;
    mixin (parseRegexp(fullpattern));
    for (int x = startindex; x<searchstr.length;++x) {
      p = x;
      rp = 0;
      if (engine()) return x;
    }
    return - 1; // no match
  }
}

struct indexrec
{
  int start;
  int end; //as for array slices, last char + 1
}

struct grouprec
{
  int start;
  int end =  - 1; //as for array slices, last char + 1
  char[] toString()
  {
    version(Tango)
    return Stdout.layout.convert("[{},{}]", start, end);
    else
      return format("[%d,%d]", start, end);
  } 
}

template index2(char [] fullpattern)
{
  indexrec index2(char [] searchstr, int startindex, char [][] param...) {
    int p; // next index to test
    int rp;
    grouprec [] group;
    mixin (parseRegexp(fullpattern));
    for (int x = startindex; x<searchstr.length;++x) {
      p = x;
      rp = 0;
      if (engine()) return indexrec(x, p);
    }
    return indexrec( - 1, - 1); // no match
  }
}

template indexall(char [] fullpattern)
{
  indexrec[] indexall(char [] searchstr, int startindex = 0, char [][] param = []) {
    int p; // next index to test
    grouprec [] group;
    mixin (parseRegexp(fullpattern));
    indexrec[] solutions;
    int soli = 0;
    for (int x = startindex; x<searchstr.length;++x) {
      p = x;
      if (engine()) 
      { 
        solutions.length = soli + 1;
        solutions[soli] = indexrec(x, p);
        soli++;
        x = p - 1;
      }
    }
    return solutions; // return all
  }
}

template indexalloverlapping(char [] fullpattern)
{
  indexrec[] indexalloverlapping(char [] searchstr, int startindex = 0, char [][] param = []) {
    int p; // next index to test
    grouprec [] group;
    mixin (parseRegexp(fullpattern));
    indexrec[] solutions;
    int soli = 0;
    for (int x = startindex; x<searchstr.length;++x) {
      p = x;
      if (engine()) 
      { 
        solutions.length = soli + 1;
        solutions[soli] = indexrec(x, p);
        soli++;
      }
    }
    return solutions; // return all
  }
}




template searchall(char [] fullpattern)
{
  char[][] searchall(char [] searchstr, char [][] param...) {
    int p; // next index to test
    grouprec [] group;
       //  pragma(msg, "here"~parseRegexp(fullpattern));
    mixin (parseRegexp(fullpattern));
    char[][] solutions;
    int soli = 0;
    for (int x = 0; x<searchstr.length;++x) {
      p = x;
            //writefln("starting ",x);
      if (engine()) 
      { 
        solutions.length = soli + 1;
        solutions[soli] = searchstr[x..p];
              //writefln(">>", searchstr[x..p], "<<");
        soli++;
        x = p - 1;
      }
    }
    return solutions; // return them
  }
}

template searchalloverlapping(char [] fullpattern)
{
  char[][] searchalloverlapping(char [] searchstr, char [][] param...) {
    int p; // next index to test
    grouprec [] group;
       //  pragma(msg, "here"~parseRegexp(fullpattern));
    mixin (parseRegexp(fullpattern));
    char[][] solutions;
    int soli = 0;
    for (int x = 0; x<searchstr.length;++x) {
      p = x;
            //writefln("starting ",x);
      if (engine()) 
      { 
        solutions.length = soli + 1;
        solutions[soli] = searchstr[x..p];
              //writefln(">>", searchstr[x..p], "<<");
        soli++;
      }
    }
    return solutions; // return them
  }
}
version(none)
//version(shortscregexpfuncnames)
{
  alias test t;
  alias index i;
  alias index2 i2;
  alias search s;
  alias searchall sa;
  alias indexall ia;
  alias indexgroups ig;
  alias indexgroupsall iga;
}



//---------------------------------------------------------------------
//                         EXAMPLE
//---------------------------------------------------------------------
version(Phobos)
import std.stdio;
version(test)
{
  void main()
  {
    version(Phobos)
    writefln("BEGINNING UNIT TESTS\n");
    else 
      Stdout("BEGINNING UNIT TESTS\n").newline;
    assert(search!("ab")("aaab") == "ab"); 
    
    
    assert(search!("a*b")("aaab") == "aaab"); 
    assert(search!("a*(b)")("aaab") == "aaab"); 
    
    assert(search!("((a*b))")("aaab") == "aaab"); 
    assert(search!("(a*)b")("aaab") == "aaab"); 
    
    assert(search!("(?:b*a*)*b")("aaab") == "aaab"); 
    
    assert(search!("b+cd")("acdbbcabbcdaaab") == "bbcd");
    
    assert(search!("b?cd")("abcacbacdb") == "cd");
    
    assert(search!("(ab)?abc")("aababcab") == "ababc");
    assert(search!("(?:ab)*abc")("aababcab") == "ababc");
    assert(search!("((?:a)*|xyz)b")("aaab") == "aaab"); 
    
    assert(search!("(?:ab)*(abb)")("bababb") == "ababb"); 
    assert(search!("e?(?:ab)*b+?")("eaaababbbbaac") == "ababb");
    assert(search!("(?:ab*)*c")("bbbababbaaabaaaabbbbc") == "ababbaaabaaaabbbbc");
    char [] quasistatic = "m";
    assert(search!("(@1.*?@1)")("they said D can't do metaprogramming?", quasistatic) == "metaprogram");
    assert(search!("[h-za]*g")("metaprogramming") == "taprog");
    assert(search!("(?:a*)*b")("cacaaab") == "aaab");
    assert(search!("(?:a*b*)*c")("dababdaabababbaaabbbcab") == "aabababbaaabbbc");
    assert(search!("(?:(?:a*b*)|da)*b")("fasdaaab") == "daaab");
    assert(search!("aaab??")("aaabbb") == "aaa");
    assert(search!("aaab?")("aaabbb") == "aaab");
    //assert(search!("aaa?")("aa") == "aa");
    
    char [] qq;
    version(Phobos)
    writefln("=========");
    version(Tango)
    Stdout("=========").newline;
    qq = search!("(?:(?:a*b*)|da)*b")("fasdaaab");
    version(Phobos) writefln("Result: ----", qq, "---");
    version(Tango) Stdout("Result: ----", qq, "---").newline;
    version(Phobos) writefln("END OF UNIT TESTS\n");
    version(Tango) Stdout("END OF UNIT TESTS\n").newline;
    version(Phobos) writefln("All tests are passed if you set -debug");
    version(Tango) Stdout("All tests are passed if you set -debug").newline;
    
  }
}
//-------------------------------------------------------------------------------
/+

// NOT CURRENTLY USED

// Finds the number of instances of 'ch' in str which aren't preceded by a backslash
// ch must not be a backslash.
template unescapedCount(char [] str, char ch)
{
    static if (str.length==0) const int unescapedCount = 0;
    else static if (str[0]=='\\' && str.length>1) const int unescapedCount = unescapedCount!(str[2..$], ch);
    else static if (str[0]==ch) const int unescapedCount = 1 + unescapedCount!(str[1..$], ch);
    else const int unescapedCount = unescapedCount!(str[1..$], ch);
}

+/



void searchgroupstest(char[]reg)(char[]input)
{
  version(Phobos)
  writefln("reg:%s", reg," input:%s", input);
  version(Tango)
  Stdout.format("reg:{} input:{}", reg, input).newline;
  int groupno = 0;
  foreach(e;indexgroups!(reg)(input))
  {
    if (e.start <= e.end)
    {
      version(Phobos)
      writefln("group %d:>>%s<<", groupno, input[e.start..e.end]);
      version(Tango)
      Stdout.format("group {}:>>{}<<", groupno, input[e.start..e.end]).newline;
    }
    else
    {
      version(Phobos)
      writefln("group %d:", groupno, "[", e.start, ",", e.end, "]");
      version(Tango)
      Stdout.format("group {}:", groupno, "[", e.start, ",", e.end, "]").newline;
    } 
    groupno++;
  } 
  version(Phobos) writefln("-------------------"); 
  version(Tango) Stdout("-------------------").newline;
} 

void searchgroupsalltest(char[]reg)(char[]input)
{
  int sno = 0;
  
  version(Phobos)
  writefln("reg:%s", reg," input:%s", input);
  version(Tango)
  Stdout.format("reg:{} input:{}", reg, input).newline;
  foreach(s;indexgroupsall!(reg)(input))
  {
    version(Phobos) writefln("solution ", sno++);
    version(Tango) Stdout.format("solution {}", sno++).newline;
    foreach(e;s)
    {
      if (e.start <= e.end)
      {
        version(Phobos) writefln("group >>%s<<", input[e.start..e.end]);
        version(Tango)Stdout.format("group >>{}<<", input[e.start..e.end]).newline; 
      }
      else
      {
        version(Phobos) writefln("group %s", e.start," ", e.end);
        version(Tango)Stdout.format("group {} {}", e.start, e.end).newline;
      } 
    }
  } 
  version(Phobos) writefln("-------------------"); 
  version(Tango)Stdout("-------------------").newline; 
} 
void searchgroupstest2(char[]reg)(char[]input, char[][] target)
{
  version(Phobos) writefln("reg:%s", reg," input:%s", input);
  version(Tango)Stdout.format("reg:{} input:{}", reg, input).newline;
  pragma(msg, "searchgroupstest2:"~reg);
  int i = 0;
  int oi = 0;
  int failed = 0;
  foreach(e;indexgroups!(reg)(input)) {
    bool compare = true;
    if (e.start <= e.end)
    {
      version(Phobos) writef("group", i," >>%s<<", input[e.start..e.end]);
      version(Tango)Stdout.format ("group {} >>{}<<", i, input[e.start..e.end]);
    }
    else
    {
      version(Phobos) writef("group", i," ","not matched [", e.start," ", e.end, "]");
      version(Tango)Stdout.format ("group {} not matched [{} {}]", i, e.start, e.end);
    } 
    if (i >= target.length)
    {
      //writefln("\nnumber of groups failed");
      failed++; 
      //writefln("\n");
      compare = false;
    } 
 //   writefln(">range ",e.start," ",e.end);
    if (e.start>e.end )
    {
   //   writefln(">range ",e.start," ",e.end);
      if (target.length>i && target[i] is null)
      {
        version(Phobos) writefln(" passed");
        version(Tango)Stdout (" passed").newline;
      }
      else
      {
        version(Phobos) writefln(" failed");
        version(Tango)Stdout (" failed").newline;
        failed++;
      }
    } 
    else if (compare && input[e.start..e.end] == target[i])
      {
        version(Phobos) writefln(" passed"); 
        version(Tango)Stdout (" passed").newline;
      } 
      else
      {
        if (compare)
        {
          version(Phobos) writefln(" failed expected %s", target[i]); 
          version(Tango)Stdout.format (" failed expected {}", target[i]).newline;
        } 
        failed++;
    }
    oi++;
    i++;
  } 
  if (oi != target.length)
  {
    version(Phobos) writefln("number of groups failed"); 
    version(Tango)Stdout ("number of groups failed").newline; 
    failed++;
  }
  else
  {
    version(Phobos) writefln("number of groups is passed"); 
    version(Tango)Stdout ("number of groups is passed").newline; 
  }
  version(Phobos) writefln("-------------------");
  version(Tango)Stdout ("-------------------").newline;
  if (failed>0)
  {
    version(Phobos) writefln("test failed"); 
    version(Tango)Stdout ("test failed").newline;
    assert(0);
  } 
  else
  {
    version(Phobos) writefln("test ok"); 
    version(Tango)Stdout ("test ok").newline;
  } 
} 

void printcode(char[] reg)
{
  version(Phobos) writefln("%s", parseRegexp(reg));
  version(Tango)Stdout.format ("{}", parseRegexp(reg)).newline;
}

void printclasscode(char[] reg)
{
 version(Phobos) writefln("%s", getclasscode(reg));
 version(Tango)Stdout.format ("{}", getclasscode(reg)).newline;   
}

char[] getclasscode(char[] reg)
{
  char [] code;
code="
version(Tango)
{}
else
{ version = Phobos;}
version(Phobos)
import std.string;
version(Tango)
{
  import tango.text.Ascii;
  alias toUpper toupper;
  alias toLower tolower;
  alias icompare icmp;
  import tango.io.Stdout;
}
struct grouprec
{
  int start;
  int end =  - 1; //as for array slices, last char + 1
  char[] toString()
  {
    version(Tango)
    return Stdout.layout.convert(\"[{},{}]\", start, end);
    else
      return format(\"[%d,%d]\", start, end);
  } 
} 
char [] group(char[] str, grouprec [] g, int groupno)
{
  if (g[groupno].end ==  - 1)
  {
    return []; 
  } 
  return str[g[groupno].start..g[groupno].end]; 
} 
 
class screg
{
  private:
  int p; // next index to test
        //int groupno=0;
  int x;
  
  char[] searchstr;
  char[][9] param;
  public:
  grouprec [] group;
  this()
  { 
    p = 0; 
  } 
  this(int startp, char[][]parameters...)
  { 
    p = startp; 
    int i;
    foreach(par;parameters)
    param[i++] = par; 
  }"~ 
  parseRegexp(reg, true)~
  "
  alias match matches;
  bool match(char[] searchstrin)
  {
    group.length = 0;
    searchstr = searchstrin;
    //pragma(msg,\"screg.match:\"~fullpattern);
    for (int x = p; x<searchstr.length;++x) {
      p = x; 
      if (engine()) {
        if (group.length == 0)
        {
          group.length = 1;
        } 
        group[0] = grouprec(x, p);
        return true;
      }
    }
    return false;
  }
  bool gmatch(char[] searchstrin)
  {
    group.length = 0;
    searchstr = searchstrin; 
    if (engine()) {
      if (group.length == 0)
      {
        group.length = 1;
      } 
      group[0] = grouprec(x, p);
      return true;
    } 
    return false;
  }
  char[] _(int groupno)
  {
    return .group(searchstr, group, groupno); 
  }
  
  char[] opIndex(int groupno)
  {
    return .group(searchstr, group, groupno); 
  }
  bool exists(int groupno)
  {
    if (group.length >= groupno)
      return false;
    if (groupno<0)
      return false;
  } 
  alias ismatched defined;
  bool ismatched(int groupno)
  {
    if (groupno >= group.length)
      return false;
    return (group[groupno].end !=  - 1);
  }
  int pos()
  {
    return p;
  } 
  void pos(int pin)
  {
    p = pin;
  } 
  void restart()
  {
    p = 0;
  } 
}
";  
  return code;
}  

//-------------
// unit tests
//-------------
version (testmeta) {
  static assert(quantifierConsumed("{456}345") == 5);
  static assert(parenConsumed("(45(6)4)5") == 8);
  static assert(parenConsumed(`(45\(6)45`) == 7);
}

/*
Copyright (c) 2006 Walter Bright
(basic framework, regular expression engine, basic documentation)
Copyright (c) 2007-2009 Marton Papp
(added /w,/s,/d,extended character classes, added groups and backreferences,
 options (msxi), extended documentation, non-greedy constucts
 converted testing functions into Tango 
)
Copyright (c) 2008  (yidabu  g m a i l at com) All rights reserved
*modified by yidabu to make it work with Tango
( D Programming Language China : http://www.d-programming-language-china.org/ )        
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/