//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 objectauto 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 unittestauto 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:

Lines 1–500 of 1217. Load more