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

Last change on this file since 5646 was 5646, checked in by nmedfort, 19 months ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

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