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

Last change on this file since 5801 was 5801, checked in by cameron, 22 months ago

Additional Alphabet analysis and transformation

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