regex/internal/parser.d

//Written in the D programming language
/*
    Regular expression pattern parser.
*/
module std.regex.internal.parser;

import std.regex.internal.ir;
import std.range.primitives, std.uni, std.meta,
    std.traits, std.typecons, std.exception;
static import std.ascii;

// package relevant info from parser into a regex object
auto makeRegex(S, CG)(Parser!(S, CG) p)
{
    import std.regex.internal.backtracking : BacktrackingMatcher;
    import std.regex.internal.thompson : ThompsonMatcher;
    import std.algorithm.searching : canFind;
    alias Char = BasicElementOf!S;
    Regex!Char re;
    auto g = p.g;
    with(re)
    {
        ir = g.ir;
        dict = g.dict;
        ngroup = g.ngroup;
        maxCounterDepth = g.counterDepth;
        flags = p.re_flags;
        charsets = g.charsets;
        matchers = g.matchers;
        backrefed = g.backrefed;
        re.pattern = p.origin.idup;
        re.postprocess();
        // check if we have backreferences, if so - use backtracking
        if (__ctfe) factory = null; // allows us to use the awful enum re = regex(...);
        else if (re.backrefed.canFind!"a != 0")
            factory =  new RuntimeFactory!(BacktrackingMatcher, Char);
        else
            factory = new RuntimeFactory!(ThompsonMatcher, Char);
        debug(std_regex_parser)
        {
            __ctfe || print();
        }
        //@@@BUG@@@ (not reduced)
        //somehow just using validate _collides_ with std.utf.validate (!)
        version (assert) re.validateRe();
    }
    return re;
}

// helper for unittest
auto makeRegex(S)(S arg)
if (isSomeString!S)
{
    return makeRegex(Parser!(S, CodeGen)(arg, ""));
}

@system unittest
{
    import std.algorithm.comparison : equal;
    auto re = makeRegex(`(?P<name>\w+) = (?P<var>\d+)`);
    auto nc = re.namedCaptures;
    static assert(isRandomAccessRange!(typeof(nc)));
    assert(!nc.empty);
    assert(nc.length == 2);
    assert(nc.equal(["name", "var"]));
    assert(nc[0] == "name");
    assert(nc[1..$].equal(["var"]));

    re = makeRegex(`(\w+) (?P<named>\w+) (\w+)`);
    nc = re.namedCaptures;
    assert(nc.length == 1);
    assert(nc[0] == "named");
    assert(nc.front == "named");
    assert(nc.back == "named");

    re = makeRegex(`(\w+) (\w+)`);
    nc = re.namedCaptures;
    assert(nc.empty);

    re = makeRegex(`(?P<year>\d{4})/(?P<month>\d{2})/(?P<day>\d{2})/`);
    nc = re.namedCaptures;
    auto cp = nc.save;
    assert(nc.equal(cp));
    nc.popFront();
    assert(nc.equal(cp[1..$]));
    nc.popBack();
    assert(nc.equal(cp[1 .. $ - 1]));
}


@trusted void reverseBytecode()(Bytecode[] code)
{
    Bytecode[] rev = new Bytecode[code.length];
    uint revPc = cast(uint) rev.length;
    Stack!(Tuple!(uint, uint, uint)) stack;
    uint start = 0;
    uint end = cast(uint) code.length;
    for (;;)
    {
        for (uint pc = start; pc < end; )
        {
            immutable len = code[pc].length;
            if (code[pc].code == IR.GotoEndOr)
                break; //pick next alternation branch
            if (code[pc].isAtom)
            {
                rev[revPc - len .. revPc] = code[pc .. pc + len];
                revPc -= len;
                pc += len;
            }
            else if (code[pc].isStart || code[pc].isEnd)
            {
                //skip over other embedded lookbehinds they are reversed
                if (code[pc].code == IR.LookbehindStart
                    || code[pc].code == IR.NeglookbehindStart)
                {
                    immutable blockLen = len + code[pc].data
                         + code[pc].pairedLength;
                    rev[revPc - blockLen .. revPc] = code[pc .. pc + blockLen];
                    pc += blockLen;
                    revPc -= blockLen;
                    continue;
                }
                immutable second = code[pc].indexOfPair(pc);
                immutable secLen = code[second].length;
                rev[revPc - secLen .. revPc] = code[second .. second + secLen];
                revPc -= secLen;
                if (code[pc].code == IR.OrStart)
                {
                    //we pass len bytes forward, but secLen in reverse
                    immutable revStart = revPc - (second + len - secLen - pc);
                    uint r = revStart;
                    uint i = pc + IRL!(IR.OrStart);
                    while (code[i].code == IR.Option)
                    {
                        if (code[i - 1].code != IR.OrStart)
                        {
                            assert(code[i - 1].code == IR.GotoEndOr);
                            rev[r - 1] = code[i - 1];
                        }
                        rev[r] = code[i];
                        auto newStart = i + IRL!(IR.Option);
                        auto newEnd = newStart + code[i].data;
                        auto newRpc = r + code[i].data + IRL!(IR.Option);
                        if (code[newEnd].code != IR.OrEnd)
                        {
                            newRpc--;
                        }
                        stack.push(tuple(newStart, newEnd, newRpc));
                        r += code[i].data + IRL!(IR.Option);
                        i += code[i].data + IRL!(IR.Option);
                    }
                    pc = i;
                    revPc = revStart;
                    assert(code[pc].code == IR.OrEnd);
                }
                else
                    pc += len;
            }
        }
        if (stack.empty)
            break;
        start = stack.top[0];
        end = stack.top[1];
        revPc = stack.top[2];
        stack.pop();
    }
    code[] = rev[];
}

struct CodeGen
{
    Bytecode[] ir;                 // resulting bytecode
    Stack!(uint) fixupStack;       // stack of opened start instructions
    NamedGroup[] dict;             // maps name -> user group number
    Stack!(uint) groupStack;       // stack of current number of group
    uint nesting = 0;              // group nesting level and repetitions step
    uint lookaroundNest = 0;       // nesting of lookaround
    uint counterDepth = 0;         // current depth of nested counted repetitions
    CodepointSet[] charsets;       // sets for char classes
    const(CharMatcher)[] matchers; // matchers for char classes
    uint[] backrefed;              // bitarray for groups refered by backref
    uint ngroup;                   // final number of groups (of all patterns)

    void start(uint length)
    {
        if (!__ctfe)
            ir.reserve((length*5+2)/4);
        fixupStack.push(0);
        groupStack.push(1);//0 - whole match
    }

    //mark referenced groups for latter processing
    void markBackref(uint n)
    {
        if (n/32 >= backrefed.length)
            backrefed.length = n/32 + 1;
        backrefed[n / 32] |= 1 << (n & 31);
    }

    bool isOpenGroup(uint n)
    {
        import std.algorithm.searching : canFind;
        // walk the fixup stack and see if there are groups labeled 'n'
        // fixup '0' is reserved for alternations
        return fixupStack.data[1..$].
            canFind!(fix => ir[fix].code == IR.GroupStart && ir[fix].data == n)();
    }

    void put(Bytecode code)
    {
        enforce(ir.length < maxCompiledLength,
            "maximum compiled pattern length is exceeded");
        ir ~= code;
    }

    void putRaw(uint number)
    {
        enforce(ir.length < maxCompiledLength,
            "maximum compiled pattern length is exceeded");
        ir ~= Bytecode.fromRaw(number);
    }

    //try to generate optimal IR code for this CodepointSet
    @trusted void charsetToIr(CodepointSet set)
    {//@@@BUG@@@ writeln is @system
        uint chars = cast(uint) set.length;
        if (chars < Bytecode.maxSequence)
        {
            switch (chars)
            {
                case 1:
                    put(Bytecode(IR.Char, set.byCodepoint.front));
                    break;
                case 0:
                    throw new RegexException("empty CodepointSet not allowed");
                default:
                    foreach (ch; set.byCodepoint)
                        put(Bytecode(IR.OrChar, ch, chars));
            }
        }
        else
        {
            import std.algorithm.searching : countUntil;
            const ivals = set.byInterval;
            immutable n = charsets.countUntil(set);
            if (n >= 0)
            {
                if (ivals.length*2 > maxCharsetUsed)
                    put(Bytecode(IR.Trie, cast(uint) n));
                else
                    put(Bytecode(IR.CodepointSet, cast(uint) n));
                return;
            }
            if (ivals.length*2 > maxCharsetUsed)
            {
                auto t  = getMatcher(set);
                put(Bytecode(IR.Trie, cast(uint) matchers.length));
                matchers ~= t;
                debug(std_regex_allocation) writeln("Trie generated");
            }
            else
            {
                put(Bytecode(IR.CodepointSet, cast(uint) charsets.length));
                matchers ~= CharMatcher.init;
            }
            charsets ~= set;
            assert(charsets.length == matchers.length);
        }
    }

    void genLogicGroup()
    {
        nesting++;
        pushFixup(length);
        put(Bytecode(IR.Nop, 0));
    }

    void genGroup()
    {
        nesting++;
        pushFixup(length);
        immutable nglob = groupStack.top++;
        enforce(groupStack.top <= maxGroupNumber, "limit on number of submatches is exceeded");
        put(Bytecode(IR.GroupStart, nglob));
    }

    void genNamedGroup(string name)
    {
        import std.array : insertInPlace;
        import std.range : assumeSorted;
        nesting++;
        pushFixup(length);
        immutable nglob = groupStack.top++;
        enforce(groupStack.top <= maxGroupNumber, "limit on submatches is exceeded");
        auto t = NamedGroup(name, nglob);
        auto d = assumeSorted!"a.name < b.name"(dict);
        immutable ind = d.lowerBound(t).length;
        insertInPlace(dict, ind, t);
        put(Bytecode(IR.GroupStart, nglob));
    }

        //generate code for start of lookaround: (?= (?! (?<= (?<!
    void genLookaround(IR opcode)
    {
        nesting++;
        pushFixup(length);
        put(Bytecode(opcode, 0));
        put(Bytecode.fromRaw(0));
        put(Bytecode.fromRaw(0));
        groupStack.push(0);
        lookaroundNest++;
        enforce(lookaroundNest <= maxLookaroundDepth,
            "maximum lookaround depth is exceeded");
    }

    void endPattern(uint num)
    {
        import std.algorithm.comparison : max;
        put(Bytecode(IR.End, num));
        ngroup = max(ngroup, groupStack.top);
        groupStack.top = 1; // reset group counter
    }

    //fixup lookaround with start at offset fix and append a proper *-End opcode
    void fixLookaround(uint fix)
    {
        lookaroundNest--;
        ir[fix] = Bytecode(ir[fix].code,
            cast(uint) ir.length - fix - IRL!(IR.LookaheadStart));
        auto g = groupStack.pop();
        assert(!groupStack.empty);
        ir[fix+1] = Bytecode.fromRaw(groupStack.top);
        //groups are cumulative across lookarounds
        ir[fix+2] = Bytecode.fromRaw(groupStack.top+g);
        groupStack.top += g;
        if (ir[fix].code == IR.LookbehindStart || ir[fix].code == IR.NeglookbehindStart)
        {
            reverseBytecode(ir[fix + IRL!(IR.LookbehindStart) .. $]);
        }
        put(ir[fix].paired);
    }

    // repetition of {1,1}
    void fixRepetition(uint offset)
    {
        import std.algorithm.mutation : copy;
        immutable replace = ir[offset].code == IR.Nop;
        if (replace)
        {
            copy(ir[offset + 1 .. $], ir[offset .. $ - 1]);
            ir.length -= 1;
        }
    }

    // repetition of {x,y}
    void fixRepetition(uint offset, uint min, uint max, bool greedy)
    {
        static import std.algorithm.comparison;
        import std.algorithm.mutation : copy;
        import std.array : insertInPlace;
        immutable replace = ir[offset].code == IR.Nop;
        immutable len = cast(uint) ir.length - offset - replace;
        if (max != infinite)
        {
            if (min != 1 || max != 1)
            {
                Bytecode op = Bytecode(greedy ? IR.RepeatStart : IR.RepeatQStart, len);
                if (replace)
                    ir[offset] = op;
                else
                    insertInPlace(ir, offset, op);
                put(Bytecode(greedy ? IR.RepeatEnd : IR.RepeatQEnd, len));
                put(Bytecode.init); //hotspot
                putRaw(1);
                putRaw(min);
                putRaw(max);
                counterDepth = std.algorithm.comparison.max(counterDepth, nesting+1);
            }
        }
        else if (min) //&& max is infinite
        {
            if (min != 1)
            {
                Bytecode op = Bytecode(greedy ? IR.RepeatStart : IR.RepeatQStart, len);
                if (replace)
                    ir[offset] = op;
                else
                    insertInPlace(ir, offset, op);
                offset += 1;//so it still points to the repeated block
                put(Bytecode(greedy ? IR.RepeatEnd : IR.RepeatQEnd, len));
                put(Bytecode.init); //hotspot
                putRaw(1);
                putRaw(min);
                putRaw(min);
                counterDepth = std.algorithm.comparison.max(counterDepth, nesting+1);
            }
            else if (replace)
            {
                copy(ir[offset+1 .. $], ir[offset .. $-1]);
                ir.length -= 1;
            }
            put(Bytecode(greedy ? IR.InfiniteStart : IR.InfiniteQStart, len));
            enforce(ir.length + len < maxCompiledLength,  "maximum compiled pattern length is exceeded");
            ir ~= ir[offset .. offset+len];
            //IR.InfinteX is always a hotspot
            put(Bytecode(greedy ? IR.InfiniteEnd : IR.InfiniteQEnd, len));
            put(Bytecode.init); //merge index
        }
        else//vanila {0,inf}
        {
            Bytecode op = Bytecode(greedy ? IR.InfiniteStart : IR.InfiniteQStart, len);
            if (replace)
                ir[offset] = op;
            else
                insertInPlace(ir, offset, op);
            //IR.InfinteX is always a hotspot
            put(Bytecode(greedy ? IR.InfiniteEnd : IR.InfiniteQEnd, len));
            put(Bytecode.init); //merge index
        }
    }

    void fixAlternation()
    {
        import std.array : insertInPlace;
        uint fix = fixupStack.top;
        if (ir.length > fix && ir[fix].code == IR.Option)
        {
            ir[fix] = Bytecode(ir[fix].code, cast(uint) ir.length - fix);
            put(Bytecode(IR.GotoEndOr, 0));
            fixupStack.top = cast(uint) ir.length; //replace latest fixup for Option
            put(Bytecode(IR.Option, 0));
            return;
        }
        uint len, orStart;
        //start a new option
        if (fixupStack.length == 1)
        {//only root entry, effectively no fixup
            len = cast(uint) ir.length + IRL!(IR.GotoEndOr);
            orStart = 0;
        }
        else
        {//IR.lookahead, etc. fixups that have length > 1, thus check ir[x].length
            len = cast(uint) ir.length - fix - (ir[fix].length - 1);
            orStart = fix + ir[fix].length;
        }
        insertInPlace(ir, orStart, Bytecode(IR.OrStart, 0), Bytecode(IR.Option, len));
        assert(ir[orStart].code == IR.OrStart);
        put(Bytecode(IR.GotoEndOr, 0));
        fixupStack.push(orStart); //fixup for StartOR
        fixupStack.push(cast(uint) ir.length); //for second Option
        put(Bytecode(IR.Option, 0));
    }

    // finalizes IR.Option, fix points to the first option of sequence
    void finishAlternation(uint fix)
    {
        enforce(ir[fix].code == IR.Option, "no matching ')'");
        ir[fix] = Bytecode(ir[fix].code, cast(uint) ir.length - fix - IRL!(IR.OrStart));
        fix = fixupStack.pop();
        enforce(ir[fix].code == IR.OrStart, "no matching ')'");
        ir[fix] = Bytecode(IR.OrStart, cast(uint) ir.length - fix - IRL!(IR.OrStart));
        put(Bytecode(IR.OrEnd, cast(uint) ir.length - fix - IRL!(IR.OrStart)));
        uint pc = fix + IRL!(IR.OrStart);
        while (ir[pc].code == IR.Option)
        {
            pc = pc + ir[pc].data;
            if (ir[pc].code != IR.GotoEndOr)
                break;
            ir[pc] = Bytecode(IR.GotoEndOr, cast(uint)(ir.length - pc - IRL!(IR.OrEnd)));
            pc += IRL!(IR.GotoEndOr);
        }
        put(Bytecode.fromRaw(0));
    }

    // returns: (flag - repetition possible?, fixup of the start of this "group")
    Tuple!(bool, uint) onClose()
    {
        nesting--;
        uint fix = popFixup();
        switch (ir[fix].code)
        {
        case IR.GroupStart:
            put(Bytecode(IR.GroupEnd, ir[fix].data));
            return tuple(true, fix);
        case IR.LookaheadStart, IR.NeglookaheadStart, IR.LookbehindStart, IR.NeglookbehindStart:
            assert(lookaroundNest);
            fixLookaround(fix);
            return tuple(false, 0u);
        case IR.Option: //| xxx )
            //two fixups: last option + full OR
            finishAlternation(fix);
            fix = topFixup;
            switch (ir[fix].code)
            {
            case IR.GroupStart:
                popFixup();
                put(Bytecode(IR.GroupEnd, ir[fix].data));
                return tuple(true, fix);
            case IR.LookaheadStart, IR.NeglookaheadStart, IR.LookbehindStart, IR.NeglookbehindStart:
                assert(lookaroundNest);
                fix = popFixup();
                fixLookaround(fix);
                return tuple(false, 0u);
            default://(?:xxx)
                popFixup();
                return tuple(true, fix);
            }
        default://(?:xxx)
            return tuple(true, fix);
        }
    }

    uint popFixup(){ return fixupStack.pop(); }

    void pushFixup(uint val){ return fixupStack.push(val); }

    @property uint topFixup(){ return fixupStack.top; }

    @property size_t fixupLength(){ return fixupStack.data.length; }

    @property uint length(){ return cast(uint) ir.length; }
}

// safety limits
enum maxGroupNumber = 2^^19;
enum maxLookaroundDepth = 16;
// *Bytecode.sizeof, i.e. 1Mb of bytecode alone
enum maxCompiledLength = 2^^18;
// amounts to up to 4 Mb of auxilary table for matching
enum maxCumulativeRepetitionLength = 2^^20;
// marker to indicate infinite repetition
enum infinite = ~0u;

struct Parser(R, Generator)
if (isForwardRange!R && is(ElementType!R : dchar))
{
    dchar front;
    bool empty;
    R pat, origin;       //keep full pattern for pretty printing error messages
    uint re_flags = 0;   //global flags e.g. multiline + internal ones
    Generator g;

    @trusted this(S)(R pattern, S flags)
        if (isSomeString!S)
    {
        pat = origin = pattern;
        //reserve slightly more then avg as sampled from unittests
        parseFlags(flags);
        front = ' ';//a safe default for freeform parsing
        popFront();
        g.start(cast(uint) pat.length);
        try
        {
            parseRegex();
        }
        catch (Exception e)
        {
            error(e.msg);//also adds pattern location
        }
        g.endPattern(1);
    }

    void _popFront()
    {
        if (pat.empty)
        {
            empty =  true;
        }
        else
        {
            front = pat.front;
            pat.popFront();
        }
    }

    void skipSpace()
    {
        while (!empty && isWhite(front)) _popFront();
    }

    void popFront()
    {
        _popFront();
        if (re_flags & RegexOption.freeform) skipSpace();
    }

    auto save(){ return this; }

    //parsing number with basic overflow check
    uint parseDecimal()
    {
        uint r = 0;
        while (std.ascii.isDigit(front))
        {
            if (r >= (uint.max/10))
                error("Overflow in decimal number");
            r = 10*r + cast(uint)(front-'0');
            popFront();
            if (empty) break;
        }
        return r;
    }

    //
    @trusted void parseFlags(S)(S flags)
    {//@@@BUG@@@ text is @system
        import std.conv : text;
        foreach (ch; flags)//flags are ASCII anyway
        {
        L_FlagSwitch:
            switch (ch)
            {

                foreach (i, op; __traits(allMembers, RegexOption))
                {
                    case RegexOptionNames[i]:
                            if (re_flags & mixin("RegexOption."~op))
                                throw new RegexException(text("redundant flag specified: ",ch));
                            re_flags |= mixin("RegexOption."~op);
                            break L_FlagSwitch;
                }
                default:
                    throw new RegexException(text("unknown regex flag '",ch,"'"));
            }
        }
    }

    //parse and store IR for regex pattern
    @trusted void parseRegex()
    {
        uint fix;//fixup pointer

        while (!empty)
        {
            debug(std_regex_parser)
                __ctfe || writeln("*LR*\nSource: ", pat, "\nStack: ",fixupStack.data);
            switch (front)
            {
            case '(':
                popFront();
                if (front == '?')
                {
                    popFront();
                    switch (front)
                    {
                    case '#':
                        for (;;)
                        {
                            popFront();
                            enforce(!empty, "Unexpected end of pattern");
                            if (front == ')')
                            {
                                popFront();
                                break;
                            }
                        }
                        break;
                    case ':':
                        g.genLogicGroup();
                        popFront();
                        break;
                    case '=':
                        g.genLookaround(IR.LookaheadStart);
                        popFront();
                        break;
                    case '!':
                        g.genLookaround(IR.NeglookaheadStart);
                        popFront();
                        break;
                    case 'P':
                        popFront();
                        enforce(front == '<', "Expected '<' in named group");
                        string name;
                        popFront();
                        if (empty || !(isAlpha(front) || front == '_'))
                            error("Expected alpha starting a named group");
                        name ~= front;
                        popFront();
                        while (!empty && (isAlpha(front) ||
                            front == '_' || std.ascii.isDigit(front)))
                        {
                            name ~= front;
                            popFront();
                        }
                        enforce(front == '>', "Expected '>' closing named group");
                        popFront();
                        g.genNamedGroup(name);
                        break;
                    case '<':
                        popFront();
                        if (front == '=')
                            g.genLookaround(IR.LookbehindStart);
                        else if (front == '!')
                            g.genLookaround(IR.NeglookbehindStart);
                        else
                            error("'!' or '=' expected after '<'");
                        popFront();
                        break;
                    default:
                        uint enableFlags, disableFlags;
                        bool enable = true;
                        do
                        {
                            switch (front)
                            {
                            case 's':
                                if (enable)
                                    enableFlags |= RegexOption.singleline;
                                else
                                    disableFlags |= RegexOption.singleline;
                                break;
                            case 'x':
                                if (enable)
                                    enableFlags |= RegexOption.freeform;
                                else
                                    disableFlags |= RegexOption.freeform;
                                break;
                            case 'i':
                                if (enable)
                                    enableFlags |= RegexOption.casefold;
                                else
                                    disableFlags |= RegexOption.casefold;
                                break;
                            case 'm':
                                if (enable)
                                    enableFlags |= RegexOption.multiline;
                                else
                                    disableFlags |= RegexOption.multiline;
                                break;
                            case '-':
                                if (!enable)
                                    error(" unexpected second '-' in flags");
                                enable = false;
                                break;
                            default:
                                error(" 's', 'x', 'i', 'm' or '-' expected after '(?' ");
                            }
                            popFront();
                        }while (front != ')');
                        popFront();
                        re_flags |= enableFlags;
                        re_flags &= ~disableFlags;
                    }
                }
                else
                {
                    g.genGroup();
                }
                break;
            case ')':
                enforce(g.nesting, "Unmatched ')'");
                popFront();
                auto pair = g.onClose();
                if (pair[0])
                    parseQuantifier(pair[1]);
                break;
            case '|':
                popFront();
                g.fixAlternation();
                break;
            default://no groups or whatever
                immutable start = g.length;
                parseAtom();
                parseQuantifier(start);
            }
        }

        if (g.fixupLength != 1)
        {
            fix = g.popFixup();
            g.finishAlternation(fix);
            enforce(g.fixupLength == 1, "no matching ')'");
        }
    }


    //parse and store IR for atom-quantifier pair
    @trusted void parseQuantifier(uint offset)
    {//copy is @system
        if (empty)
            return g.fixRepetition(offset);
        uint min, max;
        switch (front)
        {
        case '*':
            min = 0;
            max = infinite;
            break;
        case '?':
            min = 0;
            max = 1;
            break;
        case '+':
            min = 1;
            max = infinite;
            break;
        case '{':
            popFront();
            enforce(!empty, "Unexpected end of regex pattern");
            enforce(std.ascii.isDigit(front), "First number required in repetition");
            min = parseDecimal();
            if (front == '}')
                max = min;
            else if (front == ',')
            {
                popFront();
                if (std.ascii.isDigit(front))
                    max = parseDecimal();
                else if (front == '}')
                    max = infinite;
                else
                    error("Unexpected symbol in regex pattern");
                skipSpace();
                enforce(front == '}', "Unmatched '{' in regex pattern");
            }
            else
                error("Unexpected symbol in regex pattern");
            enforce(min <= max, "Illegal {n,m} quantifier");
            break;
        default:
            g.fixRepetition(offset);
            return;
        }
        bool greedy = true;
        //check only if we managed to get new symbol
        popFront();
        if (!empty && front == '?')
        {
            greedy = false;
            popFront();
        }
        g.fixRepetition(offset, min, max, greedy);
    }

    //parse and store IR for atom
    void parseAtom()
    {
        if (empty)
            return;
        switch (front)
        {
        case '*', '?', '+', '|', '{', '}':
            error("'*', '+', '?', '{', '}' not allowed in atom");
        case '.':
            if (re_flags & RegexOption.singleline)
                g.put(Bytecode(IR.Any, 0));
            else
            {
                CodepointSet set;
                g.charsetToIr(set.add('\n','\n'+1).add('\r', '\r'+1).inverted);
            }
            popFront();
            break;
        case '[':
            parseCharset();
            break;
        case '\\':
            _popFront();
            enforce(!empty, "Unfinished escape sequence");
            parseEscape();
            break;
        case '^':
            if (re_flags & RegexOption.multiline)
                g.put(Bytecode(IR.Bol, 0));
            else
                g.put(Bytecode(IR.Bof, 0));
            popFront();
            break;
        case '$':
            if (re_flags & RegexOption.multiline)
                g.put(Bytecode(IR.Eol, 0));
            else
                g.put(Bytecode(IR.Eof, 0));
            popFront();
            break;
        default:
            if (re_flags & RegexOption.casefold)
            {
                auto range = simpleCaseFoldings(front);
                assert(range.length <= 5);
                if (range.length == 1)
                    g.put(Bytecode(IR.Char, range.front));
                else
                    foreach (v; range)
                        g.put(Bytecode(IR.OrChar, v, cast(uint) range.length));
            }
            else
                g.put(Bytecode(IR.Char, front));
            popFront();
        }
    }

    //parse and store IR for CodepointSet
    void parseCharset()
    {
        const save = re_flags;
        re_flags &= ~RegexOption.freeform; // stop ignoring whitespace if we did
        bool casefold = cast(bool)(re_flags & RegexOption.casefold);
        g.charsetToIr(unicode.parseSet(this, casefold));
        re_flags = save;
        // Last next() in parseCharset is executed w/o freeform flag
        if (re_flags & RegexOption.freeform) skipSpace();
    }

    //parse and generate IR for escape stand alone escape sequence
    @trusted void parseEscape()
    {//accesses array of appender
        import std.algorithm.iteration : sum;
        switch (front)
        {
        case 'f':   popFront(); g.put(Bytecode(IR.Char, '\f')); break;
        case 'n':   popFront(); g.put(Bytecode(IR.Char, '\n')); break;
        case 'r':   popFront(); g.put(Bytecode(IR.Char, '\r')); break;
        case 't':   popFront(); g.put(Bytecode(IR.Char, '\t')); break;
        case 'v':   popFront(); g.put(Bytecode(IR.Char, '\v')); break;

        case 'd':
            popFront();
            g.charsetToIr(unicode.Nd);
            break;
        case 'D':
            popFront();
            g.charsetToIr(unicode.Nd.inverted);
            break;
        case 'b':   popFront(); g.put(Bytecode(IR.Wordboundary, 0)); break;
        case 'B':   popFront(); g.put(Bytecode(IR.Notwordboundary, 0)); break;
        case 's':
            popFront();
            g.charsetToIr(unicode.White_Space);
            break;
        case 'S':
            popFront();
            g.charsetToIr(unicode.White_Space.inverted);
            break;
        case 'w':
            popFront();
            g.charsetToIr(wordCharacter);
            break;
        case 'W':
            popFront();
            g.charsetToIr(wordCharacter.inverted);
            break;
        case 'p': case 'P':
            bool casefold = cast(bool)(re_flags & RegexOption.casefold);
            auto set = unicode.parsePropertySpec(this, front == 'P', casefold);
            g.charsetToIr(set);
            break;
        case 'x':
            immutable code = parseUniHex(pat, 2);
            popFront();
            g.put(Bytecode(IR.Char,code));
            break;
        case 'u': case 'U':
            immutable code = parseUniHex(pat, front == 'u' ? 4 : 8);
            popFront();
            g.put(Bytecode(IR.Char, code));
            break;
        case 'c': //control codes
            Bytecode code = Bytecode(IR.Char, unicode.parseControlCode(this));
            popFront();
            g.put(code);
            break;
        case '0':
            popFront();
            g.put(Bytecode(IR.Char, 0));//NUL character
            break;
        case '1': .. case '9':
            uint nref = cast(uint) front - '0';
            immutable maxBackref = sum(g.groupStack.data);
            enforce(nref < maxBackref, "Backref to unseen group");
            //perl's disambiguation rule i.e.
            //get next digit only if there is such group number
            popFront();
            while (nref < maxBackref && !empty && std.ascii.isDigit(front))
            {
                nref = nref * 10 + front - '0';
                popFront();
            }
            if (nref >= maxBackref)
                nref /= 10;
            enforce(!g.isOpenGroup(nref), "Backref to open group");
            uint localLimit = maxBackref - g.groupStack.top;
            if (nref >= localLimit)
            {
                g.put(Bytecode(IR.Backref, nref-localLimit));
                g.ir[$-1].setLocalRef();
            }
            else
                g.put(Bytecode(IR.Backref, nref));
            g.markBackref(nref);
            break;
        default:
            if (front == '\\' && !pat.empty)
            {
                if (pat.front >= privateUseStart && pat.front <= privateUseEnd)
                    enforce(false, "invalid escape sequence");
            }
            if (front >= privateUseStart && front <= privateUseEnd)
            {
                g.endPattern(front - privateUseStart + 1);
                break;
            }
            auto op = Bytecode(IR.Char, front);
            popFront();
            g.put(op);
        }
    }

    //
    @trusted void error(string msg)
    {
        import std.array : appender;
        import std.format.write : formattedWrite;
        auto app = appender!string();
        formattedWrite(app, "%s\nPattern with error: `%s` <--HERE-- `%s`",
                       msg, origin[0..$-pat.length], pat);
        throw new RegexException(app.data);
    }

    alias Char = BasicElementOf!R;

    @property program()
    {
        return makeRegex(this);
    }
}

/+
    Postproces the IR, then optimize.
+/
@trusted void postprocess(Char)(ref Regex!Char zis)
{//@@@BUG@@@ write is @system
    with(zis)
    {
        struct FixedStack(T)
        {
            T[] arr;
            uint _top;
            //this(T[] storage){   arr = storage; _top = -1; }
            @property ref T top(){  assert(!empty); return arr[_top]; }
            void push(T x){  arr[++_top] = x; }
            T pop() { assert(!empty);   return arr[_top--]; }
            @property bool empty(){   return _top == -1; }
        }
        auto counterRange = FixedStack!uint(new uint[maxCounterDepth+1], -1);
        counterRange.push(1);
        ulong cumRange = 0;
        for (uint i = 0; i < ir.length; i += ir[i].length)
        {
            if (ir[i].hotspot)
            {
                assert(i + 1 < ir.length,
                    "unexpected end of IR while looking for hotspot");
                ir[i+1] = Bytecode.fromRaw(hotspotTableSize);
                hotspotTableSize += counterRange.top;
            }
            switch (ir[i].code)
            {
            case IR.RepeatStart, IR.RepeatQStart:
                uint repEnd = cast(uint)(i + ir[i].data + IRL!(IR.RepeatStart));
                assert(ir[repEnd].code == ir[i].paired.code);
                immutable max = ir[repEnd + 4].raw;
                ir[repEnd+2].raw = counterRange.top;
                ir[repEnd+3].raw *= counterRange.top;
                ir[repEnd+4].raw *= counterRange.top;
                ulong cntRange = cast(ulong)(max)*counterRange.top;
                cumRange += cntRange;
                enforce(cumRange < maxCumulativeRepetitionLength,
                    "repetition length limit is exceeded");
                counterRange.push(cast(uint) cntRange + counterRange.top);
                threadCount += counterRange.top;
                break;
            case IR.RepeatEnd, IR.RepeatQEnd:
                threadCount += counterRange.top;
                counterRange.pop();
                break;
            case IR.GroupStart:
                if (isBackref(ir[i].data))
                    ir[i].setBackrefence();
                threadCount += counterRange.top;
                break;
            case IR.GroupEnd:
                if (isBackref(ir[i].data))
                    ir[i].setBackrefence();
                threadCount += counterRange.top;
                break;
            default:
                threadCount += counterRange.top;
            }
        }
        checkIfOneShot();
        if (!(flags & RegexInfo.oneShot))
            kickstart = Kickstart!Char(zis, new uint[](256));
        debug(std_regex_allocation) writefln("IR processed, max threads: %d", threadCount);
        optimize(zis);
    }
}

void fixupBytecode()(Bytecode[] ir)
{
    Stack!uint fixups;

    with(IR) for (uint i=0; i<ir.length; i+= ir[i].length)
    {
        if (ir[i].isStart || ir[i].code == Option)
            fixups.push(i);
        else if (ir[i].code == OrEnd)
        {
            // Alternatives need more care
            auto j = fixups.pop(); // last Option
            ir[j].data = i -  j - ir[j].length;
            j = fixups.pop(); // OrStart
            ir[j].data = i - j - ir[j].length;
            ir[i].data = ir[j].data;

            // fixup all GotoEndOrs
            j = j + IRL!(OrStart);
            assert(ir[j].code == Option);
            for (;;)
            {
                auto next = j + ir[j].data + IRL!(Option);
                if (ir[next].code == IR.OrEnd)
                    break;
                ir[next - IRL!(GotoEndOr)].data = i - next;
                j = next;
            }
        }
        else if (ir[i].code == GotoEndOr)
        {
            auto j = fixups.pop(); // Option
            ir[j].data = i - j + IRL!(GotoEndOr)- IRL!(Option); // to the next option
        }
        else if (ir[i].isEnd)
        {
            auto j = fixups.pop();
            ir[i].data = i - j - ir[j].length;
            ir[j].data = ir[i].data;
        }
    }
    assert(fixups.empty);
}

void optimize(Char)(ref Regex!Char zis)
{
    import std.array : insertInPlace;
    CodepointSet nextSet(uint idx)
    {
        CodepointSet set;
        with(zis) with(IR)
    Outer:
        for (uint i = idx; i < ir.length; i += ir[i].length)
        {
            switch (ir[i].code)
            {
                case Char:
                    set.add(ir[i].data, ir[i].data+1);
                    goto default;
                //TODO: OrChar
                case Trie, CodepointSet:
                    set = zis.charsets[ir[i].data];
                    goto default;
                case GroupStart,GroupEnd:
                    break;
                default:
                    break Outer;
            }
        }
        return set;
    }

    with(zis) with(IR) for (uint i = 0; i < ir.length; i += ir[i].length)
    {
        if (ir[i].code == InfiniteEnd)
        {
            auto set = nextSet(i+IRL!(InfiniteEnd));
            if (!set.empty && set.length < 10_000)
            {
                ir[i] = Bytecode(InfiniteBloomEnd, ir[i].data);
                ir[i - ir[i].data - IRL!(InfiniteStart)] =
                    Bytecode(InfiniteBloomStart, ir[i].data);
                ir.insertInPlace(i+IRL!(InfiniteEnd),
                    Bytecode.fromRaw(cast(uint) zis.filters.length));
                zis.filters ~= BitTable(set);
                fixupBytecode(ir);
            }
        }
    }
}

//IR code validator - proper nesting, illegal instructions, etc.
@trusted void validateRe(Char)(ref Regex!Char zis)
{//@@@BUG@@@ text is @system
    import std.conv : text;
    with(zis)
    {
        for (uint pc = 0; pc < ir.length; pc += ir[pc].length)
        {
            if (ir[pc].isStart || ir[pc].isEnd)
            {
                immutable dest = ir[pc].indexOfPair(pc);
                assert(dest < ir.length, text("Wrong length in opcode at pc=",
                    pc, " ", dest, " vs ", ir.length));
                assert(ir[dest].paired ==  ir[pc],
                    text("Wrong pairing of opcodes at pc=", pc, "and pc=", dest));
            }
            else if (ir[pc].isAtom)
            {

            }
            else
               assert(0, text("Unknown type of instruction at pc=", pc));
        }
    }
}