source: icGREP/icgrep-devel/icgrep/re/re_compiler.cpp @ 5816

Last change on this file since 5816 was 5816, checked in by cameron, 16 months ago

Supporting multiple alphabets in RE compilation - initial check-in

File size: 28.3 KB
RevLine 
[3850]1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
[5267]6
7
8
9#include "re_compiler.h"
10#include <pablo/pe_ones.h>          // for Ones
11#include <pablo/pe_var.h>           // for Var
12#include <pablo/pe_zeroes.h>        // for Zeroes
13#include <re/printer_re.h>
14#include <re/re_alt.h>
15#include <re/re_analysis.h>         // for isByteLength, isUnicodeUnitLength
[4245]16#include <re/re_any.h>
[5267]17#include <re/re_assertion.h>        // for Assertion, Assertion::Sense, Asse...
18#include <re/re_cc.h>               // for makeCC
19#include <re/re_diff.h>             // for Diff
20#include <re/re_end.h>
21#include <re/re_intersect.h>        // for Intersect
22#include <re/re_name.h>             // for Name, Name::Type, Name::Type::Zer...
23#include <re/re_name_resolve.h>     // for resolveNames
[5565]24#include <re/re_name_gather.h>      // for gatherNames
[5267]25#include <re/re_rep.h>              // for Rep, Rep::::UNBOUNDED_REP
26#include <re/re_seq.h>              // for Seq
[4199]27#include <re/re_start.h>
[5617]28#include <re/re_local.h>
[5802]29#include <re/to_utf8.h>
[5267]30#include <re/re_toolchain.h>        // for AlgorithmOptionIsSet, RE_Algorith...
[5816]31#include <cc/alphabet.h>
32#include <cc/cc_compiler.h>
[5267]33#include "pablo/builder.hpp"        // for PabloBuilder
[5755]34#include <IR_Gen/idisa_target.h>    // for AVX2_available
[5816]35#include <llvm/ADT/STLExtras.h> // for make_unique
36#include <llvm/Support/raw_ostream.h>
[5706]37#include <llvm/Support/ErrorHandling.h>
[5610]38
[5267]39namespace pablo { class PabloAST; }
[5816]40namespace pablo { class Var; }
[5267]41namespace pablo { class PabloKernel; }
42namespace re { class Alt; }
43namespace re { class RE; }
[4459]44
[4340]45using namespace pablo;
[5267]46using namespace llvm;
[4340]47
[5812]48using FollowMap = std::map<re::CC *, re::CC*>;
49
[4340]50namespace re {
51
[5816]52   
53void RE_Compiler::addAlphabet(cc::Alphabet * a, pablo::Var * basis_set) {
54    mAlphabets.push_back(a);
55    mAlphabetCompilers.push_back(make_unique<cc::CC_Compiler>(mKernel, basis_set));
56}
57
[5812]58using MarkerType = RE_Compiler::MarkerType;
59
60PabloAST * RE_Compiler::compile(RE * re, PabloAST * const initialCursors) {
61    const auto markers = initialCursors ? compile(re, initialCursors, mPB) : compile(re, mPB);
62    return markerVar(AdvanceMarker(markers, FinalPostPositionUnit, mPB));
[4197]63}
[5812]64
65inline MarkerType RE_Compiler::compile(RE * re, PabloAST * const cursors, PabloBuilder & pb) {
66    return process(re, makeMarker(FinalMatchUnit, cursors), pb);
[4330]67}
[5812]68
69inline MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
70    return process(re, makeMarker(FinalPostPositionUnit, pb.createOnes()), pb);
71}
[5548]72   
[4622]73MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
[5780]74    if (isa<Name>(re)) {
75        return compileName(cast<Name>(re), marker, pb);
76    } else if (isa<Seq>(re)) {
77        return compileSeq(cast<Seq>(re), marker, pb);
78    } else if (isa<Alt>(re)) {
79        return compileAlt(cast<Alt>(re), marker, pb);
80    } else if (isa<Rep>(re)) {
81        return compileRep(cast<Rep>(re), marker, pb);
82    } else if (isa<Assertion>(re)) {
83        return compileAssertion(cast<Assertion>(re), marker, pb);
84    } else if (isa<Any>(re)) {
85        return compileAny(marker, pb);
86    } else if (isa<Diff>(re)) {
87        return compileDiff(cast<Diff>(re), marker, pb);
88    } else if (isa<Intersect>(re)) {
89        return compileIntersect(cast<Intersect>(re), marker, pb);
90    } else if (isa<Start>(re)) {
91        return compileStart(marker, pb);
92    } else if (isa<End>(re)) {
93        return compileEnd(marker, pb);
94    } else if (isa<CC>(re)) {
95        // CCs may be passed through the toolchain directly to the compiler.
96        return compileCC(cast<CC>(re), marker, pb);
[5617]97    } else {
[5780]98        UnsupportedRE("RE Compiler failed to process " + Printer_RE::PrintRE(re));
[4197]99    }
100}
[3850]101
[4829]102inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
[5812]103    PabloAST * const nextFinalByte = markerVar(AdvanceMarker(m, FinalPostPositionUnit, pb));
104    return makeMarker(FinalMatchUnit, nextFinalByte);
[4829]105}
106
[5555]107MarkerType RE_Compiler::compileCC(CC * cc, MarkerType marker, PabloBuilder & pb) {
[5813]108    PabloAST * nextPos = markerVar(marker);
[5816]109    const cc::Alphabet * a = cc->getAlphabet();
110    if (a == &cc::Byte) {
[5812]111        if (marker.pos == FinalMatchUnit) {
112            nextPos = pb.createAdvance(nextPos, 1);
113        }
[5816]114        return makeMarker(FinalMatchUnit, pb.createAnd(nextPos, mCCCompiler.compileCC(cc, pb)));
115    } else if (a == &cc::Unicode) {
116        MarkerType m = compile(toUTF8(cc), pb);
117        nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
118        return makeMarker(FinalMatchUnit, pb.createAnd(markerVar(m), nextPos));
[5812]119    } else {
[5816]120        if (isByteLength(cc)) {
121            if (marker.pos == FinalMatchUnit) {
122                nextPos = pb.createAdvance(nextPos, 1);
123            }
124        } else {
125            nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
126        }
127        unsigned i = 0;
128        while (i < mAlphabets.size() && (a != mAlphabets[i])) i++;
129        if (i == mAlphabets.size()) llvm::report_fatal_error("Alphabet " + a->getName() + " has no CC compiler");
130        return makeMarker(FinalMatchUnit, pb.createAnd(nextPos, mAlphabetCompilers[i]->compileCC(cc, pb)));
[5801]131    }
[5555]132}
133
[4829]134inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
[5638]135    const std::string nameString = name->getName();
136    if (nameString == ".") {
137        return compileAny(marker, pb);
138    } else if (nameString == "^"){
139        return compileStart(marker, pb);
140    } else if (nameString == "$"){
141        return compileEnd(marker, pb);
142    } else if (isUnicodeUnitLength(name)) {
[5080]143        MarkerType nameMarker = compileName(name, pb);
[5812]144        MarkerType nextPos = AdvanceMarker(marker, FinalPostPositionUnit, pb);
[5080]145        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
146        return nameMarker;
[5091]147    } else if (name->getType() == Name::Type::ZeroWidth) {
148        RE * zerowidth = name->getDefinition();
149        MarkerType zero = compile(zerowidth, pb);
150        AlignMarkers(marker, zero, pb);
151        PabloAST * ze = markerVar(zero);
[5787]152        if (nameString == "\\B{g}") {
[5091]153            ze = pb.createNot(ze);
154        }
155        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
156    } else {
[5080]157        return process(name->getDefinition(), marker, pb);
158    }
[4197]159}
[4129]160
[4831]161inline MarkerType RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
[5233]162    MarkerType m;
163    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
164        return m;
[4814]165    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
[5233]166        m = compile(name->getDefinition(), pb);
167        mCompiledName->add(name, m);
[4831]168        return m;
[4486]169    }
[5308]170    UnsupportedRE("Unresolved name " + name->getName());
[4486]171}
172
[4831]173MarkerType RE_Compiler::compileSeq(Seq * seq, MarkerType marker, PabloBuilder & pb) {
[4442]174    // if-hierarchies are not inserted within unbounded repetitions
175    if (mStarDepth > 0) {
176        for (RE * re : *seq) {
177            marker = process(re, marker, pb);
178        }
179        return marker;
[4829]180    } else {
[4831]181        return compileSeqTail(seq->begin(), seq->end(), 0, marker, pb);
[4442]182    }
[4197]183}
[3955]184
[4831]185MarkerType RE_Compiler::compileSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
[5202]186    if (current == end) {
187        return marker;
188    } else if (matchLenSoFar < IfInsertionGap) {
[4442]189        RE * r = *current;
190        marker = process(r, marker, pb);
191        current++;
[4831]192        return compileSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
[4829]193    } else {
[5202]194        Var * m = pb.createVar("m", pb.createZeroes());
[5233]195        NameMap nestedMap(mCompiledName);
196        mCompiledName = &nestedMap;
[4622]197        PabloBuilder nested = PabloBuilder::Create(pb);
[4831]198        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
[5202]199        nested.createAssign(m, markerVar(m1));
200        pb.createIf(markerVar(marker), nested);
[5233]201        mCompiledName = nestedMap.getParent();
[5202]202        return makeMarker(m1.pos, m);
[4442]203    }
204}
205
[5812]206MarkerType RE_Compiler::compileAlt(Alt * alt, const MarkerType base, PabloBuilder & pb) {
[5813]207    std::vector<PabloAST *>  accum(3, pb.createZeroes());
[4340]208    // The following may be useful to force a common Advance rather than separate
209    // Advances in each alternative.
210    for (RE * re : *alt) {
[5233]211        MarkerType m = process(re, base, pb);
[5812]212        const MarkerPosition p = markerPos(m);
[5233]213        accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
[4197]214    }
[5812]215    if (isa<Zeroes>(accum[InitialPostPositionUnit]) && isa<Zeroes>(accum[FinalPostPositionUnit])) {
216        return makeMarker(FinalMatchUnit, accum[FinalMatchUnit]);
[4340]217    }
[5812]218
219    PabloAST * combine = pb.createOr(accum[InitialPostPositionUnit], pb.createAdvance(accum[FinalMatchUnit], 1), "alt");
[5810]220    if (isa<Zeroes>(accum[FinalPostPositionUnit])) {
221        return makeMarker(InitialPostPositionUnit, combine);
222    }
[5812]223    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[FinalPostPositionUnit], "alt");
224    return makeMarker(FinalPostPositionUnit, combine);
[4197]225}
[3955]226
[4831]227MarkerType RE_Compiler::compileAssertion(Assertion * a, MarkerType marker, PabloBuilder & pb) {
[4411]228    RE * asserted = a->getAsserted();
[4408]229    if (a->getKind() == Assertion::Kind::Lookbehind) {
[4411]230        MarkerType lookback = compile(asserted, pb);
[4835]231        AlignMarkers(marker, lookback, pb);
[4438]232        PabloAST * lb = markerVar(lookback);
[4411]233        if (a->getSense() == Assertion::Sense::Negative) {
[4439]234            lb = pb.createNot(lb);
[4408]235        }
[4835]236        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), lb, "lookback"));
[5308]237    } else if (a->getKind() == Assertion::Kind::Boundary) {
238        MarkerType cond = compile(asserted, pb);
[5812]239        if (LLVM_LIKELY(markerPos(cond) == FinalMatchUnit)) {
240            MarkerType postCond = AdvanceMarker(cond, FinalPostPositionUnit, pb);
[5779]241            PabloAST * boundaryCond = pb.createXor(markerVar(cond), markerVar(postCond));
[5308]242            if (a->getSense() == Assertion::Sense::Negative) {
243                boundaryCond = pb.createNot(boundaryCond);
244            }
[5812]245            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
246            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
[5308]247        }
248        else UnsupportedRE("Unsupported boundary assertion");
[4829]249    } else if (isUnicodeUnitLength(asserted)) {
[4411]250        MarkerType lookahead = compile(asserted, pb);
[5812]251        if (LLVM_LIKELY(markerPos(lookahead) == FinalMatchUnit)) {
[4831]252            PabloAST * la = markerVar(lookahead);
253            if (a->getSense() == Assertion::Sense::Negative) {
254                la = pb.createNot(la);
255            }
[5812]256            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
257            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
[4408]258        }
259    }
[5308]260    UnsupportedRE("Unsupported lookahead assertion.");
[4405]261}
262
[4829]263inline bool alignedUnicodeLength(const RE * lh, const RE * rh) {
264    const auto lhl = getUnicodeUnitLengthRange(lh);
265    const auto rhl = getUnicodeUnitLengthRange(rh);
266    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
267}
268
[4831]269MarkerType RE_Compiler::compileDiff(Diff * diff, MarkerType marker, PabloBuilder & pb) {
[4255]270    RE * lh = diff->getLH();
271    RE * rh = diff->getRH();
[4829]272    if (alignedUnicodeLength(lh, rh)) {
[4340]273        MarkerType t1 = process(lh, marker, pb);
274        MarkerType t2 = process(rh, marker, pb);
[4411]275        AlignMarkers(t1, t2, pb);
[4439]276        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
[4255]277    }
[5308]278    UnsupportedRE("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
[4255]279}
280
[4831]281MarkerType RE_Compiler::compileIntersect(Intersect * x, MarkerType marker, PabloBuilder & pb) {
[4298]282    RE * lh = x->getLH();
283    RE * rh = x->getRH();
[4829]284    if (alignedUnicodeLength(lh, rh)) {
[4340]285        MarkerType t1 = process(lh, marker, pb);
286        MarkerType t2 = process(rh, marker, pb);
[4411]287        AlignMarkers(t1, t2, pb);
[4439]288        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
[4298]289    }
[5308]290    UnsupportedRE("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
[4298]291}
292
[4831]293MarkerType RE_Compiler::compileRep(Rep * rep, MarkerType marker, PabloBuilder & pb) {
[4261]294    int lb = rep->getLB();
295    int ub = rep->getUB();
296    if (lb > 0) {
[5555]297        marker = processLowerBound(rep->getRE(), lb, marker, IfInsertionGap, pb);
[4208]298    }
[4261]299    if (ub == Rep::UNBOUNDED_REP) {
[4831]300        marker = processUnboundedRep(rep->getRE(), marker, pb);
301    } else if (lb < ub) {
[5555]302        marker = processBoundedRep(rep->getRE(), ub - lb, marker, IfInsertionGap, pb);
[4261]303    }
[4831]304    return marker;
[4208]305}
306
[4261]307/*
[5720]308   Given a stream |repeated_j| marking positions associated with |j| conecutive matches to an item
309   compute a stream marking |repeat_count| consecutive occurrences of such items.
[4261]310*/
[5720]311   
312PabloAST * RE_Compiler::consecutive_matches(PabloAST * repeated_j, int j, int repeat_count, PabloAST * indexStream, PabloBuilder & pb) {
313    if (j == repeat_count) return repeated_j;
314    int i = std::min(j, repeat_count - j);
315    int k = j + i;
[5724]316    if (/*j > IfInsertionGap*/ false) {
[5720]317        Var * repeated = pb.createVar("repeated", pb.createZeroes());
318        PabloBuilder nested = PabloBuilder::Create(pb);
319        NameMap nestedMap(mCompiledName);
320        mCompiledName = &nestedMap;
321       
322        PabloAST * adv_i = nullptr;
323        if (indexStream == nullptr) adv_i = nested.createAdvance(repeated_j, i);
324        else adv_i = nested.createIndexedAdvance(repeated_j, indexStream, i);
325        PabloAST * repeated_k = nested.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
326        nested.createAssign(repeated, consecutive_matches(repeated_k, k, repeat_count, indexStream, nested));
327        pb.createIf(repeated_j, nested);
328        mCompiledName = nestedMap.getParent();
329        return repeated;
[4841]330    }
[5720]331    else {
332        PabloAST * adv_i = nullptr;
333        if (indexStream == nullptr) adv_i = pb.createAdvance(repeated_j, i);
334        else adv_i = pb.createIndexedAdvance(repeated_j, indexStream, i);
335        PabloAST * repeated_k = pb.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
336        return consecutive_matches(repeated_k, k, repeat_count, indexStream, pb);
[4841]337    }
[4261]338}
[4405]339
[5720]340
[5710]341inline PabloAST * RE_Compiler::reachable(PabloAST * repeated, int length, int repeat_count, PabloAST * indexStream, PabloBuilder & pb) {
[4841]342    int i = length;
343    int total_lgth = repeat_count * length;
344    if (repeat_count == 0) {
345        return repeated;
346    }
[5717]347    PabloAST * reachable = nullptr;
348    if (indexStream == nullptr) reachable = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
349    else reachable = pb.createOr(repeated, pb.createIndexedAdvance(repeated, indexStream, 1), "within1");
[5371]350    while ((i * 2) < total_lgth) {
[5610]351        PabloAST * v = reachable;
[5710]352        PabloAST * v2 = nullptr;
353        if (indexStream == nullptr) v2 = pb.createAdvance(v, i);
354        else v2 = pb.createIndexedAdvance(v, indexStream, i);
[4841]355        i *= 2;
[5610]356        reachable = pb.createOr(v, v2, "within" + std::to_string(i));
[4841]357    }
[5371]358    if (LLVM_LIKELY(i < total_lgth)) {
[5610]359        PabloAST * v = reachable;
[5710]360        PabloAST * v2 = nullptr;
361        if (indexStream == nullptr) v2 = pb.createAdvance(v, total_lgth - i);
362        else v2 = pb.createIndexedAdvance(v, indexStream, total_lgth - i);
[5610]363        reachable = pb.createOr(v, v2, "within" + std::to_string(total_lgth));
[4841]364    }
[5610]365    return reachable;
[4420]366}
367
[5555]368MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, int ifGroupSize, PabloBuilder & pb) {
[5812]369    if (LLVM_UNLIKELY(lb == 0)) {
370        return marker;
371    } else if (LLVM_UNLIKELY(lb == 1)) {
372        return process(repeated, marker, pb);
373    }
[5720]374    //
375    // A bounded repetition with an upper bound of at least 2.
[5786]376    if (!AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
[5720]377        // Check for a regular expression that satisfies on of the special conditions that
378        // allow implementation using the log2 technique.
379        if (isByteLength(repeated)) {
380            PabloAST * cc = markerVar(compile(repeated, pb));
381            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, nullptr, pb);
[5812]382            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
[5720]383            PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), pos);
[5812]384            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
[5720]385        }
[5730]386        else if (isUnicodeUnitLength(repeated)) {
[5720]387            PabloAST * cc = markerVar(compile(repeated, pb));
388            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, mFinal, pb);
[5812]389            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
[5720]390            PabloAST * marker_fwd = pb.createIndexedAdvance(markerVar(marker), mFinal, pos);
[5812]391            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
[5720]392        }
[5730]393        else if (isTypeForLocal(repeated)) {
[5812]394            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
395            if (first) { // if the first symbol is unique, we can use it as an index stream.
396                PabloAST * firstCCstream = markerVar(compile(first, pb));
[5720]397                // Find all matches to the repeated regexp.
[5812]398                PabloAST * submatch = markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb));
[5720]399                // Consecutive submatches require that the symbol following the end of one submatch is the first symbol for
400                // the next submatch.   lb-1 such submatches are required.
401                PabloAST * consecutive_submatch = consecutive_matches(submatch, 1, lb-1, firstCCstream, pb);
402                // Find submatch positions which are lb-2 start symbols forward from the current marker position.
[5812]403                PabloAST * base = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
[5720]404                PabloAST * marker_fwd = pb.createIndexedAdvance(base, firstCCstream, lb - 1);
405                PabloAST * consecutive_lb_1 = pb.createAnd(marker_fwd, consecutive_submatch);
406                // From any of these positions, any position reachable by one more occurrence of the
407                // regexp is a match.
[5812]408                return process(repeated, makeMarker(FinalPostPositionUnit, consecutive_lb_1), pb);
[5720]409            }
410        }
[4340]411    }
[5555]412    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
413    auto group = ifGroupSize < lb ? ifGroupSize : lb;
414    for (auto i = 0; i < group; i++) {
415        marker = process(repeated, marker, pb);
[4340]416    }
[5555]417    if (lb == group) {
[5371]418        return marker;
419    }
[5202]420    Var * m = pb.createVar("m", pb.createZeroes());
[5168]421    PabloBuilder nested = PabloBuilder::Create(pb);
[5593]422    NameMap nestedMap(mCompiledName);
423    mCompiledName = &nestedMap;
[5555]424    MarkerType m1 = processLowerBound(repeated, lb - group, marker, ifGroupSize * 2, nested);
[5202]425    nested.createAssign(m, markerVar(m1));
426    pb.createIf(markerVar(marker), nested);
[5593]427    mCompiledName = nestedMap.getParent();
[5202]428    return makeMarker(m1.pos, m);
[4267]429}
[5168]430   
[5555]431MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  PabloBuilder & pb) {
[5812]432    if (LLVM_UNLIKELY(ub == 0)) {
433        return marker;
434    }
[5720]435    //
436    // A bounded repetition with an upper bound of at least 2.
[5786]437    if (!AlgorithmOptionIsSet(DisableLog2BoundedRepetition) && (ub > 1)) {
[5720]438        // Check for a regular expression that satisfies on of the special conditions that
439        // allow implementation using the log2 technique.
440        if (isByteLength(repeated)) {
441            // log2 upper bound for fixed length (=1) class
442            // Create a mask of positions reachable within ub from current marker.
443            // Use matchstar, then apply filter.
[5812]444            PabloAST * cursor = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
[5720]445            // If we've advanced the cursor to the post position unit, cursor begins on the first masked bit of the bounded mask.
446            // Extend the mask by ub - 1 byte positions to ensure the mask ends on the FinalMatchUnit of the repeated region.
447            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, nullptr, pb);
448            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask);
449            // MatchStar deposits any cursors on the post position. However those cursors may may land on the initial "byte" of a
450            // "multi-byte" character. Combine the masked range with any nonFinals.
451            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
[5813]452            return makeMarker(FinalPostPositionUnit, bounded);
[5720]453        }
[5730]454        else if (isUnicodeUnitLength(repeated)) {
[5720]455            // For a regexp which represent a single Unicode codepoint, we can use the mFinal stream
456            // as an index stream for an indexed advance operation.
[5812]457            PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
[5720]458            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, mFinal, pb);
459            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask, "masked");
460            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
[5812]461            return makeMarker(FinalPostPositionUnit, bounded);
[5720]462        }
[5730]463        else if (isTypeForLocal(repeated)) {
[5812]464            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
465            if (first) { // if the first symbol is unique, we can use it as an index stream.
466                PabloAST * firstCCstream = markerVar(compile(first, pb));
467                PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
[5720]468                PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, firstCCstream, pb);
[5812]469                PabloAST * masked = pb.createAnd(markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb)), upperLimitMask, "masked");
[5720]470                PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
[5812]471                return makeMarker(FinalPostPositionUnit, bounded);
[5720]472            }
473        }
[4340]474    }
[5610]475    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
[5555]476    auto group = ifGroupSize < ub ? ifGroupSize : ub;
477    for (auto i = 0; i < group; i++) {
478        MarkerType a = process(repeated, marker, pb);
479        MarkerType m = marker;
480        AlignMarkers(a, m, pb);
481        marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m)));
[4340]482    }
[5555]483    if (ub == group) {
[5371]484        return marker;
485    }
[5202]486    Var * m1a = pb.createVar("m", pb.createZeroes());
[5168]487    PabloBuilder nested = PabloBuilder::Create(pb);
[5593]488    NameMap nestedMap(mCompiledName);
489    mCompiledName = &nestedMap;
[5555]490    MarkerType m1 = processBoundedRep(repeated, ub - group, marker, ifGroupSize * 2, nested);
[5202]491    nested.createAssign(m1a, markerVar(m1));
492    pb.createIf(markerVar(marker), nested);
[5593]493    mCompiledName = nestedMap.getParent();
[5168]494    return makeMarker(m1.pos, m1a);
[4261]495}
496
[4622]497MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
[4340]498    // always use PostPosition markers for unbounded repetition.
[5813]499    PabloAST * base = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
[5786]500    if (isByteLength(repeated)  && !AlgorithmOptionIsSet(DisableMatchStar)) {
[5610]501        PabloAST * mask = markerVar(compile(repeated, pb));
502        PabloAST * nonFinal = mNonFinal;
503        // The post position character may land on the initial byte of a multi-byte character. Combine them with the masked range.
504        PabloAST * unbounded = pb.createMatchStar(base, pb.createOr(mask, nonFinal), "unbounded");
[5812]505        return makeMarker(FinalPostPositionUnit, unbounded);
[5030]506    } else if (isUnicodeUnitLength(repeated) && !AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar)) {
[4411]507        PabloAST * cc = markerVar(compile(repeated, pb));
[4829]508        PabloAST * mstar = nullptr;
509        PabloAST * nonFinal = mNonFinal;
510        cc = pb.createOr(cc, nonFinal);
[4980]511        mstar = pb.createMatchStar(base, cc);
[4829]512        PabloAST * final = mFinal;
[5812]513        return makeMarker(FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
[4829]514    } else if (mStarDepth > 0){
[5202]515        PabloBuilder * const outer = pb.getParent();
516        Var * starPending = outer->createVar("pending", outer->createZeroes());
517        Var * starAccum = outer->createVar("accum", outer->createZeroes());
[4609]518        mStarDepth++;
519        PabloAST * m1 = pb.createOr(base, starPending);
520        PabloAST * m2 = pb.createOr(base, starAccum);
[5813]521        MarkerType result = process(repeated, makeMarker(InitialPostPositionUnit, m1), pb);
522        result = AdvanceMarker(result, InitialPostPositionUnit, pb);
[4844]523        PabloAST * loopComputation = markerVar(result);
[5202]524        pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
525        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
526        mWhileTest = pb.createOr(mWhileTest, starPending);
527        mStarDepth--;     
528        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
[4829]529    } else {
[5202]530        Var * whileTest = pb.createVar("test", base);
531        Var * whilePending = pb.createVar("pending", base);
532        Var * whileAccum = pb.createVar("accum", base);
[4609]533        mWhileTest = pb.createZeroes();
[4622]534        PabloBuilder wb = PabloBuilder::Create(pb);
[5593]535        NameMap nestedMap(mCompiledName);
536        mCompiledName = &nestedMap;
[4442]537        mStarDepth++;
[5813]538        MarkerType result = process(repeated, makeMarker(InitialPostPositionUnit, whilePending), wb);
539        result = AdvanceMarker(result, InitialPostPositionUnit, wb);
[4844]540        PabloAST * loopComputation = markerVar(result);
[5202]541        wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
542        wb.createAssign(whileAccum, wb.createOr(loopComputation, whileAccum));
543        wb.createAssign(whileTest, wb.createOr(mWhileTest, whilePending));
544        pb.createWhile(whileTest, wb);
[4442]545        mStarDepth--;
[5593]546        mCompiledName = nestedMap.getParent();
[5202]547        return makeMarker(markerPos(result), whileAccum);
[4846]548    }
[4829]549}
550
[5782]551inline MarkerType RE_Compiler::compileStart(MarkerType marker, pablo::PabloBuilder & pb) {
552    PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
[5812]553    MarkerType m = AdvanceMarker(marker, InitialPostPositionUnit, pb);
554    return makeMarker(InitialPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
[4831]555}
556
[5782]557inline MarkerType RE_Compiler::compileEnd(MarkerType marker, pablo::PabloBuilder & pb) {
[5812]558    PabloAST * const nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
559    PabloAST * const atEOL = pb.createOr(pb.createAnd(mLineBreak, nextPos), pb.createAdvance(pb.createAnd(nextPos, mCRLF), 1), "eol");
560    return makeMarker(FinalPostPositionUnit, atEOL);
[4831]561}
562
[4841]563inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
564    if (marker.pos != newpos) {
[5812]565        if (marker.pos == FinalMatchUnit) {
[4841]566            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
[5812]567            marker.pos = InitialPostPositionUnit;
[5810]568        }
[5812]569        if (newpos == FinalPostPositionUnit) {
570            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), mNonFinal, "fpp");
571            marker.pos = FinalPostPositionUnit;
[4841]572        }
[4829]573    }
[4841]574    return marker;
[4829]575}
576
577inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
578    if (m1.pos < m2.pos) {
579        m1 = AdvanceMarker(m1, m2.pos, pb);
580    } else if (m2.pos < m1.pos) {
581        m2 = AdvanceMarker(m2, m1.pos, pb);
582    }
583}
[5308]584   
585LLVM_ATTRIBUTE_NORETURN void RE_Compiler::UnsupportedRE(std::string errmsg) {
586    llvm::report_fatal_error(errmsg);
587}
[4829]588
[5780]589RE_Compiler::RE_Compiler(PabloKernel * kernel, cc::CC_Compiler & ccCompiler)
[5217]590: mKernel(kernel)
[5134]591, mCCCompiler(ccCompiler)
[5042]592, mLineBreak(nullptr)
[4829]593, mCRLF(nullptr)
594, mInitial(nullptr)
595, mNonFinal(nullptr)
596, mFinal(nullptr)
597, mWhileTest(nullptr)
598, mStarDepth(0)
[5233]599, mPB(ccCompiler.getBuilder())
600, mCompiledName(&mBaseMap) {
[5561]601    Var * const linebreak = mKernel->getInputStreamVar("linebreak");
602    mLineBreak = mPB.createExtract(linebreak, mPB.getInteger(0));
[5782]603    Var * const crlf = mKernel->getInputStreamVar("cr+lf");
604    mCRLF = mPB.createExtract(crlf, mPB.getInteger(0));
[5561]605    Var * const required = mKernel->getInputStreamVar("required");
606    mInitial = mPB.createExtract(required, mPB.getInteger(0));
607    mNonFinal = mPB.createExtract(required, mPB.getInteger(1));
608    mFinal = mPB.createExtract(required, mPB.getInteger(2));
[4829]609}
610
[4340]611} // end of namespace re
Note: See TracBrowser for help on using the repository browser.