/*******************************************************************************

    copyright:      Copyright (c) 2007-2008 Jascha Wetzel. All rights reserved.

    license:        BSD style: $(LICENSE)

    version:        Initial release: Jan 2008

    authors:        Jascha Wetzel

    This is a regular expression compiler and interpreter based on the Tagged NFA/DFA method.

    The Regex class is not thread safe.

    See <a href="http://en.wikipedia.org/wiki/Regular_expression">Wikpedia's article on regular expressions</a>
    for details on regular expressions in general.

    The used method implies, that the expressions are <i>regular</i>, in the way language theory defines it,
    as opposed to what &quot;regular expression&quot; means in most implementations
    (e.g. PCRE or those from the standard libraries of Perl, Java or Python).
    The advantage of this method is it's performance, it's disadvantage is the inability to realize some features
    that Perl-like regular expressions have (e.g. back-references).
    See <a href="http://swtch.com/~rsc/regexp/regexp1.html">&quot;Regular Expression Matching Can Be Simple And Fast&quot;</a>
    for details on the differences.

    The time for matching a regular expression against an input string of length N is in O(M*N), where M depends on the
    number of matching brackets and the complexity of the expression. That is, M is constant wrt. the input
    and therefore matching is a linear-time process.

    The syntax of a regular expressions is as follows.
    <i>X</i> and <i>Y</i> stand for an arbitrary regular expression.

    <table border=1 cellspacing=0 cellpadding=5>
    <caption>Operators</caption>
    $(TR $(TD X|Y) $(TD alternation, i.e. X or Y) )
    $(TR $(TD (X)) $(TD matching brackets - creates a sub-match) )
    $(TR $(TD (?X)) $(TD non-matching brackets - only groups X, no sub-match is created) )
    $(TR $(TD [Z]) $(TD character class specification, Z is a string of characters or character ranges, e.g. [a-zA-Z0-9_.\-]) )
    $(TR $(TD [^Z]) $(TD negated character class specification) )
    $(TR $(TD &lt;X) $(TD lookbehind, X may be a single character or a character class) )
    $(TR $(TD &gt;X) $(TD lookahead, X may be a single character or a character class) )
    $(TR $(TD ^) $(TD start of input or start of line) )
    $(TR $(TD $) $(TD end of input or end of line) )
    $(TR $(TD \b) $(TD start or end of word, equals (?&lt;\s&gt;\S|&lt;\S&gt;\s)) )
    $(TR $(TD \B) $(TD opposite of \b, equals (?&lt;\S&gt;\S|&lt;\s&gt;\s)) )
    </table>

    <table border=1 cellspacing=0 cellpadding=5>
    <caption>Quantifiers</caption>
    $(TR $(TD X?) $(TD zero or one) )
    $(TR $(TD X*) $(TD zero or more) )
    $(TR $(TD X+) $(TD one or more) )
    $(TR $(TD X{n,m}) $(TD at least n, at most m instances of X.<br>If n is missing, it's set to 0.<br>If m is missing, it is set to infinity.) )
    $(TR $(TD X??) $(TD non-greedy version of the above operators) )
    $(TR $(TD X*?) $(TD see above) )
    $(TR $(TD X+?) $(TD see above) )
    $(TR $(TD X{n,m}?) $(TD see above) )
    </table>

    <table border=1 cellspacing=0 cellpadding=5>
    <caption>Pre-defined character classes</caption>
    $(TR $(TD .) $(TD any printable character) )
    $(TR $(TD \s) $(TD whitespace) )
    $(TR $(TD \S) $(TD non-whitespace) )
    $(TR $(TD \w) $(TD alpha-numeric characters or underscore) )
    $(TR $(TD \W) $(TD opposite of \w) )
    $(TR $(TD \d) $(TD digits) )
    $(TR $(TD \D) $(TD non-digit) )
    </table>

    Note that "alphanumeric" only applies to Latin-1.
*******************************************************************************/
module tango.text.Regex;

debug(TangoRegex) import tango.io.Stdout;

/* *****************************************************************************
    A simple pair
*******************************************************************************/
private struct Pair(T)
{
    static Pair opCall(T a, T b)
    {
        Pair p;
        p.a = a;
        p.b = b;
        return p;
    }

    union
    {
        struct {
            T first, second;
        }
        struct {
            T a, b;
        }
    }
}

/* *****************************************************************************
    Double linked list
*******************************************************************************/
private class List(T)
{
    class Element
    {
        T value;
        Element prev,
                next;

        this(T v)
        {
            value = v;
        }
    }

    size_t  len;
    Element head,
            tail;

    List opCatAssign(T v)
    {
        if ( tail is null )
            head = tail = new Element(v);
        else {
            tail.next = new Element(v);
            tail.next.prev = tail;
            tail = tail.next;
        }
        ++len;
        return this;
    }

    List insertAfter(T w, T v)
    {
        foreach ( e; &this.elements )
        {
            if ( e.value is w )
                return insertAfter(e, v);
        }
        return null;
    }

    List insertAfter(Element e, T v)
    {
        auto tmp = new Element(v);
        tmp.prev = e;
        tmp.next = e.next;
        e.next.prev = tmp;
        e.next = tmp;
        if ( e is tail )
            tail = tmp;
        ++len;
        return this;
    }

    List opCatAssign(List l)
    {
        if ( l.empty )
            return this;
        if ( tail is null ) {
            head = l.head;
            tail = l.tail;
        }
        else {
            tail.next = l.head;
            tail.next.prev = tail;
            tail = l.tail;
        }
        len += l.len;
        return this;
    }

    List pushFront(T v)
    {
        if ( head is null )
            head = tail = new Element(v);
        else
        {
            head.prev = new Element(v);
            head.prev.next = head;
            head = head.prev;
        }
        ++len;
        return this;
    }

    List insertBefore(T w, T v)
    {
        foreach ( e; &this.elements )
        {
            if ( e.value is w )
                return insertBefore(e, v);
        }
        return null;
    }

    List insertBefore(Element e, T v)
    {
        auto tmp = new Element(v);
        tmp.prev = e.prev;
        tmp.next = e;
        e.prev.next = tmp;
        e.prev = tmp;
        if ( e is head )
            head = tmp;
        ++len;
        return this;
    }

    List pushFront(List l)
    {
        if ( l.empty )
            return this;
        if ( head is null ) {
            head = l.head;
            tail = l.tail;
        }
        else {
            head.prev = l.tail;
            head.prev.next = head;
            head = l.head;
        }
        len += l.len;
        return this;
    }

    size_t length()
    {
        return len;
    }

    bool empty()
    {
        return head is null;
    }

    void clear()
    {
        head = null;
        tail = null;
        len = 0;
    }

    void pop()
    {
        remove(tail);
    }

    void remove(Element e)
    {
        if ( e is null )
            return;
        if ( e.prev is null )
            head = e.next;
        else
            e.prev.next = e.next;
        if ( e.next is null )
            tail = e.prev;
        else
            e.next.prev = e.prev;
        --len;
    }

    int elements(int delegate(ref Element) dg)
    {
        for ( Element e=head; e !is null; e = e.next )
        {
            int ret = dg(e);
            if ( ret )
                return ret;
        }
        return 0;
    }

    int elements_reverse(int delegate(ref Element) dg)
    {
        for ( Element e=tail; e !is null; e = e.prev )
        {
            int ret = dg(e);
            if ( ret )
                return ret;
        }
        return 0;
    }

    int opApply(int delegate(ref T) dg)
    {
        for ( Element e=head; e !is null; e = e.next )
        {
            int ret = dg(e.value);
            if ( ret )
                return ret;
        }
        return 0;
    }

    int opApplyReverse(int delegate(ref T) dg)
    {
        for ( Element e=tail; e !is null; e = e.prev )
        {
            int ret = dg(e.value);
            if ( ret )
                return ret;
        }
        return 0;
    }
}

/* *****************************************************************************
    Stack based on dynamic array
*******************************************************************************/
private struct Stack(T)
{
    size_t  _top;
    T[]     stack;

    void push(T v)
    {
        if ( _top >= stack.length )
            stack.length = stack.length*2+1;
        stack[_top] = v;
        ++_top;
    }
    alias push opCatAssign;

    void opCatAssign(T[] vs)
    {
        size_t end = _top+vs.length;
        if ( end > stack.length )
            stack.length = end*2;
        stack[_top..end] = vs;
        _top = end;
    }

    void pop(size_t num)
    {
        assert(_top>=num);
        _top -= num;
    }

    T pop()
    {
        assert(_top>0);
        return stack[--_top];
    }

    T top()
    {
        assert(_top>0);
        return stack[_top-1];
    }

    T* topPtr()
    {
        assert(_top>0);
        return &stack[_top-1];
    }

    bool empty()
    {
        return _top == 0;
    }

    void clear()
    {
        _top = 0;
    }

    size_t length()
    {
        return _top;
    }

    T[] array()
    {
        return stack[0.._top];
    }

    T opIndex(size_t i)
    {
        return stack[i];
    }

    Stack dup()
    {
        Stack s;
        s._top = _top;
        s.stack = stack.dup;
        return s;
    }
}

/* ************************************************************************************************
    Set container based on assoc array
**************************************************************************************************/
private struct Set(T)
{
    bool[T] data;

    static Set opCall()
    {
        Set s;
        return s;
    }

    static Set opCall(T v)
    {
        Set s;
        s ~= v;
        return s;
    }

    void opAddAssign(T v)
    {
        data[v] = true;
    }

    void opAddAssign(Set s)
    {
        foreach ( v; s.elements )
            data[v] = true;
    }
    alias opAddAssign opCatAssign;

    size_t length()
    {
        return data.length;
    }

    T[] elements()
    {
        return data.keys;
    }

    bool remove(T v)
    {
        if ( (v in data) is null )
            return false;
        data.remove(v);
        return true;
    }

    bool contains(T v)
    {
        return (v in data) !is null;
    }

    bool contains(Set s)
    {
        Set tmp = s - *this;
        return tmp.empty;
    }

    bool empty()
    {
        return data.length==0;
    }

    Set opSub(Set s)
    {
        Set res = dup;
        foreach ( v; s.elements )
            res.remove(v);
        return res;
    }

    Set dup()
    {
        Set s;
        foreach ( v; data.keys )
            s.data[v] = true;
        return s;
    }
}

/* ************************************************************************************************

**************************************************************************************************/
void quickSort(T)(T[] a)
{
    quickSort(a,cast(size_t)0,a.length);
}

void quickSort(T)(T[] a, size_t l, size_t r)
{
    T t;
    auto i = r-l;
    if ( i < 3 )
    {
        if ( i < 2 )
            return;
        if ( a[l] < a[l+1] )
            return;
        t = a[l];
        a[l] = a[l+1];
        a[l+1] = t;
        return;
    }

    auto p = a[l];
    i = l;
    auto j = r;

    while ( true )
    {
        ++i;
        for ( ; i < j && a[i] < p; ++i ) {}
        --j;
        for ( ; i < j && a[j] >= p; --j ) {}
        if ( i >= j )
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    --i;
    a[l] = a[i];
    a[i] = p;

    quickSort(a, l, i);
    quickSort(a, i+1, r);
}
import tango.math.Math;

/* ************************************************************************************************
    A range of characters
**************************************************************************************************/
struct CharRange(char_t)
{
    char_t  l_, r_;

    static CharRange opCall(char_t c)
    {
        CharRange cr;
        cr.l_ = c;
        cr.r_ = c;
        return cr;
    }

    static CharRange opCall(char_t a, char_t b)
    {
        CharRange cr;
        cr.l_ = min(a,b);
        cr.r_ = max(a,b);
        return cr;
    }

    char_t l()
    {
        return l_;
    }

    char_t r()
    {
        return r_;
    }

    /* ********************************************************************************************
        Compares the ranges according to their beginning.
    **********************************************************************************************/
    int opCmp(CharRange cr)
    {
        if ( l_ == cr.l_ )
            return 0;
        if ( l_ < cr.l_ )
            return -1;
        return 1;
    }

    int opEquals(CharRange cr)
    {
        if ( l_ == cr.l_ && r_ == cr.r_ )
            return 1;
        return 0;
    }

    bool contains(char_t c)
    {
        return c >= l_ && c <= r_;
    }

    bool contains(CharRange cr)
    {
        return l_ <= cr.l_ && r_ >= cr.r_;
    }

    bool intersects(CharRange cr)
    {
        return r_ >= cr.l_ && l_ <= cr.r_;
    }

    CharRange intersect(CharRange cr)
    {
        assert(intersects(cr));
        CharRange ir;
        ir.l_ = max(l_, cr.l_);
        ir.r_ = min(r_, cr.r_);
        if ( ir.l_ > ir.r_ )
            ir.l_ = ir.r_ = char_t.min;
        return ir;
    }

    CharRange[] subtract(CharRange cr)
    {
        CharRange[] sr;
        if ( cr.contains(*this) )
            return sr;
        if ( !intersects(cr) )
            sr ~= *this;
        else
        {
            CharRange d;
            if ( contains(cr) )
            {
                d.l_ = l_;
                d.r_ = cr.l_-1;
                if ( d.l_ <= d.r_ )
                    sr ~= d;
                d.l_ = cr.r_+1;
                d.r_ = r_;
                if ( d.l_ <= d.r_ )
                    sr ~= d;
            }
            else if ( cr.r_ > l_ )
            {
                d.l_ = cr.r_+1;
                d.r_ = r_;
                if ( d.l_ <= d.r_ )
                    sr ~= d;
            }
            else if ( cr.l_ < r_ )
            {
                d.l_ = l_;
                d.r_ = cr.l_-1;
                if ( d.l_ <= d.r_ )
                    sr ~= d;
            }
        }
        return sr;
    }

    string toString()
    {
        string str;
        if ( l_ == r_ )
        {
            if ( l_ > 0x20 && l_ < 0x7f )
                str = Format.convert("'{}'", l_);
            else
                str = Format.convert("({:x})", cast(int)l_);
        }
        else
        {
            if ( l_ > 0x20 && l_ < 0x7f )
                str = Format.convert("'{}'", l_);
            else
                str = Format.convert("({:x})", cast(int)l_);
            str ~= "-";
            if ( r_ > 0x20 && r_ < 0x7f )
                str ~= Format.convert("'{}'", r_);
            else
                str ~= Format.convert("({:x})", cast(int)r_);
        }
        return str;
    }
}

/* ************************************************************************************************
    Represents a class of characters as used in regular expressions (e.g. [0-9a-z], etc.)
**************************************************************************************************/
struct CharClass(char_t)
{
    alias CharRange!(char_t) range_t;

    //---------------------------------------------------------------------------------------------
    // pre-defined character classes
    static const CharClass!(char_t)
        line_startend = {parts: [
            {l_:0x00, r_:0x00},
            {l_:0x0a, r_:0x0a},
            {l_:0x13, r_:0x13}
        ]},
        digit = {parts: [
            {l_:0x30, r_:0x39}
        ]},
        whitespace = {parts: [
            {l_:0x09, r_:0x09},
            {l_:0x0a, r_:0x0a},
            {l_:0x0b, r_:0x0b},
            {l_:0x13, r_:0x13},
            {l_:0x14, r_:0x14},
            {l_:0x20, r_:0x20}
        ]};

    // 8bit classes
    static if ( is(char_t == char) )
    {
        static const CharClass!(char_t)
            any_char = {parts: [
                {l_:0x01, r_:0xff}
            ]},
            dot_oper = {parts: [
                {l_:0x01, r_:0xff}
            ]},
            alphanum_ = {parts: [
                {l_:0x30, r_:0x39},
                {l_:0x41, r_:0x5a},
                {l_:0x5f, r_:0x5f},
                {l_:0x61, r_:0x7a}
            ]};
    }
    // 16bit and 32bit classes
    static if ( is(char_t == wchar) || is(char_t == dchar) )
    {
        static const CharClass!(char_t)
            any_char = {parts: [
                {l_:0x0001, r_:0xffff}
            ]},
            dot_oper = {parts: [
                {l_:0x0001, r_:0xffff}
            ]},
            alphanum_ = {parts: [
                {l_:0x30, r_:0x39},
                {l_:0x41, r_:0x5a},
                {l_:0x5f, r_:0x5f},
                {l_:0x61, r_:0x7a}
            ]};
    }

    //---------------------------------------------------------------------------------------------
    range_t[] parts;

    invariant()
    {
//        foreach ( i, p; parts )
//            assert(p.l_<=p.r_, Int.toString(i)~": "~Int.toString(p.l_)~" > "~Int.toString(p.r_));
    }

    static CharClass opCall(CharClass cc)
    {
        CharClass ncc;
        ncc.parts = cc.parts.dup;
        return ncc;
    }

    int opCmp(CharClass cc)
    {
        if ( parts.length < cc.parts.length )
            return -1;
        if ( parts.length > cc.parts.length )
            return 1;
        foreach ( i, p; cc.parts )
        {
            if ( p.l_ != parts[i].l_ || p.r_ != parts[i].r_ )
                return 1;
        }
        return 0;
    }

    bool empty()
    {
        return parts.length <= 0;
    }

    bool matches(char_t c)
    {
        foreach ( p; parts )
        {
            if ( p.contains(c) )
                return true;
        }
        return false;
    }

    CharClass intersect(CharClass cc)
    {
        CharClass ic;
        foreach ( p; parts )
        {
            foreach ( cp; cc.parts )
            {
                if ( p.intersects(cp) )
                    ic.parts ~= p.intersect(cp);
            }
        }
        return ic;
    }

    // requires the class to be optimized
    bool contains(range_t cr)
    {
        foreach ( p; parts )
        {
            if ( p.contains(cr) )
                return true;
        }
        return false;
    }

    // requires the class to be optimized
    bool contains(CharClass cc)
    {
        Louter: foreach ( p; cc.parts )
        {
            foreach ( p2; parts )
            {
                if ( p2.contains(p) )
                    continue Louter;
            }
            return false;
        }
        return true;
    }

    void subtract(CharClass cc)
    {
        negate;
        add(cc);
        negate;
    }

    void add(CharClass cc)
    {
        parts ~= cc.parts;
    }

    void add(range_t cr)
    {
        parts ~= cr;
    }

    void add(char_t c)
    {
        parts ~= CharRange!(char_t)(c);
    }

    /* ********************************************************************************************
        Requires the CharClass to be optimized.
    **********************************************************************************************/
    void negate()
    {
        optimize;
        char_t  start = char_t.min;

        // first part touches left boundary of value range
        if ( parts.length > 0 && parts[0].l_ == start )
        {
            start = parts[0].r_;
            if ( start < char_t.max )
                ++start;

            foreach ( i, ref cr; parts[0 .. $-1] )
            {
                cr.l_ = start;
                cr.r_ = parts[i+1].l_-1;
                start = parts[i+1].r_;
                if ( start < char_t.max )
                    ++start;
            }
            if ( start != char_t.max ) {
                parts[$-1].l_ = start;
                parts[$-1].r_ = char_t.max;
            }
            else
                parts.length = parts.length-1;
            return;
        }

        foreach ( i, ref cr; parts )
        {
            char_t tmp = cr.l_-1;
            cr.l_ = start;
            start = cr.r_;
            if ( start < char_t.max )
                ++start;
            cr.r_ = tmp;
        }

        // last part does not touch right boundary
        if ( start != char_t.max )
            parts ~= range_t(start, char_t.max);
    }

    void optimize()
    {
        if ( empty )
            return;

        parts.sort;

        size_t i = 0;
        foreach ( p; parts[1 .. $] )
        {
            if ( p.l_ > parts[i].r_+1 ) {
                ++i;
                parts[i].l_ = p.l_;
                parts[i].r_ = p.r_;
                continue;
            }
            parts[i].r_ = max(p.r_, parts[i].r_);
            if ( parts[i].r_ >= char_t.max )
                break;
        }
        parts.length = i+1;
    }

    char[] toString()
    {
        char[] str;
        str ~= "[";
        foreach ( p; parts )
            str ~= p.toString;
        str ~= "]";
        return str;
    }
}

debug(UnitTest)
{
unittest
{
    static CharClass!(char) cc = { parts: [{l_:0,r_:10},{l_:0,r_:6},{l_:5,r_:12},{l_:12,r_:17},{l_:20,r_:100}] };
    assert(cc.toString, "[(0)-(a)(0)-(6)(5)-(c)(c)-(11)(14)-'d']");
    cc.optimize;
    assert(cc.toString,  "[(0)-(11)(14)-'d']");
    cc.negate;
    assert(cc.toString,  " [(12)-(13)'e'-(ff)]");
    cc.optimize;
    assert(cc.toString,  "[(0)-(11)(14)-'d']");
    cc.negate;
    assert(cc.toString,  "[(12)-(13)'e'-(ff)]");

    static CharClass!(char) cc2 = { parts: [] };
    assert(cc.toString,  "[]");
    cc2.optimize;
    assert(cc.toString,  "[]");
    cc2.negate;
    assert(cc.toString,  "[(0)-(ff)]");
    cc2.optimize;
    assert(cc.toString,  "[(0)-(ff)]");
    cc2.negate;
    assert(cc.toString,  "[]");

    static CharClass!(char) cc3 = { parts: [{l_:0,r_:100},{l_:200,r_:0xff},] };
    assert(cc3.toString, "[(0)-'d'(c8)-(ff)]");
    cc3.negate;
    assert(cc.toString,  "['e'-(c7)]");
    cc3.negate;
    assert(cc.toString,  "[(0)-'d'(c8)-(ff)]");

    static CharClass!(char) cc4 = { parts: [{l_:0,r_:200},{l_:100,r_:0xff},] };
    assert(cc.toString,  "[(0)-(c8)'d'-(ff)]");
    cc4.optimize;
    assert(cc.toString,  "[(9)-(13)(20)-'~'(a0)-(ff)(100)-(17f)(180)-(24f)(20a3)-(20b5)]");

    static CharClass!(dchar) cc5 = { parts: [{l_:0x9,r_:0x13},{0x20,r_:'~'},{l_:0xa0,r_:0xff},{l_:0x100,r_:0x17f},{l_:0x180,r_:0x24f},{l_:0x20a3,r_:0x20b5}] };
    cc5.optimize;
    assert(cc.toString,  "[(9)-(13)(20)-'~'(a0)-(24f)(20a3)-(20b5)]");
    cc5.negate;
    assert(cc.toString,  "[(0)-(8)(14)-(1f)(7f)-(9f)(250)-(20a2)(20b6)-(10ffff)]");
    cc5.optimize;
    assert(cc.toString,  "[(0)-(8)(14)-(1f)(7f)-(9f)(250)-(20a2)(20b6)-(10ffff)]");
    cc5.negate;
    assert(cc.toString,  "[(9)-(13)(20)-'~'(a0)-(24f)(20a3)-(20b5)]");
}
}

/* ************************************************************************************************

**************************************************************************************************/
private struct Predicate(char_t)
{
    alias char_t[]              string_t;
    alias CharClass!(char_t)    cc_t;
    alias CharRange!(char_t)    cr_t;

    // generic data
    enum Type {
        consume, epsilon, lookahead, lookbehind
    }

    cc_t    input;
    Type    type;

    // data for compiled predicates
    const uint  MAX_BITMAP_LENGTH = 256,
                MAX_SEARCH_LENGTH = 256;
    enum MatchMode {
        generic, generic_l,
        single_char, bitmap, string_search,         // consume
        single_char_l, bitmap_l, string_search_l    // lookahead
    }

    MatchMode   mode;
    // data_chr had to be pulled out of the union due to
    // http://d.puremagic.com/issues/show_bug.cgi?id=2632 --- don't put it back
    // in until this is resolved!
    //
    // Keep in mind that data_str.length can't be modified directly unless the
    // new length is strictly greater than the old length. This is essentially
    // because ubyte.sizeof can be less than char_t.sizeof. If you set
    // data_str.length to anything less than or equal to data_bmp.length,
    // data_str will not be reallocated: only the length value will change but
    // nothing will realize that not that much space has actually been
    // allocated. data_str will be too small and you'll likely get segfaults or
    // such.
    //
    // In short: don't mess with data_str.length. If you have to, remove the
    // union entirely.
    //
    // -- Deewiant
    union {
        ubyte[]     data_bmp;
        string_t    data_str;
    };
    char_t      data_chr;


    void compile()
    {
        assert(input.parts.length > 0);

        // single char?
        if ( input.parts.length == 1 && input.parts[0].l_ == input.parts[0].r_ )
        {
            mode = type==Type.consume ? MatchMode.single_char : MatchMode.single_char_l;
            data_chr = input.parts[0].l_;
            return;
        }
        // check whether we can use a bitmap
        foreach ( p; input.parts )
        {
            if ( p.l_ > MAX_BITMAP_LENGTH || p.r_ > MAX_BITMAP_LENGTH )
                goto LnoBitmap;
        }

        // setup bitmap
        data_bmp.length = MAX_BITMAP_LENGTH/8;
        foreach ( p; input.parts )
        {
            for ( char_t c = p.l_; c <= p.r_; ++c )
                data_bmp[c/8] |= 1 << (c&7);
        }
        mode = type==Type.consume ? MatchMode.bitmap : MatchMode.bitmap_l;
        return;

    LnoBitmap:
/*
        // check whether the class is small enough to justify a string-search
        // TODO: consider inverse class for 8bit chars?
        uint class_size;
        foreach ( p; input.parts )
            class_size += cast(uint)p.r_+1-p.l_;
        if ( class_size > MAX_SEARCH_LENGTH )
            goto Lgeneric;
        data_str.length = class_size;
        size_t ind;
        foreach ( p; input.parts )
        {
            for ( char_t c = p.l_; c <= p.r_; ++c )
                data_str[ind++] = c;
        }
        mode = type==Type.consume ? MatchMode.string_search : MatchMode.string_search_l;
        return;
*/
    Lgeneric:
        data_str = cast(char_t[])input.parts;
        mode = type==Type.consume ? MatchMode.generic : MatchMode.generic_l;
    }

    bool matches(char_t c)
    {
        if ( type == Type.consume || type == Type.lookahead )
            return input.matches(c);
        assert(0);
    }

    Predicate intersect(Predicate p)
    {
        Predicate p2;
        if ( type != Type.epsilon && p.type != Type.epsilon )
            p2.input = input.intersect(p.input);
        return p2;
    }

    bool intersects(Predicate p)
    {
        if ( type != p.type )
            return false;
        foreach ( cr; input.parts )
        {
            foreach ( cr2; p.input.parts )
            {
                if ( cr.intersects(cr2) )
                    return true;
            }
        }
        return false;
    }

    bool exceedsMax(uint maxc)
    {
        foreach ( p; input.parts )
        {
            if ( p.l_ > maxc || p.r_ > maxc )
                return true;
        }

        return false;
    }

    bool empty()
    {
        return type != Type.epsilon && input.empty;
    }

    void subtract(Predicate p)
    {
        if ( type != Type.epsilon && p.type != Type.epsilon )
            input.subtract(p.input);
    }

    void negate()
    {
        assert(type != Type.epsilon);
        input.negate;
    }

    void optimize()
    {
        assert(type != Type.epsilon);
        input.optimize;
    }

    int opCmp(Predicate p)
    {
        return input.opCmp(p.input);
    }

    int opEquals(Predicate p)
    {
        if ( type != p.type )
            return 0;
        if ( input.opCmp(p.input) != 0 )
            return 0;
        return 1;
    }

    cc_t getInput()
    {
        return input;
    }

    void setInput(cc_t cc)
    {
        input = cc;
    }

    void appendInput(cr_t cr)
    {
        input.add(cr);
    }

    void appendInput(cc_t cc)
    {
        input.add(cc);
    }

    void appendInput(Predicate p)
    {
        input.add(p.input);
    }

    string toString()
    {
        string str;
        switch ( type )
        {
            case Type.consume:      str = input.toString;       break;
            case Type.epsilon:      str = "eps";                break;
            case Type.lookahead:    str = "la:"~input.toString; break;
            case Type.lookbehind:   str = "lb:"~input.toString; break;
            default:
                assert(0);
        }
        return str;
    }
}
import Utf = tango.text.convert.Utf;
import tango.text.convert.Format;

/* ************************************************************************************************

**************************************************************************************************/
class RegExpException : Exception
{
    this(string msg)
    {
        super("RegExp: "~msg);
    }
}

/* ************************************************************************************************
    TNFA state
**************************************************************************************************/
private class TNFAState(char_t)
{
    bool    accept = false,
            visited = false;
    uint    index;
    List!(TNFATransition!(char_t))  transitions;

    this()
    {
        transitions = new List!(TNFATransition!(char_t));
    }
}


/* ************************************************************************************************
    Priority classes used to linearize priorities after non-linear transition creation.
**************************************************************************************************/
private enum PriorityClass {
    greedy=0, normal=1, reluctant=2, extraReluctant=3
}

/* ********************************************************************************
    TNFA tagged transition
***********************************************************************************/
private class TNFATransition(char_t)
{
    TNFAState!(char_t)  target;
    Predicate!(char_t)  predicate;
    uint                priority,
                        tag;        /// one-based tag number, 0 = untagged
    PriorityClass       priorityClass;

    this(PriorityClass pc)
    {
        priorityClass = pc;
    }

    /******************************************************************************
        Move through states only going via epsilon transitions, and only choosing
        the one with highest priority. If the highest priority transition from a
        state isn't an epsilon transition, false is returned.
        If the accepting NFA state can be reached in this manner, true is returned.

        NOTE: This method does not look for cycles which should be kept in mind for
        later. larsivi 20090827
    *******************************************************************************/
    bool canFinish()
    {
        TNFAState!(char_t)  t = target;
        while (!t.accept) {
            TNFATransition!(char_t) highestPriTrans;
            foreach (trans; t.transitions) {
                if (!highestPriTrans || highestPriTrans.priority > trans.priority)
                    highestPriTrans = trans;
            }
            if (!(highestPriTrans.predicate.type == Predicate!(char_t).Type.epsilon))
                return false;

            t = highestPriTrans.target;
        }
        return true;
    }

}

/* ************************************************************************************************
    Fragments of TNFAs as used in the Thompson method
**************************************************************************************************/
private class TNFAFragment(char_t)
{
    alias TNFAState!(char_t)        state_t;
    alias TNFATransition!(char_t)   trans_t;

    List!(trans_t)  entries,        /// transitions to be added to the entry state
                    exits,          /// transitions to be added to the exit state
                    entry_state,    /// transitions to write the entry state to
                    exit_state;     /// transitions to write the exit state to

    bool swapMatchingBracketSyntax;

    this()
    {
        entries     = new List!(trans_t);
        exits       = new List!(trans_t);
        entry_state = new List!(trans_t);
        exit_state  = new List!(trans_t);
    }

    /* ********************************************************************************************
        Write the given state as entry state to this fragment.
    **********************************************************************************************/
    void setEntry(state_t state)
    {
        state.transitions ~= entries;
        foreach ( t; entry_state )
            t.target = state;
    }

    /* ********************************************************************************************
        Write the given state as exit state to this fragment.
    **********************************************************************************************/
    void setExit(state_t state)
    {
        state.transitions ~= exits;
        foreach ( t; exit_state )
            t.target = state;
    }
}

/* ************************************************************************************************
    Tagged NFA
**************************************************************************************************/
private final class TNFA(char_t)
{
    alias TNFATransition!(char_t)   trans_t;
    alias TNFAFragment!(char_t)     frag_t;
    alias TNFAState!(char_t)        state_t;
    alias Predicate!(char_t)        predicate_t;
    alias char_t[]                  string_t;
    alias CharRange!(char_t)        range_t;
    alias CharClass!(char_t)        cc_t;

    string_t    pattern;
    state_t[]   states;
    state_t     start;

    bool swapMatchingBracketSyntax; /// whether to make (?...) matching and (...) non-matching

    /* ********************************************************************************************
        Creates the TNFA from the given regex pattern
    **********************************************************************************************/
    this(string_t regex)
    {
        next_tag        = 1;
        transitions     = new List!(trans_t);

        pattern = regex;
    }

    /* ********************************************************************************************
        Print the TNFA (tabular representation of the delta function)
    **********************************************************************************************/
    debug(TangoRegex) void print()
    {
        foreach ( int i, s; states )
        {
            Stdout.format("{}{:d2}{}", s is start?">":" ", i, s.accept?"*":" ");

            bool first=true;
            Stdout(" {");
            foreach ( t; s.transitions )
            {
                Stdout.format("{}{}{}:{}->{}", first?"":", ", t.priority, "gnrx"[t.priorityClass], t.predicate.toString, t.target is null?-1:t.target.index);
                if ( t.tag > 0 ) {
                    Stdout.format(" t{}", t.tag);
                }
                first = false;
            }
            Stdout("}").newline;
        }
    }

    uint tagCount()
    {
        return next_tag-1;
    }

    /* ********************************************************************************************
        Constructs the TNFA using extended Thompson method.
        Uses a slightly extended version of Dijkstra's shunting yard algorithm to convert
        the regexp from infix notation.
    **********************************************************************************************/
    void parse(bool unanchored)
    {
        List!(frag_t)       frags       = new List!(frag_t);
        Stack!(Operator)    opStack;
        Stack!(uint)        tagStack;
        Stack!(Pair!(uint)) occurStack;
        opStack ~= Operator.eos;

        /* ****************************************************************************************
            Perform action on operator stack
        ******************************************************************************************/
        bool perform(Operator next_op, bool explicit_operator=true)
        {
            // calculate index in action matrix
            int index = cast(int)opStack.top*(Operator.max+1);
            index += cast(int)next_op;

            debug(tnfa) Stdout.formatln("\t{}:{} -> {}  {} frag(s)",
                operator_names[opStack.top], operator_names[next_op], action_names[action_lookup[index]], frags.length
            );
            switch ( action_lookup[index] )
            {
                case Act.pua:
                    opStack ~= next_op;
                    if ( next_op == Operator.open_par ) {
                        tagStack ~= next_tag;
                        next_tag += 2;
                    }
                    break;
                case Act.poc:
                    switch ( opStack.top )
                    {
                        case Operator.concat:       constructConcat(frags);                             break;
                        case Operator.altern:       constructAltern(frags);                             break;
                        case Operator.zero_one_g:   constructZeroOne(frags, PriorityClass.greedy);      break;
                        case Operator.zero_one_ng:  constructZeroOne(frags, PriorityClass.reluctant);   break;
                        case Operator.zero_one_xr:  constructZeroOne(frags, PriorityClass.extraReluctant);  break;
                        case Operator.zero_more_g:  constructZeroMore(frags, PriorityClass.greedy);     break;
                        case Operator.zero_more_ng: constructZeroMore(frags, PriorityClass.reluctant);  break;
                        case Operator.zero_more_xr: constructZeroMore(frags, PriorityClass.extraReluctant); break;
                        case Operator.one_more_g:   constructOneMore(frags, PriorityClass.greedy);      break;
                        case Operator.one_more_ng:  constructOneMore(frags, PriorityClass.reluctant);   break;
                        case Operator.one_more_xr:  constructOneMore(frags, PriorityClass.extraReluctant);  break;
                        case Operator.occur_g:
                            Pair!(uint) occur = occurStack.pop;
                            constructOccur(frags, occur.a, occur.b, PriorityClass.greedy);
                            break;
                        case Operator.occur_ng:
                            Pair!(uint) occur = occurStack.pop;
                            constructOccur(frags, occur.a, occur.b, PriorityClass.reluctant);
                            break;
                        default:
                            throw new RegExpException("cannot process operand at \""~Utf.toString(pattern[cursor..$])~"\"");
                    }
                    opStack.pop;

                    perform(next_op, false);
                    break;
                case Act.poa:
                    opStack.pop;
                    break;
                case Act.pca:
                    if ( opStack.top == Operator.open_par )
                    {
                        if ( tagStack.empty )
                            throw new RegExpException(Format.convert("Missing opening parentheses for closing parentheses at char {} \"{}\"", cursor, Utf.toString(pattern[cursor..$])));
                        constructBracket(frags, tagStack.top);
                        tagStack.pop;
                    }
                    else {
                        assert(opStack.top == Operator.open_par_nm);
                        constructBracket(frags);
                    }
                    opStack.pop;
                    break;
                case Act.don:
                    return true;
                case Act.err:
                default:
                    throw new RegExpException(Format.convert("Unexpected operand at char {} \"{}\" in \"{}\"", cursor, Utf.toString(pattern[cursor..$]), Utf.toString(pattern)));
            }

            return false;
        }

        // add implicit extra reluctant .* (with . == any_char) at the beginning for unanchored matches
        // and matching bracket for total match group
        if ( unanchored ) {
            frags ~= constructChars(cc_t.any_char, predicate_t.Type.consume);
            perform(Operator.zero_more_xr, false);
            perform(Operator.concat, false);
            perform(Operator.open_par, false);
        }

        // convert regex to postfix and create TNFA
        bool implicit_concat;
        predicate_t.Type pred_type;

        while ( !endOfPattern )
        {
            pred_type = predicate_t.Type.consume;

            dchar c = readPattern;
            switch ( c )
            {
                case '|':
                    perform(Operator.altern);
                    implicit_concat = false;
                    break;
                case '(':
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = false;
                    if ( peekPattern == '?' ) {
                        readPattern;
                        perform(swapMatchingBracketSyntax?Operator.open_par:Operator.open_par_nm);
                    }
                    else
                        perform(swapMatchingBracketSyntax?Operator.open_par_nm:Operator.open_par);
                    break;
                case ')':
                    perform(Operator.close_par);
                    break;
                case '?':
                    if ( peekPattern == '?' ) {
                        readPattern;
                        perform(Operator.zero_one_ng);
                    }
                    else
                        perform(Operator.zero_one_g);
                    break;
                case '*':
                    if ( peekPattern == '?' ) {
                        readPattern;
                        perform(Operator.zero_more_ng);
                    }
                    else
                        perform(Operator.zero_more_g);
                    break;
                case '+':
                    if ( peekPattern == '?' ) {
                        readPattern;
                        perform(Operator.one_more_ng);
                    }
                    else
                        perform(Operator.one_more_g);
                    break;
                case '{':
                    Pair!(uint) occur;
                    parseOccurCount(occur.a, occur.b);
                    occurStack ~= occur;
                    if ( peekPattern == '?' ) {
                        readPattern;
                        perform(Operator.occur_ng);
                    }
                    else
                        perform(Operator.occur_g);
                    break;
                case '[':
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;
                    frags ~= constructCharClass(pred_type);
                    break;
                case '.':
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;
                    frags ~= constructChars(cc_t.dot_oper, pred_type);
                    break;
                case '$':
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;

                    frags ~= constructChars(cc_t.line_startend, predicate_t.Type.lookahead);
                    break;
                case '^':
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;

                    frags ~= constructChars(cc_t.line_startend, predicate_t.Type.lookbehind);
                    break;
                case '>':
                    c = readPattern;
                    pred_type = predicate_t.Type.lookahead;
                    if ( c == '[' )
                        goto case '[';
                    else if ( c == '\\' )
                        goto case '\\';
                    else if ( c == '.' )
                        goto case '.';
                    else
                        goto default;
                case '<':
                    c = readPattern;
                    pred_type = predicate_t.Type.lookbehind;
                    if ( c == '[' )
                        goto case '[';
                    else if ( c == '\\' )
                        goto case '\\';
                    else if ( c == '.' )
                        goto case '.';
                    else
                        goto default;
                case '\\':
                    c = readPattern;

                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;

                    switch ( c )
                    {
                        case 't':
                            frags ~= constructSingleChar('\t', pred_type);
                            break;
                        case 'n':
                            frags ~= constructSingleChar('\n', pred_type);
                            break;
                        case 'r':
                            frags ~= constructSingleChar('\r', pred_type);
                            break;
                        case 'w':   // alphanumeric and _
                            frags ~= constructChars(cc_t.alphanum_, pred_type);
                            break;
                        case 'W':   // non-(alphanum and _)
                            auto cc = cc_t(cc_t.alphanum_);
                            cc.negate;
                            frags ~= constructChars(cc, pred_type);
                            break;
                        case 's':   // whitespace
                            frags ~= constructChars(cc_t.whitespace, pred_type);
                            break;
                        case 'S':   // non-whitespace
                            auto cc = cc_t(cc_t.whitespace);
                            cc.negate;
                            frags ~= constructChars(cc, pred_type);
                            break;
                        case 'd':   // digit
                            frags ~= constructChars(cc_t.digit, pred_type);
                            break;
                        case 'D':   // non-digit
                            auto cc = cc_t(cc_t.digit);
                            cc.negate;
                            frags ~= constructChars(cc, pred_type);
                            break;
                        case 'b':   // either end of word
                            if ( pred_type != predicate_t.Type.consume )
                                throw new RegExpException("Escape sequence \\b not allowed in look-ahead or -behind");

                            // create (?<\S>\s|<\s>\S)
                            auto cc = cc_t(cc_t.whitespace);
                            cc.negate;

                            perform(Operator.open_par_nm);

                            frags ~= constructChars(cc, predicate_t.Type.lookbehind);
                            perform(Operator.concat, false);
                            frags ~= constructChars(cc_t.whitespace, predicate_t.Type.lookahead);
                            perform(Operator.altern, false);
                            frags ~= constructChars(cc_t.whitespace, predicate_t.Type.lookbehind);
                            perform(Operator.concat, false);
                            frags ~= constructChars(cc, predicate_t.Type.lookahead);

                            perform(Operator.close_par, false);
                            break;
                        case 'B':   // neither end of word
                            if ( pred_type != predicate_t.Type.consume )
                                throw new RegExpException("Escape sequence \\B not allowed in look-ahead or -behind");

                            // create (?<\S>\S|<\s>\s)
                            auto cc = cc_t(cc_t.whitespace);
                            cc.negate;

                            perform(Operator.open_par_nm);

                            frags ~= constructChars(cc, predicate_t.Type.lookbehind);
                            perform(Operator.concat, false);
                            frags ~= constructChars(cc, predicate_t.Type.lookahead);
                            perform(Operator.altern, false);
                            frags ~= constructChars(cc_t.whitespace, predicate_t.Type.lookbehind);
                            perform(Operator.concat, false);
                            frags ~= constructChars(cc_t.whitespace, predicate_t.Type.lookahead);

                            perform(Operator.close_par, false);
                            break;
                        case '(':
                        case ')':
                        case '[':
                        case ']':
                        case '{':
                        case '}':
                        case '*':
                        case '+':
                        case '?':
                        case '.':
                        case '\\':
                        case '^':
                        case '$':
                        case '|':
                        case '<':
                        case '>':
                        default:
                            frags ~= constructSingleChar(c, pred_type);
                            break;
//                            throw new RegExpException(Format.convert("Unknown escape sequence \\{}", c));
                    }
                    break;

                default:
                    if ( implicit_concat )
                        perform(Operator.concat, false);
                    implicit_concat = true;
                    frags ~= constructSingleChar(c, pred_type);
            }
        }

        // add implicit reluctant .* (with . == any_char) at the end for unanchored matches
        if ( unanchored )
        {
            perform(Operator.close_par, false);
            if ( implicit_concat )
                perform(Operator.concat, false);
            frags ~= constructChars(cc_t.any_char, predicate_t.Type.consume);
            perform(Operator.zero_more_ng, false);
        }

        // empty operator stack
        while ( !perform(Operator.eos) ) {}

        // set start and finish states
        start = addState;
        state_t finish = addState;
        finish.accept = true;

        foreach ( f; frags ) {
            f.setExit(finish);
            f.setEntry(start);
        }

        // set transition priorities
        List!(trans_t)[PriorityClass.max+1] trans;
        foreach ( ref t; trans )
            t = new List!(trans_t);

        Stack!(trans_t) todo;
        state_t state = start;

        while ( !todo.empty || !state.visited )
        {
            if ( !state.visited )
            {
                state.visited = true;
                foreach_reverse ( t; state.transitions )
                    todo ~= t;
            }

            if ( todo.empty )
                break;
            trans_t t = todo.top;
            todo.pop;
            assert(t.priorityClass<=PriorityClass.max);
            trans[t.priorityClass] ~= t;
            state = t.target;
        }

        uint nextPrio;
        foreach ( ts; trans )
        {
            foreach ( t; ts )
                t.priority = nextPrio++;
        }
    }

private:
    uint            next_tag;
    size_t          cursor,
                    next_cursor;
    List!(trans_t)  transitions;

    state_t[state_t]    clonedStates;
    trans_t[trans_t]    clonedTransitions;

    /// RegEx operators
    enum Operator {
        eos, concat, altern, open_par, close_par,
        zero_one_g, zero_more_g, one_more_g,        // greedy
        zero_one_ng, zero_more_ng, one_more_ng,     // non-greedy/reluctant
        zero_one_xr, zero_more_xr, one_more_xr,     // extra-reluctant
        open_par_nm, occur_g, occur_ng
    }
    const char[][] operator_names = ["EOS", "concat", "|", "(", ")", "?", "*", "+", "??", "*?", "+?", "??x", "*?x", "+?x", "(?", "{x,y}", "{x,y}?"];

    /// Actions for to-postfix transformation
    enum Act {
        pua, poc, poa, pca, don, err
    }
    const char[][] action_names = ["push+advance", "pop+copy", "pop+advance", "pop+copy+advance", "done", "error"];

    /// Action lookup for to-postfix transformation
    const Act[] action_lookup =
    [
    //  eos      concat   |        (        )        ?        *        +        ??       *?       +?       ??extra  *?extra  +?extra  (?       {x,y}    {x,y}?
        Act.don, Act.pua, Act.pua, Act.pua, Act.err, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua,
        Act.poc, Act.pua, Act.poc, Act.pua, Act.poc, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua,
        Act.err, Act.pua, Act.pua, Act.pua, Act.pca, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua,
        Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err, Act.err,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.err, Act.pua, Act.pua, Act.pua, Act.pca, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua, Act.pua,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc,
        Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.poc, Act.pua, Act.poc, Act.poc
    ];

    final dchar peekPattern()
    {
        auto tmp = next_cursor;
        if ( tmp < pattern.length )
            return decode(pattern, tmp);
        return 0;
    }

    final dchar readPattern()
    {
        cursor = next_cursor;
        if ( next_cursor < pattern.length )
            return decode(pattern, next_cursor);
        return 0;
    }

    final bool endOfPattern()
    {
        return next_cursor >= pattern.length;
    }

    state_t addState()
    {
        state_t s = new state_t;
        s.index = states.length;
        states ~= s;
        return s;
    }

    trans_t addTransition(PriorityClass pc = PriorityClass.normal)
    {
        trans_t trans = new trans_t(pc);
        transitions ~= trans;
        return trans;
    }

    uint parseNumber()
    {
        uint res;
        while ( !endOfPattern )
        {
            auto c = peekPattern;
            if ( c < '0' || c > '9' )
                break;
            res = res*10+(c-'0');
            readPattern;
        }
        return res;
    }

    void parseOccurCount(out uint minOccur, out uint maxOccur)
    {
        assert(pattern[cursor] == '{');