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

Last change on this file since 5782 was 5782, checked in by nmedfort, 17 months ago

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

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