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

Last change on this file since 5617 was 5617, checked in by xuedongx, 20 months ago

new RE compiler pipeline for local language(enlightened by Glushkov automaton)

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