/*
Kickstart is a coarse-grained "filter" engine that finds likely matches
to be verified by full-blown matcher.
*/
module std.regex.internal.kickstart;
package(std.regex):
import std.range.primitives, std.utf;
import std.regex.internal.ir;
//utility for shiftOr, returns a minimum number of bytes to test in a Char
uint effectiveSize(Char)()
{
static if (is(Char == char))
return 1;
else static if (is(Char == wchar))
return 2;
else static if (is(Char == dchar))
return 3;
else
static assert(0);
}
/*
Kickstart engine using ShiftOr algorithm,
a bit parallel technique for inexact string searching.
*/
struct ShiftOr(Char)
{
private:
uint[] table;
uint fChar;
uint n_length;
enum charSize = effectiveSize!Char();
//maximum number of chars in CodepointSet to process
enum uint charsetThreshold = 32_000;
static struct ShiftThread
{
uint[] tab;
uint mask;
uint idx;
uint pc, counter, hops;
this(uint newPc, uint newCounter, uint[] table)
{
pc = newPc;
counter = newCounter;
mask = 1;
idx = 0;
hops = 0;
tab = table;
}
void setMask(uint idx, uint mask)
{
tab[idx] |= mask;
}
void setInvMask(uint idx, uint mask)
{
tab[idx] &= ~mask;
}
void set(alias setBits = setInvMask)(dchar ch)
{
static if (charSize == 3)
{
uint val = ch, tmask = mask;
setBits(val&0xFF, tmask);
tmask <<= 1;
val >>= 8;
setBits(val&0xFF, tmask);
tmask <<= 1;
val >>= 8;
assert(val <= 0x10);
setBits(val, tmask);
tmask <<= 1;
}
else
{
Char[dchar.sizeof/Char.sizeof] buf;
uint tmask = mask;
size_t total = encode(buf, ch);
for (size_t i = 0; i < total; i++, tmask<<=1)
{
static if (charSize == 1)
setBits(buf[i], tmask);
else static if (charSize == 2)
{
setBits(buf[i]&0xFF, tmask);
tmask <<= 1;
setBits(buf[i]>>8, tmask);
}
}
}
}
void add(dchar ch){ return set!setInvMask(ch); }
void advance(uint s)
{
mask <<= s;
idx += s;
}
@property bool full(){ return !mask; }
}
static ShiftThread fork(ShiftThread t, uint newPc, uint newCounter)
{
ShiftThread nt = t;
nt.pc = newPc;
nt.counter = newCounter;
return nt;
}
@trusted static ShiftThread fetch(ref ShiftThread[] worklist)
{
auto t = worklist[$-1];
worklist.length -= 1;
if (!__ctfe)
cast(void) worklist.assumeSafeAppend();
return t;
}
static uint charLen(uint ch)
{
assert(ch <= 0x10FFFF);
return codeLength!Char(cast(dchar) ch)*charSize;
}
public:
@trusted this(ref Regex!Char re, uint[] memory)
{
static import std.algorithm.comparison;
import std.algorithm.searching : countUntil;
import std.conv : text;
import std.range : assumeSorted;
assert(memory.length == 256);
fChar = uint.max;
// FNV-1a flavored hash (uses 32bits at a time)
ulong hash(uint[] tab)
{
ulong h = 0xcbf29ce484222325;
foreach (v; tab)
{
h ^= v;
h *= 0x100000001b3;
}
return h;
}
L_FindChar:
for (size_t i = 0;;)
{
switch (re.ir[i].code)
{
case IR.Char:
fChar = re.ir[i].data;
static if (charSize != 3)
{
Char[dchar.sizeof/Char.sizeof] buf;
encode(buf, fChar);
fChar = buf[0];
}
fChar = fChar & 0xFF;
break L_FindChar;
case IR.GroupStart, IR.GroupEnd:
i += IRL!(IR.GroupStart);
break;
case IR.Bof, IR.Bol, IR.Wordboundary, IR.Notwordboundary:
i += IRL!(IR.Bol);
break;
default:
break L_FindChar;
}
}
table = memory;
table[] = uint.max;
alias MergeTab = bool[ulong];
// use reasonably complex hash to identify equivalent tables
auto merge = new MergeTab[re.hotspotTableSize];
ShiftThread[] trs;
ShiftThread t = ShiftThread(0, 0, table);
//locate first fixed char if any
n_length = 32;
for (;;)
{
L_Eval_Thread:
for (;;)
{
switch (re.ir[t.pc].code)
{
case IR.Char:
uint s = charLen(re.ir[t.pc].data);
if (t.idx+s > n_length)
goto L_StopThread;
t.add(re.ir[t.pc].data);
t.advance(s);
t.pc += IRL!(IR.Char);
break;
case IR.OrChar://assumes IRL!(OrChar) == 1
uint len = re.ir[t.pc].sequence;
uint end = t.pc + len;
uint[Bytecode.maxSequence] s;
uint numS;
for (uint i = 0; i < len; i++)
{
auto x = charLen(re.ir[t.pc+i].data);
if (countUntil(s[0 .. numS], x) < 0)
s[numS++] = x;
}
for (uint i = t.pc; i < end; i++)
{
t.add(re.ir[i].data);
}
for (uint i = 0; i < numS; i++)
{
auto tx = fork(t, t.pc + len, t.counter);
if (tx.idx + s[i] <= n_length)
{
tx.advance(s[i]);
trs ~= tx;
}
}
if (!trs.empty)
t = fetch(trs);
else
goto L_StopThread;
break;
case IR.CodepointSet:
case IR.Trie:
auto set = re.charsets[re.ir[t.pc].data];
uint[4] s;
uint numS;
static if (charSize == 3)
{
s[0] = charSize;
numS = 1;
}
else
{
static if (charSize == 1)
static immutable codeBounds = [0x0, 0x7F, 0x80, 0x7FF, 0x800, 0xFFFF, 0x10000, 0x10FFFF];
else //== 2
static immutable codeBounds = [0x0, 0xFFFF, 0x10000, 0x10FFFF];
uint[] arr = new uint[set.byInterval.length * 2];
size_t ofs = 0;
foreach (ival; set.byInterval)
{
arr[ofs++] = ival.a;
arr[ofs++] = ival.b;
}
auto srange = assumeSorted!"a <= b"(arr);
for (uint i = 0; i < codeBounds.length/2; i++)
{
auto start = srange.lowerBound(codeBounds[2*i]).length;
auto end = srange.lowerBound(codeBounds[2*i+1]).length;
if (end > start || (end == start && (end & 1)))
s[numS++] = (i+1)*charSize;
}
}
if (numS == 0 || t.idx + s[numS-1] > n_length)
goto L_StopThread;
auto chars = set.length;
if (chars > charsetThreshold)
goto L_StopThread;
foreach (ch; set.byCodepoint)
{
//avoid surrogate pairs
if (0xD800 <= ch && ch <= 0xDFFF)
continue;
t.add(ch);
}
for (uint i = 0; i < numS; i++)
{
auto tx = fork(t, t.pc + IRL!(IR.CodepointSet), t.counter);
tx.advance(s[i]);
trs ~= tx;
}
if (!trs.empty)
t = fetch(trs);
else
goto L_StopThread;
break;
case IR.Any:
goto L_StopThread;
case IR.GotoEndOr:
t.pc += IRL!(IR.GotoEndOr)+re.ir[t.pc].data;
assert(re.ir[t.pc].code == IR.OrEnd);
goto case;
case IR.OrEnd:
auto slot = re.ir[t.pc+1].raw+t.counter;
auto val = hash(t.tab);
if (val in merge[slot])
goto L_StopThread; // merge equivalent
merge[slot][val] = true;
t.pc += IRL!(IR.OrEnd);
break;
case IR.OrStart:
t.pc += IRL!(IR.OrStart);
goto case;
case IR.Option:
uint next = t.pc + re.ir[t.pc].data + IRL!(IR.Option);
//queue next Option
if (re.ir[next].code == IR.Option)
{
trs ~= fork(t, next, t.counter);
}
t.pc += IRL!(IR.Option);
break;
case IR.RepeatStart:case IR.RepeatQStart:
t.pc += IRL!(IR.RepeatStart)+re.ir[t.pc].data;
goto case IR.RepeatEnd;
case IR.RepeatEnd:
case IR.RepeatQEnd:
auto slot = re.ir[t.pc+1].raw+t.counter;
auto val = hash(t.tab);
if (val in merge[slot])
goto L_StopThread; // merge equivalent
merge[slot][val] = true;
uint len = re.ir[t.pc].data;
uint step = re.ir[t.pc+2].raw;
uint min = re.ir[t.pc+3].raw;
if (t.counter < min)
{
t.counter += step;
t.pc -= len;
break;
}
uint max = re.ir[t.pc+4].raw;
if (t.counter < max)
{
trs ~= fork(t, t.pc - len, t.counter + step);
t.counter = t.counter%step;
t.pc += IRL!(IR.RepeatEnd);
}
else
{
t.counter = t.counter%step;
t.pc += IRL!(IR.RepeatEnd);
}
break;
case IR.InfiniteStart, IR.InfiniteQStart:
t.pc += re.ir[t.pc].data + IRL!(IR.InfiniteStart);
goto case IR.InfiniteEnd; //both Q and non-Q
case IR.InfiniteEnd:
case IR.InfiniteQEnd:
auto slot = re.ir[t.pc+1].raw+t.counter;
auto val = hash(t.tab);
if (val in merge[slot])
goto L_StopThread; // merge equivalent
merge[slot][val] = true;
uint len = re.ir[t.pc].data;
uint pc1, pc2; //branches to take in priority order
if (++t.hops == 32)
goto L_StopThread;
pc1 = t.pc + IRL!(IR.InfiniteEnd);
pc2 = t.pc - len;
trs ~= fork(t, pc2, t.counter);
t.pc = pc1;
break;
case IR.GroupStart, IR.GroupEnd:
t.pc += IRL!(IR.GroupStart);
break;
case IR.Bof, IR.Bol, IR.Wordboundary, IR.Notwordboundary:
t.pc += IRL!(IR.Bol);
break;
case IR.LookaheadStart, IR.NeglookaheadStart, IR.LookbehindStart, IR.NeglookbehindStart:
t.pc += IRL!(IR.LookaheadStart) + IRL!(IR.LookaheadEnd) + re.ir[t.pc].data;
break;
default:
L_StopThread:
assert(re.ir[t.pc].code >= 0x80, text(re.ir[t.pc].code));
debug (fred_search) writeln("ShiftOr stumbled on ",re.ir[t.pc].mnemonic);
n_length = std.algorithm.comparison.min(t.idx, n_length);
break L_Eval_Thread;
}
}
if (trs.empty)
break;
t = fetch(trs);
}
debug(std_regex_search)
{
writeln("Min length: ", n_length);
}
}
@property bool empty() const { return n_length == 0; }
@property uint length() const{ return n_length/charSize; }
// lookup compatible bit pattern in haystack, return starting index
// has a useful trait: if supplied with valid UTF indexes,
// returns only valid UTF indexes
// (that given the haystack in question is valid UTF string)
@trusted size_t search(const(Char)[] haystack, size_t idx) const
{//@BUG: apparently assumes little endian machines
import core.stdc.string : memchr;
import std.conv : text;
assert(!empty);
auto p = cast(const(ubyte)*)(haystack.ptr+idx);
uint state = uint.max;
uint limit = 1u<<(n_length - 1u);
debug(std_regex_search) writefln("Limit: %32b",limit);
if (fChar != uint.max)
{
const(ubyte)* end = cast(ubyte*)(haystack.ptr + haystack.length);
const orginalAlign = cast(size_t) p & (Char.sizeof-1);
while (p != end)
{
if (!~state)
{//speed up seeking first matching place
for (;;)
{
assert(p <= end, text(p," vs ", end));
p = cast(ubyte*) memchr(p, fChar, end - p);
if (!p)
return haystack.length;
if ((cast(size_t) p & (Char.sizeof-1)) == orginalAlign)
break;
if (++p == end)
return haystack.length;
}
state = ~1u;
assert((cast(size_t) p & (Char.sizeof-1)) == orginalAlign);
static if (charSize == 3)
{
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
}
else
p++;
//first char is tested, see if that's all
if (!(state & limit))
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
else
{//have some bits/states for possible matches,
//use the usual shift-or cycle
static if (charSize == 3)
{
state = (state << 1) | table[p[0]];
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
}
else
{
state = (state << 1) | table[p[0]];
p++;
}
if (!(state & limit))
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
debug(std_regex_search) writefln("State: %32b", state);
}
}
else
{
//normal path, partially unrolled for char/wchar
static if (charSize == 3)
{
const(ubyte)* end = cast(ubyte*)(haystack.ptr + haystack.length);
while (p != end)
{
state = (state << 1) | table[p[0]];
state = (state << 1) | table[p[1]];
state = (state << 1) | table[p[2]];
p += 4;
if (!(state & limit))//division rounds down for dchar
return (p-cast(ubyte*) haystack.ptr)/Char.sizeof
-length;
}
}
else
{
auto len = cast(ubyte*)(haystack.ptr + haystack.length) - p;
size_t i = 0;
if (len & 1)
{
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof-length;
}
while (i < len)
{
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof
-length;
state = (state << 1) | table[p[i++]];
if (!(state & limit))
return idx+i/Char.sizeof
-length;
debug(std_regex_search) writefln("State: %32b", state);
}
}
}
return haystack.length;
}
@system debug static void dump(uint[] table)
{//@@@BUG@@@ writef(ln) is @system
import std.stdio : writefln;
for (size_t i = 0; i < table.length; i += 4)
{
writefln("%32b %32b %32b %32b",table[i], table[i+1], table[i+2], table[i+3]);
}
}
}
@system unittest
{
import std.conv, std.regex;
@trusted void test_fixed(alias Kick)()
{
static foreach (i, v; AliasSeq!(char, wchar, dchar))
{{
alias Char = v;
alias String = immutable(v)[];
auto r = regex(to!String(`abc$`));
auto kick = Kick!Char(r, new uint[256]);
assert(kick.length == 3, text(Kick.stringof," ",v.stringof, " == ", kick.length));
auto r2 = regex(to!String(`(abc){2}a+`));
kick = Kick!Char(r2, new uint[256]);
assert(kick.length == 7, text(Kick.stringof,v.stringof," == ", kick.length));
auto r3 = regex(to!String(`\b(a{2}b{3}){2,4}`));
kick = Kick!Char(r3, new uint[256]);
assert(kick.length == 10, text(Kick.stringof,v.stringof," == ", kick.length));
auto r4 = regex(to!String(`\ba{2}c\bxyz`));
kick = Kick!Char(r4, new uint[256]);
assert(kick.length == 6, text(Kick.stringof,v.stringof, " == ", kick.length));
auto r5 = regex(to!String(`\ba{2}c\b`));
kick = Kick!Char(r5, new uint[256]);
size_t x = kick.search("aabaacaa", 0);
assert(x == 3, text(Kick.stringof,v.stringof," == ", kick.length));
x = kick.search("aabaacaa", x+1);
assert(x == 8, text(Kick.stringof,v.stringof," == ", kick.length));
}}
}
@trusted void test_flex(alias Kick)()
{
static foreach (i, v; AliasSeq!(char, wchar, dchar))
{{
alias Char = v;
alias String = immutable(v)[];
auto r = regex(to!String(`abc[a-z]`));
auto kick = Kick!Char(r, new uint[256]);
auto x = kick.search(to!String("abbabca"), 0);
assert(x == 3, text("real x is ", x, " ",v.stringof));
auto r2 = regex(to!String(`(ax|bd|cdy)`));
String s2 = to!String("abdcdyabax");
kick = Kick!Char(r2, new uint[256]);
x = kick.search(s2, 0);
assert(x == 1, text("real x is ", x));
x = kick.search(s2, x+1);
assert(x == 3, text("real x is ", x));
x = kick.search(s2, x+1);
assert(x == 8, text("real x is ", x));
auto rdot = regex(to!String(`...`));
kick = Kick!Char(rdot, new uint[256]);
assert(kick.length == 0);
auto rN = regex(to!String(`a(b+|c+)x`));
kick = Kick!Char(rN, new uint[256]);
assert(kick.length == 3, to!string(kick.length));
assert(kick.search("ababx",0) == 2);
assert(kick.search("abaacba",0) == 3);//expected inexact
}}
}
test_fixed!(ShiftOr)();
test_flex!(ShiftOr)();
}
alias Kickstart = ShiftOr;