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

Last change on this file since 5842 was 5842, checked in by cameron, 15 months ago

Decoupling PabloKernels? from CC_compiler

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