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

Last change on this file since 5610 was 5610, checked in by nmedfort, 21 months ago

Bug fix for bounded/unbounded repetitions.

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