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

Last change on this file since 5706 was 5706, checked in by nmedfort, 18 months ago

First stage of MultiBlockKernel? and pipeline restructuring

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