/* dtest.d*/
import std.stdio;
import std.c.time;
import std.perf;
import stonespace;
import std.string;
import std.regexp;
import ministl;
static import meta.regexp3;


void main ()
{
  stone0();
  stone("start");
  stone("timer test");
  //append string
  char[] s;
  for (auto i=0;i<1000;i++)
  {
    s~="12323434662xxx434";
  }
  stone("append test 1 ");
  char[] tos;
  for (int i = 0;i<1000;i++)
  {
    tos= toString(i);
    tos= toString(i);
    tos= toString(i);
    tos= toString(i);
    tos= toString(i);
    tos= toString(i);
  }
  stone("tostring test 1 ");
  char[] s2;
  for (auto i=0;i<1000;i++)
  {
    s2~="12323434662xxx434";
    s2~="12323434662xxx434";
    s2~="12323434662xxx434";
  }
  stone("append test 2 ");
 for (auto i=0;i<10000;i++)
  {
    s2~="12323434662xxx434";
    s2~="12323434662xxx434";
    s2~="12323434662xxx434";
  }
  stone("append test 3 ");
   char[] keysa[10000/4];
    for (auto i=0;i<10000/4;i++)
    {
      keysa[i]="ddddd"~toString(i);
    }
   stone("tostring+array fill test");
   int hash[char[]];
   for (auto i=0;i<10000/4;i++)
  {
  
    hash[keysa[i]]=i;
    hash[keysa[i]]=i;
    hash[keysa[i]]=i;
    hash[keysa[i]]=i;
  }
   stone("fill associative array test  ");
    
    for (auto i=0;i<10000/4;i++)
  {
   if (hash[keysa[i]])
   {

    }
  }
   stone("find keys in associative array test  ");
    for (auto i=0;i<10000/4;i++)
  {
  
    hash.remove(keysa[i]);
  }
   stone("remove associative array test  ");
   
  
     auto m = std.regexp.search("abcdef", "c");
     for (auto i=0;i<100/5;i++)
     {
     m = std.regexp.search("abcdef", "c");
      m = std.regexp.search("abcdef", "c");
       m = std.regexp.search("abcdef", "c");
        m = std.regexp.search("abcdef", "c");
        m = std.regexp.search("abcdef", "c");
        }
  stone("simple regexp search  ");
  char[] inp="CREATE PACKAGE BODY b IS

PROCEDURE proc1 IS
BEGIN
IF 7 <> 5 THEN
FOR rec IN (SELECT * FROM dual
                  WHERE g = 5) LOOP
NULL;
END LOOP;
    END IF;
END;
  
PROCEDURE recurse IS
   b number:=5;
   d456 number:=456;
cursor one is 
select list 
from todo;
BEGIN
    select star from sky
      where star=(select star
                  from catalogue
                  where r>3 
                      and brightness>5
                  );
    recurse    ;
    proc1;
    a := (a +        1
          +4
          + 5
          + 8);
    c := f + 4 + 34;
    total := earth +sky;
    
    --this is comment
    
    uk:=h;
    g:=l;
           exception
           when no_data then
           hello;
  END;
  
  BEGIN
    NULL;
END;
";
 int ii;
  foreach(m; RegExp("((--.*?$)|(\".*?\")|((\\'.*?\\')+)|(\\/\\*.*?\\*\\/)|([a-zA-Z_][\\da-zA-Z_\\#\\$]*(\\.([a-zA-Z_][\\da-zA-Z_\\#\\$]*|\\*))*)|([\t ]+|[\n][\t ]*)|(\")|(\\')|(=>|\\:=|\\|\\||<>|!=|<=|>=|~=|\\^=|\\.\\.|.))"
 ).search(inp))
     {
       ii++;
       // writefln(">>", m.match(0), "<<");
     }
    stone("complex regexp search  ");
    char[] tokens[];
    tokens.length=1000;
    long tokenid=0;
   foreach(m; RegExp("((--.*?$)|(\".*?\")|((\\'.*?\\')+)|(\\/\\*.*?\\*\\/)|([a-zA-Z_][\\da-zA-Z_\\#\\$]*(\\.([a-zA-Z_][\\da-zA-Z_\\#\\$]*|\\*))*)|([\t ]+|[\n][\t ]*)|(\")|(\\')|(=>|\\:=|\\|\\||<>|!=|<=|>=|~=|\\^=|\\.\\.|.))"
 ).search(inp))
     {
       if (tokenid>=tokens.length)
       {
        tokens.length=tokens.length*2;
       }
        tokens[tokenid++]=m.match(0);
       // writefln(">>", m.match(0), "<<");
     }
  
  stone("fill array+complex regexp search  ");
   char[] tokens2[];
    tokens2.length=1000;
    long tokenid2=0;
long i=meta.regexp3.unescapedFindFirst!("[\\#\\$]*(\\.([a-zA-Z_][\\da-zA-Z_\\#\\$]*|\\*))*",']');
  foreach(m2; meta.regexp3.searchall!("((--.*?$)|(\".*?\")|((\\'.*?\\')+)|(\\/\\*.*?\\*\\/)|([a-zA-Z_][\\da-zA-Z_\\#\\$]*(\\.([a-zA-Z_][\\da-zA-Z_\\#\\$]*|\\*))*)|([\t ]+|[\n][\t ]*)|(\")|(\\')|(=>|\\:=|\\|\\||<>|!=|<=|>=|~=|\\^=|\\.\\.|.))"
  )(inp))
/* foreach(m2; meta.regexp3.searchall!("[\\da-zA-Z_\\#\\$]*(\\.([a-zA-Z_][\\da-zA-Z_\\#\\$]*|\\*))*"
 )(inp))*/
     {
       if (tokenid2>=tokens2.length)
       {
        tokens2.length=tokens2.length*2;
       }
        tokens[tokenid2++]=inp[m2.start..m2.end];
       // writefln(">>", m.match(0), "<<");
     }
  
  stone("fill array+complex statically compilerd regexp search  ");
   writefln("tokens:", tokenid);
   stone ("writefln");
   vector!(int) v=new vector!(int)(10000);
   for (int i=0;i<9999;i+=3)
   {
     v[i]=i;
     v[i+1]=i;
     v[i+2]=i;
   }
   stone ("vector test fill 10000");
   scope vector!(int) v3=new vector!(int)(10000);
   for (int i=0;i<9999;i+=3)
   {
     v3[i]=i;
     v3[i+1]=i;
     v3[i+2]=i;
   }
   stone ("vector on stack test fill 10000");
   vector!(int) v2=new vector!(int)(10000);
   for (int i=0;i<9999;i+=3)
   {
     v2.v[i]=i;
     v2.v[i+1]=i;
     v2.v[i+2]=i;
   }
   stone ("vector test (with hack) fill 10000");
   int[] arr=new int [10000];
   for (int i=0;i<9999;i+=3)
   {
     arr[i]=i;
     arr[i+1]=i;
     arr[i+2]=i;
   }
  stone ("array test fill 10000");
}

/*stone.d*/
//#include <hrt/performance_counter.hpp>
//#include <hrt/time_provider.hpp>
//#include <hrt/system_time.hpp>
module stonespace;

import std.stdio;
import std.c.time;
import std.perf;

debug {
  void main ()
  {
    
    ini();
    accbegin("timer");
    std.c.time.msleep(300);
    accend("timer");
    accbegin("timer2");
    std.c.time.msleep(300);
    accend("timer2");
    pacctime("timer");
    pacctime("timer2");
    ptotalacctime();
    stone0;
    std.c.time.msleep(300);
    stone("point 1");
    std.c.time.msleep(100);
     stone("point 2");
    std.c.time.msleep(50);
     stone("point 3");
    accbegin("timer3");
     accend("timer3");
      pacctime("timer3");
  }
}



  //raw_time_type stime = 0;
ulong stime = 0;
static ulong[char[]] acc; 
ulong [char[]] lasttime; 
HighPerformanceCounter hpc;
void ini()
{
 hpc = new HighPerformanceCounter();
 //hpc.start();
   //provider = (new time_provider_type)->instance();
   //stime = 0;
  stime = hpc.microseconds();
}
void stonex (char[] name)
{
  
}

void accend(char[] name)
{
  hpc.stop();
  ulong t1 = hpc.microseconds();
  //   std::cout << "procid" << GetCurrentProcessId() << endl; 
     //std::cout << "accbefore " << acc[name.c_str()]  <<endl;  
  acc[name] += t1;
  
     //std::cout << "diff " << (t1-stime)  <<endl; 
     //std::cout << "accend " << acc[name.c_str()]  <<endl; 
     //stime = t1;
    debug (3) {
      writefln("accend acc name ",acc[name], name, ' ',t1);
     
     }
  lasttime[name] = hpc.microseconds(); 
} 
void accini(char[] name)
{ 
  acc[name] = 0; 
} 
void accbegin(char[] name)
{ 
    // acc[name.c_str()]=0;  
  hpc.start();
  lasttime[name] = hpc.microseconds(); 
  debug (3) {
   writefln("lasttime ",name, " ",lasttime[name]);}
} 

ulong acctime(char[] name)
{
  return acc[name]; 
} 
void pacctime(char[] name)
{
 
  float sec = cast(float)acc[name] / (cast(float)1000000);
   // provider.systemtime_from_rawtime(acc[name.c_str()],&st);
  writefln("accumulated time of " , name , ":" ,  sec  ); 
} 
void ptotalacctime()
{
  ulong total = 0;
  foreach (ulong v;acc)
  {
    total += v;
  }
  float sec = cast(float)total / (cast(float)1000000);
  writefln("total accumulated time:",  sec ) ; 
}
void stone0()
{
    //return;
  ini();
  hpc.start(); 

}

void stone(char[] name)
{
    //return;
 hpc.stop();
  ulong t1 = hpc.microseconds(); 
  
  if (stime>0 )
  {
    float sec = cast (float)t1 / (cast(float)1000000); 
    writefln ("stone " , name , " " , "%f",sec );
  }
  else
    {
    writefln ("stone " , name , " " , "%f",0.0 );
  }
  stime = 1; 
  hpc.start();
}

/*regexp3.d*/
// Compile-time regular expression parser, version 2.0
// Author: Don Clugston, borrowing heavily from the 1.0 parser written by Eric Anderton.
// This version uses mixins for simplicity, flexibility, and high performance.

// 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".

/*
Features currently supported:
   * 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
   other characters match themselves
   a|b   match regular expression a or b
   uncaptured grouping via ( )
   ^   start of line
   [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).
   
   All matches are lazy, rather than greedy.
   
Planned, but not yet supported:
   $   end of line
   captured grouping
   escape characters
   word matching
   greedy matching
   full diagnostic error messages
  
Possible:
  an optimisation pass, including features such as searching the pattern in reverse order.
  \1..\9 to match previously captured subsequences
  Perl 6 syntax
   
*/

// 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 meta.regexp3;

//---------------------------------------------------------------------
// Part 0 : Functions from the meta library
//---------------------------------------------------------------------

/******************************************************
 *  ulong atoui!(char [] s);
 *
 *  Converts an ASCII string to an uint.
 */
template atoui(char [] s, uint result=0, int indx=0)
{
    static if (s.length==indx)
        const uint atoui = result;
    else static if (s[indx]<'0' || s[indx]>'9')
        const uint atoui = result;
    else 
        const uint atoui = atoui!(s, result * 10 + s[indx]-'0', indx+1);
}

//---------------------------------------------------------------------
// 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
template unescapedFindFirst(char [] regstr, char ch, int indx=0)
{
    static if (regstr.length<=indx)
        const int unescapedFindFirst = -1; // not found
    else static if (regstr[indx]==ch) const int unescapedFindFirst=indx;
    else static if (regstr[indx]=='\\')
        // if it's escaped, prevent it from matching.
        const int unescapedFindFirst = unescapedFindFirst!(regstr, ch, indx+2);
    else const int unescapedFindFirst = unescapedFindFirst!(regstr, ch, indx+1);
}

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

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

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

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

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

// find the index of the first |, or -1 if not found.
// ignores escaped items, and anything in parentheses.
template findUnion(char [] regstr, int indx=0, int numopenparens=0)
{
    static if (indx>=regstr.length)
        const int findUnion = -1;
    else static if (numopenparens==0 && regstr[indx]=='|')
        const int findUnion = indx;
    else static if (regstr[indx]==')')
        const int findUnion = findUnion!(regstr, indx+1, numopenparens-1);
    else static if (indx+2<regstr.length && regstr[indx..indx+3]=="(?:")
        const int findUnion = findUnion!(regstr, indx+3, numopenparens+1);
    else static if (regstr[indx]=='(')
        const int findUnion = findUnion!(regstr, indx+1, numopenparens+1);
    else static if (regstr[indx]=='\\') // skip the escaped character
        const int findUnion = findUnion!(regstr, indx+2, numopenparens);
    else 
        const int findUnion = findUnion!(regstr, indx+1, numopenparens);
}

// keeps going until the number of ) parens equals the number of ( parens.
// All escaped characters are ignored.
// BUG: what about inside [-] ?
template parenConsumed(char [] regstr, int numopenparens=0)
{
    static if (regstr.length==0) {
        pragma(msg, "Unmatched parenthesis");
        static assert(0);
    } else static if (regstr[0]==')') {
        static if (numopenparens==1) const int parenConsumed=1; // finished!
    else const int parenConsumed = 1 + parenConsumed!(regstr[1..$], numopenparens-1);
    } else static if (regstr.length>2 && regstr[0..3]=="(?:") {
        const int parenConsumed = 3 + parenConsumed!(regstr[3..$], numopenparens+1);
    } else static if (regstr[0]=='(') {
        const int parenConsumed = 1 + parenConsumed!(regstr[1..$], numopenparens+1);
    } else static if (regstr[0]=='\\' && regstr.length>1)
        // ignore \(, \).
        const int parenConsumed = 2 + parenConsumed!(regstr[2..$], numopenparens);
    else 
        const int parenConsumed = 1 + parenConsumed!(regstr[1..$], numopenparens);    
}

// the naked term, with no quantifier. Either an atom, or a subsequence.
template atomConsumed(char [] regstr)
{
    static if (regstr.length>2 && regstr[0..3]=="(?:") const int atomConsumed = parenConsumed!(regstr);
    else  static if (regstr[0]=='(') const int atomConsumed = parenConsumed!(regstr);
    else static if (regstr[0]=='[') const int atomConsumed = 1 + unescapedFindFirst!(regstr, ']');
    else static if (regstr[0]=='\\') { // escape character
        static if (regstr.length>0) {
            const int atomConsumed=2;
        } else  {
            pragma(msg, "Error: Regexp must not end with \\");
            static assert(0);
        }
    } else static if (regstr[0]=='@')  { // NONSTANDARD: referenced parameter
        const int atomConsumed=2;
    } else const int atomConsumed=1; // match single char
}

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

//---------------------------------------------------------------------
// 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 mixin is passed a subset of a regexp string.
// It generates a member function bool fn(), which updates a pointer p,
// and returns true if a match was found.

// Each mixin 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 mixin also recieves a template alias '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.fn 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.

template parseRegexp(char [] pattern)
{
    mixin alwaysTrue!() endSequence;
    mixin regSequence!(0,pattern, endSequence) allseq;
    alias allseq.fn fn;
}

template alwaysTrue() // used to mark the end of a sequence
{
   bool fn () { return true; }
}

// regstr is a sequence of productions, possibly containing a union
template regSequence(int groupno,char [] regstr, alias next)
{
    static if (findUnion!(regstr)==-1) {
        // No unions to worry about
        mixin regNoUnions!(groupno,regstr, next);
    } else {
        bool fn() {
            // Both halves of the union have the same next, inherited from the parent
            mixin regSequence!(groupno,regstr[0..findUnion!(regstr)], next) a;
            mixin regSequence!(groupno,regstr[findUnion!(regstr)+1..$], next) b;
            int oldp = p;
            if (a.fn()) return true;
            p = oldp;
            group.length=groupno+1;
            return b.fn();
        }
    }
}

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

// regstr is a sequence of terms, all of which must be matched
// Does not contain any unions
template regNoUnions(int groupno,char [] regstr, alias next)
{
    static if (regstr.length == termConsumed!(regstr)) {
        // there's only a single item (possibly including a quantifier)
        mixin regTerm!(groupno,regstr, next);
    } else {
        bool fn() {            
            mixin regSequence!(groupno+countGroups!(regstr),regstr[termConsumed!(regstr)..$], next) second;
            mixin regTerm!(groupno,regstr[0..termConsumed!(regstr)], second) first;
            return first.fn();
        }
    }
}
template regStop(int groupno, alias next)
{
     int bracketend=-1;
     bool fn() {
     bracketend=p;
     return next.fn();   
     }
}

// the term without a quantifier. Here we deal with embedded subsequences.
template regSingleTerm(int groupno,char [] regstr, alias next)
{
        static if (regstr.length>2 && regstr[0..3]=="(?:") {
            // A sequence always calls next.
            mixin regSequence!(groupno,regstr[3..$-1], next);
          }  
         else static if (regstr[0]=='(') {
            // A sequence always calls next.
            mixin regStop!(groupno+1, next) stop;
            mixin regSequence!(groupno+1,regstr[1..$-1], stop) a;
            bool fn() {
              int oldp=p;              
              bool r=a.fn();
              if (r)
              {
              if (group.length<=groupno+1)
              {
                 group.length=groupno+2;
              }   
              group[groupno+1]=grouprec(oldp,bracketend);
              writefln("grouprec1 ",oldp," ",p);
              }
              else
              {
              group.length=groupno+1;  
              }  
             return r;
              }
        } else  {
            // A simple atom doesn't call next, so we need to do it here.
            bool fn() {
                mixin regAtom!(regstr) a;
                return a.fn() && next.fn();
            }
        }
}

// 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
template regSequenceDontUpdateP(int groupno,char [] regstr)
{
    bool fn() {
        mixin regSequence!(groupno,regstr, endSequence) x;
        // It's only a successful match if _something_ was consumed
        if (p==theinitialp) return false;      
        int oldp = p;
        if (!x.fn()) 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.
template regTermTwice(int groupno,char [] regstr)
{
    static if (regstr.length>2 && regstr[0..3]=="(?:") {
        bool fn()
        {
            // 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;
            mixin regSequenceDontUpdateP!(groupno,regstr[3..t-1]) suddendeath; //groupno may be incorrect but does not matter
            mixin regSequence!(groupno,regstr[3..t-1], suddendeath) a;
            return a.fn();
       }
      } 
      else static if (regstr[0]=='(') {
        bool fn()
        {
            // 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;
            mixin regSequenceDontUpdateP!(groupno+1,regstr[1..t-1]) suddendeath;
            mixin regSequence!(groupno+1,regstr[1..t-1], suddendeath) a;
             int oldp=p;              
              bool r=a.fn();
              if (r)
              {
              if (group.length<=groupno+1)
              {
                 group.length=groupno+2;
              }  
              group[groupno+1]=grouprec(oldp,p);
              writefln("grouprec ",oldp," ",p);
              }
              else
              {
              group.length=groupno+1;  
              }
             return r;
            //return a.fn();
       }
    } else {
            bool fn() {
                // It's easy with atoms, because we know they always eat something.
                // BUG: Maybe this will fail when null @n strings are passed in?                
                mixin regAtom!(regstr) a;
                return a.fn();
            }    
    }
}

// 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.
template regTerm(int groupno,char [] regstr, alias next)
{
    static if (atomConsumed!(regstr)==regstr.length) {
            // there is no quantifier, just use the naked term
       mixin regSingleTerm!(groupno,regstr, next);
    } else {
        bool fn() {
            const int t = atomConsumed!(regstr);
            const int qc =quantifierConsumed!(regstr[t..$]);
            const uint repmin = quantifierMin!(regstr[t..$]);
            const uint repmax = quantifierMax!(regstr[t..$]);
            const uint greedy = quantifierGreediness!(regstr[t+qc..$]);
            
            // 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
            mixin regTerm!(groupno,regstr[0..t], next) atomAndNext;

            debug writefln(fullpattern, " Quantifier ",regstr ,  " starting at ", searchstr[p..$]);
            
            static if (repmin == 0 && repmax == 1) { 
                // "?", or "{0,1}". Worth optimising seperately
                int oldp = p;
                static if (!greedy)
                {
                if (next.fn()) { return true; }
                p = oldp;
                return atomAndNext.fn();
                }
                else //greedy
                {
                     // pragma(msg, "?greedy");
                if (atomAndNext.fn())
                  {
                    return true;
                  } 
                p = oldp;
                if (next.fn())
                {
                  return true;       
                }  
                p = oldp;
                return false;  
                }
            } else {
                // 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.                       
                  mixin regTermTwice!(groupno,regstr[0..t]) atomonly;

                static if (repmin==0 && repmax == uint.max) {
                    // optimise for "*", "{0,}"
                    static if (!greedy) 
                    {
                    int oldp=p;
                    if (next.fn()) return true; // We can finish right now.
                    p=oldp;
                    do {
                      // Can we do (atom).(next) ?
                      oldp = p;
                      if (atomAndNext.fn()) { 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.fn() && p != oldp);
                    return false;
                    }
                    else // greedy
                    {
                     int oldp;
                     int veryoldp=p;    
                     grouprec [] savegroups;  
                     int newp=-1;            
                   // p=oldp;
                    do {
                      // Can we do (atom).(next) ?
                      oldp = p;
                      if (atomAndNext.fn()) 
                      { newp=p; 
                        savegroups.length=group.length-(groupno+1);
                        if (savegroups.length>0)
                        {
                        savegroups[0..$]=group[groupno+1..$];
                        }    
                        group.length=groupno+1;  
                      }
                      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.fn() && p != oldp);
                     if (newp!=-1)
                     {
                      p=newp;
                      group.length=groupno+1+savegroups.length;
                      if (savegroups.length>0)
                      {
                        group[groupno+1..$]=savegroups[0..$];
                      }  
                             
                      return true;
                     }
                    p = veryoldp;
                    group.length=groupno+1;
                    if (next.fn()) return true; // success but we want longer ones
                    return false;
                    }
                } else { // "+", or "{m,n}"
                 static if (!greedy) 
                    {
                    int numreps=0; // how many repeats have we found?
                    int oldp;
                    do {
                        oldp = p;
                        numreps++;
                        if (numreps>=repmin && atomAndNext.fn()) return true;
                        p = oldp;
                        static if (repmax<uint.max) {
                            // optimise for "+", "{n,}"
                            if (numreps == repmax) return false;
                        }
                     } while (atomonly.fn() && p!=oldp);
                    return false;
                    }
                  else  // greedy
                  {
                    int numreps=0; // how many repeats have we found?
                    int oldp;
                    int newp=-1;
                    grouprec [] savegroups;  
                    do {
                        oldp = p;
                        numreps++;
                        if (numreps>=repmin && atomAndNext.fn()) {newp=p;
                        savegroups.length=group.length-(groupno+1);
                        if (savegroups.length>0)
                        {
                        savegroups[0..$]=group[groupno+1..$];
                        }  
                        group.length=groupno+1;       
                        }
                        p = oldp;
                        static if (repmax<uint.max) {
                            // optimise for "+", "{n,}"
                            if (numreps == repmax) return false;
                        }
                     } while (atomonly.fn() && p!=oldp);
                     if (newp!=-1)
                     {
                      p=newp;
                      group.length=groupno+1+savegroups.length;
                      if (savegroups.length>0)
                      {
                        group[groupno+1..$]=savegroups[0..$];
                      } 
                      return true;
                     }
                    return false;
                  }
               }
            }
        }
    }
}

// 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.
template regAtom(char [] regstr)
{
    static if (regstr[0]=='[') {
        static if (regstr[1]=='^')
        {
            bool fn() { // inverse character class            
                return (p<searchstr.length && !charMatches!(regstr[2..$-1])(searchstr[p++]));
            }
        } else {
            bool fn() { // character class
                return (p<searchstr.length && charMatches!(regstr[1..$-1])(searchstr[p++]));
            }
        }            
    } else static if (regstr[0]=='.') { // match any
        bool fn() {
            if (p==searchstr.length) return false;
            p++;
            return true;
        }
    } else static if (regstr.length>1 && regstr[0..2]=="\\w") { // match a word letter
       bool fn() {   
                return (p<searchstr.length && charMatches!("[a-zA-Z0-9_]")(searchstr[p++]));
            }
          }
      else static if (regstr.length>1 && regstr[0..2]=="\\s") { // match whitespace
       bool fn() {    
                return (p<searchstr.length && charMatches!("[\t \n]")(searchstr[p++]));
            }
          }
        else static if (regstr.length>1 && regstr[0..2]=="\\d") { // match numbers
       bool fn() {    
                return (p<searchstr.length && charMatches!("[0-9]")(searchstr[p++]));
            }
    } else static if (regstr[0]=='@')  { // NONSTANDARD: referenced parameter
        mixin regParameter!(atoui!(regstr[1..$])-1);
    } else static if (regstr[0]=='^') { // start of line
        bool fn() {
            return (p==0 || searchstr[p-1]=='\n');
        } 
    } else static if (regstr[0]=='$') { // end of line
        bool fn() {
            return (p==searchstr.length || searchstr[p++]=='\n');
        }    
    } else static if (regstr.length>1 && regstr[0]=='\\') { // end of line
         bool fn() {
            if (p==searchstr.length || searchstr[p]!=regstr[1]) return false;
            p++;
            return true;
        }
      } else {
        // match single character
        bool fn() {
            if (p==searchstr.length || searchstr[p]!=regstr[0]) return false;
            p++;
            return true;
        }
    }
}

// match a variable string, which will be passed as a parameter.
template regParameter(int parmnum)
{
    bool fn() {
        if (p + param[parmnum].length > searchstr.length) return false;
        if (searchstr[p..p+param[parmnum].length] != param[parmnum]) return false;
        p+=param[parmnum].length;
        return true;
    }
}

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

// return true if char ch is matched by the character class regstr.
template charMatches(char [] regstr)
{
    bool charMatches(char ch) {
        static if (regstr.length==0) return false;
        else static if (regstr.length>=3 && regstr[1]=='-') {
            return (ch>=regstr[0] && ch<=regstr[2]) || charMatches!(regstr[3..$])(ch);
        } 
        else static if (regstr.length>=2 && regstr[0..2]=="\\w") {         
          return charMatches!("a-zA-Z0-9_")(ch) || charMatches!(regstr[2..$])(ch);           
          }
        else static if (regstr.length>=2 && regstr[0..2]=="\\d") {         
          return charMatches!("0-9")(ch) || charMatches!(regstr[2..$])(ch);           
          }
        else return (ch==regstr[0]) || charMatches!(regstr[1..$])(ch);
    }
}

//---------------------------------------------------------------------
// 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
        mixin parseRegexp!(fullpattern) engine;
        return engine.fn();
    }
}

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

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



template index(char [] fullpattern)
{
    int index(char [] searchstr,int startindex, char [][] param...) {
        int p; // next index to test
        int groupno=0;
        grouprec [] group;
        int rp;
        mixin parseRegexp!(fullpattern) engine;
        for (int x=startindex; x<searchstr.length; ++x) {
            p=x;
            rp=0;
            if (engine.fn()) 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;  //as for array slices, last char + 1
}

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

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



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





//---------------------------------------------------------------------
//                         EXAMPLE
//---------------------------------------------------------------------

import std.stdio;

void main()
{
writefln("BEGINNING UNIT TESTS\n");
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");

char [] qq;
writefln("=========");

qq = search!("((a*b*)|da)*b")("fasdaaab");
writefln("Result: ----",qq, "---");
writefln("=========");

}

//-------------------------------------------------------------------------------
/+

// 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);
}

+/

//-------------
// 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);
}