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

Last change on this file since 5888 was 5888, checked in by cameron, 14 months ago

Allow RE compilers to be associated with any Pablo block, not just kernel entry

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