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