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

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

Re compiler fixes for raw CCs

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