// 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 unescapedunescapedFindFirst = 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!(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(char [] regstr, alias next)
{
static if (findUnion!(regstr)==-1) {
// No unions to worry about
mixin regNoUnions!(regstr, next);
} else {
bool fn() {
// Both halves of the union have the same next, inherited from the parent
mixin regSequence!(regstr[0..findUnion!(regstr)], next) a;
mixin regSequence!(regstr[findUnion!(regstr)+1..$], next) b;
int oldp = p;
if (a.fn()) return true;
p = oldp;
return b.fn();
}
}
}
// regstr is a sequence of terms, all of which must be matched
// Does not contain any unions
template regNoUnions(char [] regstr, alias next)
{
static if (regstr.length == termConsumed!(regstr)) {
// there's only a single item (possibly including a quantifier)
mixin regTerm!(regstr, next);
} else {
bool fn() {
mixin regSequence!(regstr[termConsumed!(regstr)..$], next) second;
mixin regTerm!(regstr[0..termConsumed!(regstr)], second) first;
return first.fn();
}
}
}
// the term without a quantifier. Here we deal with embedded subsequences.
template regSingleTerm(char [] regstr, alias next)
{
static if (regstr.length>2 && regstr[0..3]=="(?:") {
// A sequence always calls next.
mixin regSequence!(regstr[3..$-1], next);
}
else static if (regstr[0]=='(') {
// A sequence always calls next.
mixin regSequence!(regstr[1..$-1], next) a;
bool fn() {
groupno+=1;
return a.fn();
}
} 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(char [] regstr)
{
bool fn() {
mixin regSequence!(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(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!(regstr[3..t-1]) suddendeath;
mixin regSequence!(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!(regstr[1..t-1]) suddendeath;
mixin regSequence!(regstr[1..t-1], suddendeath) a;
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(char [] regstr, alias next)
{
static if (atomConsumed!(regstr)==regstr.length) {
// there is no quantifier, just use the naked term
mixin regSingleTerm!(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!(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 (next.fn())
{
int newp=p;
p = oldp;
if (atomAndNext.fn())
{
return true;
}
p = newp;
return true;
}
p = oldp;
return atomAndNext.fn();
}
} 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!(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=p;
int newp=-1;
if (next.fn()) newp=p; // success but we want longer ones
p=oldp;
do {
// Can we do (atom).(next) ?
oldp = p;
if (atomAndNext.fn()) { 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.fn() && p != oldp);
if (newp!=-1)
{
p=newp;
return true;
}
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
{
int numreps=0; // how many repeats have we found?
int oldp;
int newp=-1;
do {
oldp = p;
numreps++;
if (numreps>=repmin && atomAndNext.fn()) newp=p;
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;
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 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
mixin parseRegexp!(fullpattern) engine;
for (int x=0; x<searchstr.length; ++x) {
p=x;
if (engine.fn()) return searchstr[x..p];
}
return null; // no match
}
}
template searchgroups(char [] fullpattern)
{
char [] search(char [] searchstr, char [][] param...) {
int p; // next index to test
int groupno=0;
mixin parseRegexp!(fullpattern) engine;
for (int x=0; x<searchstr.length; ++x) {
p=x;
if (engine.fn()) return searchstr[x..p];
}
return null; // no match
}
}
template index(char [] fullpattern)
{
int index(char [] searchstr,int startindex, char [][] param...) {
int p; // next index to test
int groupno=0;
mixin parseRegexp!(fullpattern) engine;
for (int x=startindex; x<searchstr.length; ++x) {
p=x;
if (engine.fn()) return x;
}
return -1; // no match
}
}
struct indexrec
{
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;
mixin parseRegexp!(fullpattern) engine;
for (int x=startindex; x<searchstr.length; ++x) {
p=x;
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;
mixin parseRegexp!(fullpattern) engine;
indexrec[] solutions;
int soli=0;
for (int x=startindex; x<searchstr.length; ++x) {
p=x;
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;
mixin parseRegexp!(fullpattern) engine;
indexrec[] solutions;
int soli=0;
for (int x=0; x<searchstr.length; ++x) {
p=x;
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);
}