/*
Implementation of backtracking std.regex engine.
Contains both compile-time and run-time versions.
*/
module std.regex.internal.backtracking;
package(std.regex):
import core.stdc.stdlib, std.range.primitives, std.traits, std.typecons;
import std.regex.internal.ir;
import core.memory : pureMalloc, pureFree;
/+
BacktrackingMatcher implements backtracking scheme of matching
regular expressions.
+/
@trusted class BacktrackingMatcher(Char, Stream = Input!Char) : Matcher!Char
if (is(Char : dchar))
{
alias DataIndex = Stream.DataIndex;
struct State
{//top bit in pc is set if saved along with matches
DataIndex index;
uint pc, counter, infiniteNesting;
}
static assert(State.sizeof % size_t.sizeof == 0);
enum stateSize = State.sizeof / size_t.sizeof;
enum initialStack = 1 << 11; // items in a block of segmented stack
alias String = const(Char)[];
alias RegEx = Regex!Char;
alias MatchFn = bool function(BacktrackingMatcher) pure;
const RegEx re; // regex program
MatchFn nativeFn; // native code for that program
// Stream state
Stream s;
DataIndex index;
dchar front;
bool exhausted;
// Backtracking machine state
uint pc, counter;
DataIndex lastState = 0; // Top of state stack
uint infiniteNesting;
size_t[] memory;
Trace[] merge;
static struct Trace
{
ulong mask;
size_t offset;
bool mark(size_t idx)
{
immutable d = idx - offset;
if (d < 64) // including overflow
{
immutable p = mask & (1UL << d);
mask |= 1UL << d;
return p != 0;
}
else
{
offset = idx;
mask = 1;
return false;
}
}
}
//local slice of matches, global for backref
Group!DataIndex[] matches, backrefed;
size_t _refCount;
final:
override @property ref size_t refCount() { return _refCount; }
override @property ref const(RegEx) pattern(){ return re; }
static if (__traits(hasMember,Stream, "search"))
{
enum kicked = true;
}
else
enum kicked = false;
static size_t initialMemory(const ref RegEx re)
{
return stackSize(re)*size_t.sizeof + re.hotspotTableSize*Trace.sizeof;
}
static size_t stackSize(const ref RegEx re)
{
size_t itemSize = stateSize
+ re.ngroup * (Group!DataIndex).sizeof / size_t.sizeof;
return initialStack * itemSize + 2;
}
@property bool atStart(){ return index == 0; }
@property bool atEnd(){ return index == s.lastIndex && s.atEnd; }
void next()
{
if (!s.nextChar(front, index))
index = s.lastIndex;
}
void search()
{
static if (kicked)
{
if (!s.search(re.kickstart, front, index))
{
index = s.lastIndex;
}
}
else
next();
}
//
void newStack()
{
auto chunk = mallocArray!(size_t)(stackSize(re));
chunk[0] = cast(size_t)(memory.ptr);
chunk[1] = lastState;
memory = chunk[2..$];
lastState = 0;
}
bool prevStack()
{
// pointer to previous block
size_t* prev = cast(size_t*) memory.ptr[-2];
if (!prev)
{
// The last segment is freed in RegexMatch
return false;
}
else
{
import core.memory : pureFree;
// memory used in previous block
size_t size = memory.ptr[-1];
pureFree(memory.ptr-2);
memory = prev[0 .. size];
lastState = size;
return true;
}
}
void initExternalMemory(void[] memBlock)
{
merge = arrayInChunk!(Trace)(re.hotspotTableSize, memBlock);
merge[] = Trace.init;
memory = cast(size_t[]) memBlock;
memory[0] = 0; // hidden pointer
memory[1] = 0; // used size
memory = memory[2..$];
}
void initialize(ref const RegEx program, Stream stream, void[] memBlock)
{
s = stream;
exhausted = false;
initExternalMemory(memBlock);
backrefed = null;
}
override void dupTo(Matcher!Char m, void[] memBlock)
{
auto backtracking = cast(BacktrackingMatcher) m;
backtracking.s = s;
backtracking.front = front;
backtracking.index = index;
backtracking.exhausted = exhausted;
backtracking.initExternalMemory(memBlock);
}
override Matcher!Char rearm(in Char[] data)
{
merge[] = Trace.init;
exhausted = false;
s = Stream(data);
next();
return this;
}
this(ref const RegEx program, Stream stream, void[] memBlock, dchar ch, DataIndex idx)
{
_refCount = 1;
re = program;
nativeFn = null;
initialize(program, stream, memBlock);
front = ch;
index = idx;
}
this(ref const RegEx program, MatchFn func, Stream stream, void[] memBlock)
{
_refCount = 1;
re = program;
initialize(program, stream, memBlock);
nativeFn = func;
next();
}
this(ref const RegEx program, Stream stream, void[] memBlock)
{
_refCount = 1;
re = program;
nativeFn = null;
initialize(program, stream, memBlock);
next();
}
auto fwdMatcher(ref const RegEx re, void[] memBlock)
{
alias BackMatcher = BacktrackingMatcher!(Char, Stream);
auto fwdMatcher = new BackMatcher(re, s, memBlock, front, index);
return fwdMatcher;
}
auto bwdMatcher(ref const RegEx re, void[] memBlock)
{
alias BackMatcher = BacktrackingMatcher!(Char, typeof(s.loopBack(index)));
auto fwdMatcher =
new BackMatcher(re, s.loopBack(index), memBlock);
return fwdMatcher;
}
//
int matchFinalize()
{
immutable start = index;
immutable val = matchImpl();
if (val)
{//stream is updated here
matches[0].begin = start;
matches[0].end = index;
if (!(re.flags & RegexOption.global) || atEnd)
exhausted = true;
if (start == index)//empty match advances input
next();
return val;
}
else
return 0;
}
//lookup next match, fill matches with indices into input
override int match(Group!DataIndex[] matches)
{
debug(std_regex_matcher)
{
writeln("------------------------------------------");
}
if (exhausted) //all matches collected
return false;
this.matches = matches;
if (re.flags & RegexInfo.oneShot)
{
exhausted = true;
const DataIndex start = index;
immutable m = matchImpl();
if (m)
{
matches[0].begin = start;
matches[0].end = index;
}
return m;
}
static if (kicked)
{
if (!re.kickstart.empty)
{
for (;;)
{
immutable val = matchFinalize();
if (val)
return val;
else
{
if (atEnd)
break;
search();
if (atEnd)
{
exhausted = true;
return matchFinalize();
}
}
}
exhausted = true;
return 0; //early return
}
}
//no search available - skip a char at a time
for (;;)
{
immutable val = matchFinalize();
if (val)
return val;
else
{
if (atEnd)
break;
next();
if (atEnd)
{
exhausted = true;
return matchFinalize();
}
}
}
exhausted = true;
return 0;
}
/+
match subexpression against input,
results are stored in matches
+/
int matchImpl() pure
{
if (nativeFn)
{
debug(std_regex_ctr) writeln("using C-T matcher");
return nativeFn(this);
}
else
{
pc = 0;
counter = 0;
lastState = 0;
infiniteNesting = 0;
matches[] = Group!DataIndex.init;
auto start = s._index;
debug(std_regex_matcher)
writeln("Try match starting at ", s[index .. s.lastIndex]);
for (;;)
{
debug(std_regex_matcher)
writefln("PC: %s\tCNT: %s\t%s \tfront: %s src: %s",
pc, counter, disassemble(re.ir, pc, re.dict),
front, s._index);
switch (re.ir[pc].code)
{
case IR.OrChar://assumes IRL!(OrChar) == 1
if (atEnd)
goto L_backtrack;
uint len = re.ir[pc].sequence;
uint end = pc + len;
if (re.ir[pc].data != front && re.ir[pc+1].data != front)
{
for (pc = pc+2; pc < end; pc++)
if (re.ir[pc].data == front)
break;
if (pc == end)
goto L_backtrack;
}
pc = end;
next();
break;
case IR.Char:
if (atEnd || front != re.ir[pc].data)
goto L_backtrack;
pc += IRL!(IR.Char);
next();
break;
case IR.Any:
if (atEnd)
goto L_backtrack;
pc += IRL!(IR.Any);
next();
break;
case IR.CodepointSet:
if (atEnd || !re.charsets[re.ir[pc].data].scanFor(front))
goto L_backtrack;
next();
pc += IRL!(IR.CodepointSet);
break;
case IR.Trie:
if (atEnd || !re.matchers[re.ir[pc].data][front])
goto L_backtrack;
next();
pc += IRL!(IR.Trie);
break;
case IR.Wordboundary:
dchar back;
DataIndex bi;
//at start & end of input
if (atStart && wordMatcher[front])
{
pc += IRL!(IR.Wordboundary);
break;
}
else if (atEnd && s.loopBack(index).nextChar(back, bi)
&& wordMatcher[back])
{
pc += IRL!(IR.Wordboundary);
break;
}
else if (s.loopBack(index).nextChar(back, bi))
{
immutable af = wordMatcher[front];
immutable ab = wordMatcher[back];
if (af ^ ab)
{
pc += IRL!(IR.Wordboundary);
break;
}
}
goto L_backtrack;
case IR.Notwordboundary:
dchar back;
DataIndex bi;
//at start & end of input
if (atStart && wordMatcher[front])
goto L_backtrack;
else if (atEnd && s.loopBack(index).nextChar(back, bi)
&& wordMatcher[back])
goto L_backtrack;
else if (s.loopBack(index).nextChar(back, bi))
{
immutable af = wordMatcher[front];
immutable ab = wordMatcher[back];
if (af ^ ab)
goto L_backtrack;
}
pc += IRL!(IR.Wordboundary);
break;
case IR.Bof:
if (atStart)
pc += IRL!(IR.Bol);
else
goto L_backtrack;
break;
case IR.Bol:
dchar back;
DataIndex bi;
if (atStart)
pc += IRL!(IR.Bol);
else if (s.loopBack(index).nextChar(back,bi)
&& endOfLine(back, front == '\n'))
{
pc += IRL!(IR.Bol);
}
else
goto L_backtrack;
break;
case IR.Eof:
if (atEnd)
pc += IRL!(IR.Eol);
else
goto L_backtrack;
break;
case IR.Eol:
dchar back;
DataIndex bi;
debug(std_regex_matcher) writefln("EOL (front 0x%x) %s", front, s[index .. s.lastIndex]);
//no matching inside \r\n
if (atEnd || (endOfLine(front, s.loopBack(index).nextChar(back,bi)
&& back == '\r')))
{
pc += IRL!(IR.Eol);
}
else
goto L_backtrack;
break;
case IR.InfiniteStart, IR.InfiniteQStart:
pc += re.ir[pc].data + IRL!(IR.InfiniteStart);
//now pc is at end IR.Infinite(Q)End
uint len = re.ir[pc].data;
if (re.ir[pc].code == IR.InfiniteEnd)
{
pushState(pc+IRL!(IR.InfiniteEnd), counter);
pc -= len;
}
else
{
pushState(pc - len, counter);
pc += IRL!(IR.InfiniteEnd);
}
break;
case IR.InfiniteBloomStart:
pc += re.ir[pc].data + IRL!(IR.InfiniteBloomStart);
//now pc is at end IR.InfiniteBloomEnd
immutable len = re.ir[pc].data;
immutable filterIdx = re.ir[pc+2].raw;
if (re.filters[filterIdx][front])
pushState(pc+IRL!(IR.InfiniteBloomEnd), counter);
pc -= len;
break;
case IR.RepeatStart, IR.RepeatQStart:
pc += re.ir[pc].data + IRL!(IR.RepeatStart);
break;
case IR.RepeatEnd:
case IR.RepeatQEnd:
if (merge[re.ir[pc + 1].raw+counter].mark(index))
{
// merged!
goto L_backtrack;
}
//len, step, min, max
immutable len = re.ir[pc].data;
immutable step = re.ir[pc+2].raw;
immutable min = re.ir[pc+3].raw;
immutable max = re.ir[pc+4].raw;
if (counter < min)
{
counter += step;
pc -= len;
}
else if (counter < max)
{
if (re.ir[pc].code == IR.RepeatEnd)
{
pushState(pc + IRL!(IR.RepeatEnd), counter%step);
counter += step;
pc -= len;
}
else
{
pushState(pc - len, counter + step);
counter = counter%step;
pc += IRL!(IR.RepeatEnd);
}
}
else
{
counter = counter%step;
pc += IRL!(IR.RepeatEnd);
}
break;
case IR.InfiniteEnd:
case IR.InfiniteQEnd:
debug(std_regex_matcher) writeln("Infinited nesting:", infiniteNesting);
if (merge[re.ir[pc + 1].raw+counter].mark(index))
{
// merged!
goto L_backtrack;
}
immutable len = re.ir[pc].data;
if (re.ir[pc].code == IR.InfiniteEnd)
{
pushState(pc + IRL!(IR.InfiniteEnd), counter);
pc -= len;
}
else
{
pushState(pc-len, counter);
pc += IRL!(IR.InfiniteEnd);
}
break;
case IR.InfiniteBloomEnd:
debug(std_regex_matcher) writeln("Infinited nesting:", infiniteNesting);
if (merge[re.ir[pc + 1].raw+counter].mark(index))
{
// merged!
goto L_backtrack;
}
immutable len = re.ir[pc].data;
immutable filterIdx = re.ir[pc+2].raw;
if (re.filters[filterIdx][front])
{
infiniteNesting--;
pushState(pc + IRL!(IR.InfiniteBloomEnd), counter);
infiniteNesting++;
}
pc -= len;
break;
case IR.OrEnd:
if (merge[re.ir[pc + 1].raw+counter].mark(index))
{
// merged!
goto L_backtrack;
}
pc += IRL!(IR.OrEnd);
break;
case IR.OrStart:
pc += IRL!(IR.OrStart);
goto case;
case IR.Option:
immutable len = re.ir[pc].data;
if (re.ir[pc+len].code == IR.GotoEndOr)//not a last one
{
pushState(pc + len + IRL!(IR.Option), counter); //remember 2nd branch
}
pc += IRL!(IR.Option);
break;
case IR.GotoEndOr:
pc = pc + re.ir[pc].data + IRL!(IR.GotoEndOr);
break;
case IR.GroupStart:
immutable n = re.ir[pc].data;
matches[n].begin = index;
debug(std_regex_matcher) writefln("IR group #%u starts at %u", n, index);
pc += IRL!(IR.GroupStart);
break;
case IR.GroupEnd:
immutable n = re.ir[pc].data;
matches[n].end = index;
debug(std_regex_matcher) writefln("IR group #%u ends at %u", n, index);
pc += IRL!(IR.GroupEnd);
break;
case IR.LookaheadStart:
case IR.NeglookaheadStart:
immutable len = re.ir[pc].data;
auto save = index;
immutable ms = re.ir[pc+1].raw, me = re.ir[pc+2].raw;
auto mem = pureMalloc(initialMemory(re))[0 .. initialMemory(re)];
scope(exit) pureFree(mem.ptr);
auto slicedRe = re.withCode(re.ir[
pc+IRL!(IR.LookaheadStart) .. pc+IRL!(IR.LookaheadStart)+len+IRL!(IR.LookaheadEnd)
]);
static if (Stream.isLoopback)
{
auto matcher = bwdMatcher(slicedRe, mem);
}
else
{
auto matcher = fwdMatcher(slicedRe, mem);
}
matcher.matches = matches[ms .. me];
matcher.backrefed = backrefed.empty ? matches : backrefed;
immutable match = (matcher.matchImpl() != 0) ^ (re.ir[pc].code == IR.NeglookaheadStart);
s.reset(save);
next();
if (!match)
goto L_backtrack;
else
{
pc += IRL!(IR.LookaheadStart)+len+IRL!(IR.LookaheadEnd);
}
break;
case IR.LookbehindStart:
case IR.NeglookbehindStart:
immutable len = re.ir[pc].data;
immutable ms = re.ir[pc+1].raw, me = re.ir[pc+2].raw;
auto mem = pureMalloc(initialMemory(re))[0 .. initialMemory(re)];
scope(exit) pureFree(mem.ptr);
auto slicedRe = re.withCode(re.ir[
pc + IRL!(IR.LookbehindStart) .. pc + IRL!(IR.LookbehindStart) + len + IRL!(IR.LookbehindEnd)
]);
static if (Stream.isLoopback)
{
alias Matcher = BacktrackingMatcher!(Char, Stream);
auto matcher = new Matcher(slicedRe, s, mem, front, index);
}
else
{
alias Matcher = BacktrackingMatcher!(Char, typeof(s.loopBack(index)));
auto matcher = new Matcher(slicedRe, s.loopBack(index), mem);
}
matcher.matches = matches[ms .. me];
matcher.backrefed = backrefed.empty ? matches : backrefed;
immutable match = (matcher.matchImpl() != 0) ^ (re.ir[pc].code == IR.NeglookbehindStart);
if (!match)
goto L_backtrack;
else
{
pc += IRL!(IR.LookbehindStart)+len+IRL!(IR.LookbehindEnd);
}
break;
case IR.Backref:
immutable n = re.ir[pc].data;
auto referenced = re.ir[pc].localRef
? s[matches[n].begin .. matches[n].end]
: s[backrefed[n].begin .. backrefed[n].end];
while (!atEnd && !referenced.empty && front == referenced.front)
{
next();
referenced.popFront();
}
if (referenced.empty)
pc++;
else
goto L_backtrack;
break;
case IR.Nop:
pc += IRL!(IR.Nop);
break;
case IR.LookaheadEnd:
case IR.NeglookaheadEnd:
case IR.LookbehindEnd:
case IR.NeglookbehindEnd:
case IR.End:
// cleanup stale stack blocks if any
while (prevStack()) {}
return re.ir[pc].data;
default:
debug printBytecode(re.ir[0..$]);
assert(0);
L_backtrack:
if (!popState())
{
s.reset(start);
return 0;
}
}
}
}
assert(0);
}
@property size_t stackAvail()
{
return memory.length - lastState;
}
void stackPush(T)(T val)
if (!isDynamicArray!T)
{
*cast(T*)&memory[lastState] = val;
enum delta = (T.sizeof+size_t.sizeof/2)/size_t.sizeof;
lastState += delta;
debug(std_regex_matcher) writeln("push element SP= ", lastState);
}
void stackPush(T)(T[] val)
{
static assert(T.sizeof % size_t.sizeof == 0);
(cast(T*)&memory[lastState])[0 .. val.length]
= val[0..$];
lastState += val.length*(T.sizeof/size_t.sizeof);
debug(std_regex_matcher) writeln("push array SP= ", lastState);
}
void stackPop(T)(ref T val)
if (!isDynamicArray!T)
{
enum delta = (T.sizeof+size_t.sizeof/2)/size_t.sizeof;
lastState -= delta;
val = *cast(T*)&memory[lastState];
debug(std_regex_matcher) writeln("pop element SP= ", lastState);
}
void stackPop(T)(T[] val)
{
stackPop(val); // call ref version
}
void stackPop(T)(ref T[] val)
{
lastState -= val.length*(T.sizeof/size_t.sizeof);
val[0..$] = (cast(T*)&memory[lastState])[0 .. val.length];
debug(std_regex_matcher) writeln("pop array SP= ", lastState);
}
//helper function, saves engine state
void pushState(uint pc, uint counter)
{
if (stateSize + 2 * matches.length > stackAvail)
{
newStack();
}
*cast(State*)&memory[lastState] =
State(index, pc, counter, infiniteNesting);
lastState += stateSize;
memory[lastState .. lastState + 2 * matches.length] = (cast(size_t[]) matches)[];
lastState += 2*matches.length;
debug(std_regex_matcher)
writefln("Saved(pc=%s) front: %s src: %s",
pc, front, s[index .. s.lastIndex]);
}
//helper function, restores engine state
bool popState()
{
if (!lastState && !prevStack())
return false;
lastState -= 2*matches.length;
auto pm = cast(size_t[]) matches;
pm[] = memory[lastState .. lastState + 2 * matches.length];
lastState -= stateSize;
State* state = cast(State*)&memory[lastState];
index = state.index;
pc = state.pc;
counter = state.counter;
infiniteNesting = state.infiniteNesting;
debug(std_regex_matcher)
{
writefln("Restored matches", front, s[index .. s.lastIndex]);
foreach (i, m; matches)
writefln("Sub(%d) : %s..%s", i, m.begin, m.end);
}
s.reset(index);
next();
debug(std_regex_matcher)
writefln("Backtracked (pc=%s) front: %s src: %s",
pc, front, s[index .. s.lastIndex]);
return true;
}
}
//very shitty string formatter, $$ replaced with next argument converted to string
@trusted string ctSub( U...)(string format, U args)
{
import std.conv : to;
bool seenDollar;
foreach (i, ch; format)
{
if (ch == '$')
{
if (seenDollar)
{
static if (args.length > 0)
{
return format[0 .. i - 1] ~ to!string(args[0])
~ ctSub(format[i + 1 .. $], args[1 .. $]);
}
else
assert(0);
}
else
seenDollar = true;
}
else
seenDollar = false;
}
return format;
}
struct CtContext
{
import std.conv : to, text;
//dirty flags
bool counter;
//to mark the portion of matches to save
int match, total_matches;
int reserved;
const(CodepointInterval)[][] charsets;
//state of codegenerator
static struct CtState
{
string code;
int addr;
}
this(Char)(ref const Regex!Char re)
{
match = 1;
reserved = 1; //first match is skipped
total_matches = re.ngroup;
foreach (ref set; re.charsets)
{
charsets ~= set.intervals;
}
}
CtContext lookaround(uint s, uint e)
{
CtContext ct;
ct.total_matches = e - s;
ct.match = 1;
return ct;
}
//restore state having current context
string restoreCode()
{
string text;
//stack is checked in L_backtrack
text ~= counter
? "
stackPop(counter);"
: "
counter = 0;";
if (match < total_matches)
{
text ~= ctSub("
stackPop(matches[$$..$$]);", reserved, match);
text ~= ctSub("
matches[$$..$] = typeof(matches[0]).init;", match);
}
else
text ~= ctSub("
stackPop(matches[$$..$]);", reserved);
return text;
}
//save state having current context
string saveCode(uint pc, string count_expr="counter")
{
string text = ctSub("
if (stackAvail < $$*(Group!(DataIndex)).sizeof/size_t.sizeof + $$)
{
newStack();
}", match - reserved, cast(int) counter + 2);
if (match < total_matches)
text ~= ctSub("
stackPush(matches[$$..$$]);", reserved, match);
else
text ~= ctSub("
stackPush(matches[$$..$]);", reserved);
text ~= counter ? ctSub("
stackPush($$);", count_expr) : "";
text ~= ctSub("
stackPush(index); stackPush($$); \n", pc);
return text;
}
//
CtState ctGenBlock(const(Bytecode)[] ir, int addr)
{
CtState result;
result.addr = addr;
while (!ir.empty)
{
auto n = ctGenGroup(ir, result.addr);
result.code ~= n.code;
result.addr = n.addr;
}
return result;
}
//
CtState ctGenGroup(ref const(Bytecode)[] ir, int addr)
{
import std.algorithm.comparison : max;
auto bailOut = "goto L_backtrack;";
auto nextInstr = ctSub("goto case $$;", addr+1);
CtState r;
assert(!ir.empty);
switch (ir[0].code)
{
case IR.InfiniteStart, IR.InfiniteBloomStart,IR.InfiniteQStart, IR.RepeatStart, IR.RepeatQStart:
immutable infLoop =
ir[0].code == IR.InfiniteStart || ir[0].code == IR.InfiniteQStart ||
ir[0].code == IR.InfiniteBloomStart;
counter = counter ||
ir[0].code == IR.RepeatStart || ir[0].code == IR.RepeatQStart;
immutable len = ir[0].data;
auto nir = ir[ir[0].length .. ir[0].length+len];
r = ctGenBlock(nir, addr+1);
//start/end codegen
//r.addr is at last test+ jump of loop, addr+1 is body of loop
nir = ir[ir[0].length + len .. $];
r.code = ctGenFixupCode(ir[0 .. ir[0].length], addr, r.addr) ~ r.code;
r.code ~= ctGenFixupCode(nir, r.addr, addr+1);
r.addr += 2; //account end instruction + restore state
ir = nir;
break;
case IR.OrStart:
immutable len = ir[0].data;
auto nir = ir[ir[0].length .. ir[0].length+len];
r = ctGenAlternation(nir, addr);
ir = ir[ir[0].length + len .. $];
assert(ir[0].code == IR.OrEnd);
ir = ir[ir[0].length..$];
break;
case IR.LookaheadStart:
case IR.NeglookaheadStart:
case IR.LookbehindStart:
case IR.NeglookbehindStart:
immutable len = ir[0].data;
immutable behind = ir[0].code == IR.LookbehindStart || ir[0].code == IR.NeglookbehindStart;
immutable negative = ir[0].code == IR.NeglookaheadStart || ir[0].code == IR.NeglookbehindStart;
string fwdType = "typeof(fwdMatcher(re, []))";
string bwdType = "typeof(bwdMatcher(re, []))";
string fwdCreate = "fwdMatcher(re, mem)";
string bwdCreate = "bwdMatcher(re, mem)";
immutable start = IRL!(IR.LookbehindStart);
immutable end = IRL!(IR.LookbehindStart)+len+IRL!(IR.LookaheadEnd);
CtContext context = lookaround(ir[1].raw, ir[2].raw); //split off new context
auto slice = ir[start .. end];
r.code ~= ctSub(`
case $$: //fake lookaround "atom"
static if (typeof(matcher.s).isLoopback)
alias Lookaround = $$;
else
alias Lookaround = $$;
static bool matcher_$$(Lookaround matcher) @trusted
{
//(neg)lookaround piece start
$$
//(neg)lookaround piece ends
}
auto save = index;
auto mem = pureMalloc(initialMemory(re))[0 .. initialMemory(re)];
scope(exit) pureFree(mem.ptr);
static if (typeof(matcher.s).isLoopback)
auto lookaround = $$;
else
auto lookaround = $$;
lookaround.matches = matches[$$..$$];
lookaround.backrefed = backrefed.empty ? matches : backrefed;
lookaround.nativeFn = &matcher_$$; //hookup closure's binary code
int match = $$;
s.reset(save);
next();
if (match)
$$
else
$$`, addr,
behind ? fwdType : bwdType, behind ? bwdType : fwdType,
addr, context.ctGenRegEx(slice),
behind ? fwdCreate : bwdCreate, behind ? bwdCreate : fwdCreate,
ir[1].raw, ir[2].raw, //start - end of matches slice
addr,
negative ? "!lookaround.matchImpl()" : "lookaround.matchImpl()",
nextInstr, bailOut);
ir = ir[end .. $];
r.addr = addr + 1;
break;
case IR.LookaheadEnd: case IR.NeglookaheadEnd:
case IR.LookbehindEnd: case IR.NeglookbehindEnd:
ir = ir[IRL!(IR.LookaheadEnd) .. $];
r.addr = addr;
break;
default:
assert(ir[0].isAtom, text(ir[0].mnemonic));
r = ctGenAtom(ir, addr);
}
return r;
}
//generate source for bytecode contained in OrStart ... OrEnd
CtState ctGenAlternation(const(Bytecode)[] ir, int addr)
{
CtState[] pieces;
CtState r;
enum optL = IRL!(IR.Option);
for (;;)
{
assert(ir[0].code == IR.Option);
auto len = ir[0].data;
if (optL+len < ir.length && ir[optL+len].code == IR.Option)//not a last option
{
auto nir = ir[optL .. optL+len-IRL!(IR.GotoEndOr)];
r = ctGenBlock(nir, addr+2);//space for Option + restore state
//r.addr+1 to account GotoEndOr at end of branch
r.code = ctGenFixupCode(ir[0 .. ir[0].length], addr, r.addr+1) ~ r.code;
addr = r.addr+1;//leave space for GotoEndOr
pieces ~= r;
ir = ir[optL + len .. $];
}
else
{
pieces ~= ctGenBlock(ir[optL..$], addr);
addr = pieces[$-1].addr;
break;
}
}
r = pieces[0];
for (uint i = 1; i < pieces.length; i++)
{
r.code ~= ctSub(`
case $$:
goto case $$; `, pieces[i-1].addr, addr);
r.code ~= pieces[i].code;
}
r.addr = addr;
return r;
}
// generate fixup code for instruction in ir,
// fixup means it has an alternative way for control flow
string ctGenFixupCode(const(Bytecode)[] ir, int addr, int fixup)
{
return ctGenFixupCode(ir, addr, fixup); // call ref Bytecode[] version
}
string ctGenFixupCode(ref const(Bytecode)[] ir, int addr, int fixup)
{
string r;
string testCode;
r = ctSub(`
case $$: debug(std_regex_matcher) writeln("#$$");`,
addr, addr);
switch (ir[0].code)
{
case IR.InfiniteStart, IR.InfiniteQStart, IR.InfiniteBloomStart:
r ~= ctSub( `
goto case $$;`, fixup);
ir = ir[ir[0].length..$];
break;
case IR.InfiniteEnd:
testCode = ctQuickTest(ir[IRL!(IR.InfiniteEnd) .. $],addr + 1);
r ~= ctSub( `
if (merge[$$+counter].mark(index))
{
// merged!
goto L_backtrack;
}
$$
{
$$
}
goto case $$;
case $$: //restore state and go out of loop
$$
goto case;`, ir[1].raw, testCode, saveCode(addr+1), fixup,
addr+1, restoreCode());
ir = ir[ir[0].length..$];
break;
case IR.InfiniteBloomEnd:
//TODO: check bloom filter and skip on failure
testCode = ctQuickTest(ir[IRL!(IR.InfiniteBloomEnd) .. $],addr + 1);
r ~= ctSub( `
if (merge[$$+counter].mark(index))
{
// merged!
goto L_backtrack;
}
$$
{
$$
}
goto case $$;
case $$: //restore state and go out of loop
$$
goto case;`, ir[1].raw, testCode, saveCode(addr+1), fixup,
addr+1, restoreCode());
ir = ir[ir[0].length..$];
break;
case IR.InfiniteQEnd:
testCode = ctQuickTest(ir[IRL!(IR.InfiniteEnd) .. $],addr + 1);
auto altCode = testCode.length ? ctSub("else goto case $$;", fixup) : "";
r ~= ctSub( `
if (merge[$$+counter].mark(index))
{
// merged!
goto L_backtrack;
}
$$
{
$$
goto case $$;
}
$$
case $$://restore state and go inside loop
$$
goto case $$;`, ir[1].raw,
testCode, saveCode(addr+1), addr+2, altCode,
addr+1, restoreCode(), fixup);
ir = ir[ir[0].length..$];
break;
case IR.RepeatStart, IR.RepeatQStart:
r ~= ctSub( `
goto case $$;`, fixup);
ir = ir[ir[0].length..$];
break;
case IR.RepeatEnd, IR.RepeatQEnd:
//len, step, min, max
immutable len = ir[0].data;
immutable step = ir[2].raw;
immutable min = ir[3].raw;
immutable max = ir[4].raw;
r ~= ctSub(`
if (merge[$$+counter].mark(index))
{
// merged!
goto L_backtrack;
}
if (counter < $$)
{
debug(std_regex_matcher) writeln("RepeatEnd min case pc=", $$);
counter += $$;
goto case $$;
}`, ir[1].raw, min, addr, step, fixup);
if (ir[0].code == IR.RepeatEnd)
{
string counter_expr = ctSub("counter % $$", step);
r ~= ctSub(`
else if (counter < $$)
{
$$
counter += $$;
goto case $$;
}`, max, saveCode(addr+1, counter_expr), step, fixup);
}
else
{
string counter_expr = ctSub("counter % $$", step);
r ~= ctSub(`
else if (counter < $$)
{
$$
counter = counter % $$;
goto case $$;
}`, max, saveCode(addr+1,counter_expr), step, addr+2);
}
r ~= ctSub(`
else
{
counter = counter % $$;
goto case $$;
}
case $$: //restore state
$$
goto case $$;`, step, addr+2, addr+1, restoreCode(),
ir[0].code == IR.RepeatEnd ? addr+2 : fixup );
ir = ir[ir[0].length..$];
break;
case IR.Option:
r ~= ctSub( `
{
$$
}
goto case $$;
case $$://restore thunk to go to the next group
$$
goto case $$;`, saveCode(addr+1), addr+2,
addr+1, restoreCode(), fixup);
ir = ir[ir[0].length..$];
break;
default:
assert(0, text(ir[0].mnemonic));
}
return r;
}
string ctQuickTest(const(Bytecode)[] ir, int id)
{
uint pc = 0;
while (pc < ir.length && ir[pc].isAtom)
{
if (ir[pc].code == IR.GroupStart || ir[pc].code == IR.GroupEnd)
{
pc++;
}
else if (ir[pc].code == IR.Backref)
break;
else
{
auto code = ctAtomCode(ir[pc..$], -1);
return ctSub(`
int test_$$()
{
$$ //$$
}
if (test_$$() >= 0)`, id, code.ptr ? code : "return 0;",
ir[pc].mnemonic, id);
}
}
return "";
}
//process & generate source for simple bytecodes at front of ir using address addr
CtState ctGenAtom(ref const(Bytecode)[] ir, int addr)
{
CtState result;
result.code = ctAtomCode(ir, addr);
ir.popFrontN(ir[0].code == IR.OrChar ? ir[0].sequence : ir[0].length);
result.addr = addr + 1;
return result;
}
//D code for atom at ir using address addr, addr < 0 means quickTest
string ctAtomCode(const(Bytecode)[] ir, int addr)
{
string code;
string bailOut, nextInstr;
if (addr < 0)
{
bailOut = "return -1;";
nextInstr = "return 0;";
}
else
{
bailOut = "goto L_backtrack;";
nextInstr = ctSub("goto case $$;", addr+1);
code ~= ctSub( `
case $$: debug(std_regex_matcher) writeln("#$$");
`, addr, addr);
}
switch (ir[0].code)
{
case IR.OrChar://assumes IRL!(OrChar) == 1
code ~= ctSub(`
if (atEnd)
$$`, bailOut);
immutable len = ir[0].sequence;
for (uint i = 0; i < len; i++)
{
code ~= ctSub( `
if (front == $$)
{
$$
$$
}`, ir[i].data, addr >= 0 ? "next();" :"", nextInstr);
}
code ~= ctSub( `
$$`, bailOut);
break;
case IR.Char:
code ~= ctSub( `
if (atEnd || front != $$)
$$
$$
$$`, ir[0].data, bailOut, addr >= 0 ? "next();" :"", nextInstr);
break;
case IR.Any:
code ~= ctSub( `
if (atEnd || (!(re.flags & RegexOption.singleline)
&& (front == '\r' || front == '\n')))
$$
$$
$$`, bailOut, addr >= 0 ? "next();" :"",nextInstr);
break;
case IR.CodepointSet:
if (charsets.length)
{
string name = `func_`~to!string(addr+1);
string funcCode = CodepointSet.toSourceCode(charsets[ir[0].data], name);
code ~= ctSub( `
static $$
if (atEnd || !$$(front))
$$
$$
$$`, funcCode, name, bailOut, addr >= 0 ? "next();" :"", nextInstr);
}
else
code ~= ctSub( `
if (atEnd || !re.charsets[$$].scanFor(front))
$$
$$
$$`, ir[0].data, bailOut, addr >= 0 ? "next();" :"", nextInstr);
break;
case IR.Trie:
if (charsets.length && charsets[ir[0].data].length <= 8)
goto case IR.CodepointSet;
code ~= ctSub( `
if (atEnd || !re.matchers[$$][front])
$$
$$
$$`, ir[0].data, bailOut, addr >= 0 ? "next();" :"", nextInstr);
break;
case IR.Wordboundary:
code ~= ctSub( `
dchar back;
DataIndex bi;
if (atStart && wordMatcher[front])
{
$$
}
else if (atEnd && s.loopBack(index).nextChar(back, bi)
&& wordMatcher[back])
{
$$
}
else if (s.loopBack(index).nextChar(back, bi))
{
bool af = wordMatcher[front];
bool ab = wordMatcher[back];
if (af ^ ab)
{
$$
}
}
$$`, nextInstr, nextInstr, nextInstr, bailOut);
break;
case IR.Notwordboundary:
code ~= ctSub( `
dchar back;
DataIndex bi;
//at start & end of input
if (atStart && wordMatcher[front])
$$
else if (atEnd && s.loopBack(index).nextChar(back, bi)
&& wordMatcher[back])
$$
else if (s.loopBack(index).nextChar(back, bi))
{
bool af = wordMatcher[front];
bool ab = wordMatcher[back];
if (af ^ ab)
$$
}
$$`, bailOut, bailOut, bailOut, nextInstr);
break;
case IR.Bol:
code ~= ctSub(`
dchar back;
DataIndex bi;
if (atStart || (s.loopBack(index).nextChar(back,bi)
&& endOfLine(back, front == '\n')))
{
debug(std_regex_matcher) writeln("BOL matched");
$$
}
else
$$`, nextInstr, bailOut);
break;
case IR.Bof:
code ~= ctSub(`
if (atStart)
{
debug(std_regex_matcher) writeln("BOF matched");
$$
}
else
$$`, nextInstr, bailOut);
break;
case IR.Eol:
code ~= ctSub(`
dchar back;
DataIndex bi;
debug(std_regex_matcher) writefln("EOL (front 0x%x) %s", front, s[index .. s.lastIndex]);
//no matching inside \r\n
if (atEnd || (endOfLine(front, s.loopBack(index).nextChar(back,bi)
&& back == '\r')))
{
debug(std_regex_matcher) writeln("EOL matched");
$$
}
else
$$`, nextInstr, bailOut);
break;
case IR.Eof:
code ~= ctSub(`
if (atEnd)
{
debug(std_regex_matcher) writeln("BOF matched");
$$
}
else
$$`, nextInstr, bailOut);
break;
case IR.GroupStart:
code ~= ctSub(`
matches[$$].begin = index;
$$`, ir[0].data, nextInstr);
match = ir[0].data+1;
break;
case IR.GroupEnd:
code ~= ctSub(`
matches[$$].end = index;
$$`, ir[0].data, nextInstr);
break;
case IR.Backref:
string mStr = "auto referenced = ";
mStr ~= ir[0].localRef
? ctSub("s[matches[$$].begin .. matches[$$].end];",
ir[0].data, ir[0].data)
: ctSub("s[backrefed[$$].begin .. backrefed[$$].end];",
ir[0].data, ir[0].data);
code ~= ctSub( `
$$
while (!atEnd && !referenced.empty && front == referenced.front)
{
next();
referenced.popFront();
}
if (referenced.empty)
$$
else
$$`, mStr, nextInstr, bailOut);
break;
case IR.Nop:
case IR.End:
break;
default:
assert(0, text(ir[0].mnemonic, " is not supported yet"));
}
return code;
}
//generate D code for the whole regex
public string ctGenRegEx(const(Bytecode)[] ir)
{
auto bdy = ctGenBlock(ir, 0);
auto r = `
import core.memory : pureMalloc, pureFree;
with(matcher)
{
pc = 0;
counter = 0;
lastState = 0;
matches[] = Group!DataIndex.init;
auto start = s._index;`;
r ~= `
goto StartLoop;
debug(std_regex_matcher) writeln("Try CT matching starting at ",s[index .. s.lastIndex]);
L_backtrack:
if (lastState || prevStack())
{
stackPop(pc);
stackPop(index);
s.reset(index);
next();
}
else
{
s.reset(start);
return false;
}
StartLoop:
switch (pc)
{
`;
r ~= bdy.code;
r ~= ctSub(`
case $$: break;`,bdy.addr);
r ~= `
default:
assert(0);
}
// cleanup stale stack blocks
while (prevStack()) {}
return true;
}
`;
return r;
}
}
string ctGenRegExCode(Char)(const Regex!Char re)
{
auto context = CtContext(re);
return context.ctGenRegEx(re.ir);
}