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

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

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

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