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

Last change on this file since 5310 was 5310, checked in by nmedfort, 2 years ago

Adjusted pablo compiler to use getInputStream and getOutputStream when accessing packed stream fields.

File size: 30.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_rep.h>              // for Rep, Rep::::UNBOUNDED_REP
25#include <re/re_seq.h>              // for Seq
26#include <re/re_start.h>
27#include <re/re_toolchain.h>        // for AlgorithmOptionIsSet, RE_Algorith...
28#include "cc/cc_compiler.h"         // for CC_Compiler
29#include "pablo/builder.hpp"        // for PabloBuilder
30namespace pablo { class PabloAST; }
31namespace pablo { class PabloKernel; }
32namespace re { class Alt; }
33namespace re { class RE; }
34
35
36#define UNICODE_LINE_BREAK (!AlgorithmOptionIsSet(DisableUnicodeLineBreak))
37
38using namespace pablo;
39using namespace llvm;
40
41namespace re {
42
43void RE_Compiler::initializeRequiredStreams(const unsigned encodingBits) {
44    if (encodingBits == 8) {
45        RE_Compiler::initializeRequiredStreams_utf8();
46    } else if (encodingBits == 16) {
47        RE_Compiler::initializeRequiredStreams_utf16();
48    }
49}
50
51void RE_Compiler::initializeRequiredStreams_utf16() {
52    PabloAST * LF = mCCCompiler.compileCC("LF", makeCC(0x000A), mPB);
53    PabloAST * CR = mCCCompiler.compileCC("CR", makeCC(0x000D), mPB);
54    PabloAST * LF_VT_FF_CR = mCCCompiler.compileCC(makeCC(0x000A, 0x000D));
55    PabloAST * NEL = mCCCompiler.compileCC("NEL", makeCC(0x0085), mPB);
56    PabloAST * LS_PS = mCCCompiler.compileCC("LS_PS", makeCC(0x2028, 0x2029), mPB);
57    PabloAST * NEL_LS_PS = mPB.createOr(NEL, LS_PS, "NEL_LS_PS");
58
59    PabloAST * cr1 = mPB.createAdvance(CR, 1, "cr1");
60    mCRLF = mPB.createAnd(cr1, LF, "crlf");
61
62    PabloAST * hi_surrogate = mCCCompiler.compileCC(makeCC(0xD800, 0xDBFF));
63    //PabloAST * lo_surrogate = mCCCompiler.compileCC(makeCC(0xDC00, 0xDFFF));
64    PabloAST * u16hi_hi_surrogate = mCCCompiler.compileCC(makeCC(0xD800, 0xDB00));    //u16hi_hi_surrogate = [\xD8-\xDB]
65    PabloAST * u16hi_lo_surrogate = mCCCompiler.compileCC(makeCC(0xDC00, 0xDF00));    //u16hi_lo_surrogate = [\xDC-\xDF]
66
67    PabloAST * invalidTemp = mPB.createAdvance(u16hi_hi_surrogate, 1, "InvalidTemp");
68    PabloAST * u16invalid = mPB.createXor(invalidTemp, u16hi_lo_surrogate, "u16invalid");
69    // errors.Unicode=pablo.Advance(u16hi_hi_surrogate) ^ u16hi_lo_surrogate
70    PabloAST * u16valid = mPB.createNot(u16invalid, "u16valid");
71
72    PabloAST * u16single_temp = mPB.createOr(mCCCompiler.compileCC(makeCC(0x0000, 0xD7FF)), mCCCompiler.compileCC(makeCC(0xE000, 0xFFFF)));
73    PabloAST * u16single = mPB.createAnd(u16single_temp, mPB.createNot(u16invalid));
74   
75    mNonFinal = mPB.createAnd(hi_surrogate, u16valid, "nonfinal");
76    mFinal = mPB.createNot(mPB.createOr(mNonFinal, u16invalid), "final");
77    mInitial = mPB.createOr(u16single, hi_surrogate, "initial");
78   
79    PabloAST * LB_chars = mPB.createOr(LF_VT_FF_CR, NEL_LS_PS);
80    PabloAST * UnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
81    PabloAST * lb = UNICODE_LINE_BREAK ? UnicodeLineBreak : LF;
82    PabloAST * unterminatedLineAtEOF = mPB.createAtEOF(mPB.createAdvance(mPB.createNot(LB_chars), 1));
83    mLineBreak = mPB.createOr(lb, unterminatedLineAtEOF);
84    mAny = mPB.createNot(lb, "any");
85}
86void RE_Compiler::initializeRequiredStreams_utf8() {
87    PabloAST * LF = mCCCompiler.compileCC("LF", makeCC(0x0A), mPB);
88    PabloAST * CR = mCCCompiler.compileCC(makeCC(0x0D));
89    PabloAST * LF_VT_FF_CR = mCCCompiler.compileCC(makeCC(0x0A, 0x0D));
90
91    Zeroes * const zero = mPB.createZeroes();
92    Var * crlf = mPB.createVar("crlf", zero);
93    PabloBuilder crb = PabloBuilder::Create(mPB);
94    PabloAST * cr1 = crb.createAdvance(CR, 1, "cr1");
95    crb.createAssign(crlf, crb.createAnd(cr1, LF));
96    mPB.createIf(CR, crb);
97
98    mCRLF = crlf;
99
100    Var * u8invalid = mPB.createVar("u8invalid", zero);
101    Var * valid_pfx = mPB.createVar("valid_pfx", zero);
102    Var * nonFinal = mPB.createVar("nonfinal", zero);
103    Var * NEL_LS_PS = mPB.createVar("NEL_LS_PS", zero);
104
105    PabloAST * u8pfx = mCCCompiler.compileCC(makeCC(0xC0, 0xFF));
106    PabloBuilder it = PabloBuilder::Create(mPB);
107    mPB.createIf(u8pfx, it);
108
109    mNonFinal = nonFinal;
110
111    PabloAST * u8pfx2 = mCCCompiler.compileCC(makeCC(0xC2, 0xDF), it);
112    PabloAST * u8pfx3 = mCCCompiler.compileCC(makeCC(0xE0, 0xEF), it);
113    PabloAST * u8pfx4 = mCCCompiler.compileCC(makeCC(0xF0, 0xF4), it);
114    PabloAST * u8suffix = mCCCompiler.compileCC("u8suffix", makeCC(0x80, 0xBF), it);
115
116    //
117    // Two-byte sequences
118    Var * u8scope22 = it.createVar("u8scope22", zero);
119    Var * NEL = it.createVar("NEL", zero);
120    PabloBuilder it2 = PabloBuilder::Create(it);
121    it2.createAssign(u8scope22, it2.createAdvance(u8pfx2, 1));
122    it2.createAssign(NEL, it2.createAnd(it2.createAdvance(mCCCompiler.compileCC(makeCC(0xC2), it2), 1), mCCCompiler.compileCC(makeCC(0x85), it2)));
123    it.createIf(u8pfx2, it2);
124
125    //
126    // Three-byte sequences
127    Var * u8scope32 = it.createVar("u8scope32", zero);
128    Var * u8scope3X = it.createVar("u8scope3X", zero);
129    Var * LS_PS = it.createVar("LS_PS", zero);
130    Var * EX_invalid = it.createVar("EX_invalid", zero);
131
132    PabloBuilder it3 = PabloBuilder::Create(it);
133    it.createIf(u8pfx3, it3);
134
135    it3.createAssign(u8scope32, it3.createAdvance(u8pfx3, 1));
136    PabloAST * u8scope33 = it3.createAdvance(u8pfx3, 2);
137    it3.createAssign(u8scope3X, it3.createOr(u8scope32, u8scope33));
138    PabloAST * E2_80 = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE2), it3), 1), mCCCompiler.compileCC(makeCC(0x80), it3));
139    it3.createAssign(LS_PS, it3.createAnd(it3.createAdvance(E2_80, 1), mCCCompiler.compileCC(makeCC(0xA8,0xA9), it3)));
140    PabloAST * E0_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE0), it3), 1), mCCCompiler.compileCC(makeCC(0x80, 0x9F), it3));
141    PabloAST * ED_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xED), it3), 1), mCCCompiler.compileCC(makeCC(0xA0, 0xBF), it3));
142    it3.createAssign(EX_invalid, it3.createOr(E0_invalid, ED_invalid));
143
144    it.createAssign(NEL_LS_PS, it.createOr(NEL, LS_PS));
145
146    //
147    // Four-byte sequences
148    Var * u8scope4nonfinal = it.createVar("u8scope4nonfinal", zero);
149    Var * u8scope4X = it.createVar("u8scope4X", zero);
150    Var * FX_invalid = it.createVar("FX_invalid", zero);
151    PabloBuilder it4 = PabloBuilder::Create(it);
152    it.createIf(u8pfx4, it4);
153    PabloAST * u8scope42 = it4.createAdvance(u8pfx4, 1, "u8scope42");
154    PabloAST * u8scope43 = it4.createAdvance(u8scope42, 1, "u8scope43");
155    PabloAST * u8scope44 = it4.createAdvance(u8scope43, 1, "u8scope44");
156    it4.createAssign(u8scope4nonfinal, it4.createOr(u8scope42, u8scope43));
157    it4.createAssign(u8scope4X, it4.createOr(u8scope4nonfinal, u8scope44));
158    PabloAST * F0_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF0), it4), 1), mCCCompiler.compileCC(makeCC(0x80, 0x8F), it4));
159    PabloAST * F4_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF4), it4), 1), mCCCompiler.compileCC(makeCC(0x90, 0xBF), it4));
160    it4.createAssign(FX_invalid, it4.createOr(F0_invalid, F4_invalid));
161
162    //
163    // Invalid cases
164    PabloAST * anyscope = it.createOr(u8scope22, it.createOr(u8scope3X, u8scope4X));
165    PabloAST * legalpfx = it.createOr(it.createOr(u8pfx2, u8pfx3), u8pfx4);
166    //  Any scope that does not have a suffix byte, and any suffix byte that is not in
167    //  a scope is a mismatch, i.e., invalid UTF-8.
168    PabloAST * mismatch = it.createXor(anyscope, u8suffix);
169    //
170    PabloAST * EF_invalid = it.createOr(EX_invalid, FX_invalid);
171    PabloAST * pfx_invalid = it.createXor(u8pfx, legalpfx);
172    it.createAssign(u8invalid, it.createOr(pfx_invalid, it.createOr(mismatch, EF_invalid)));
173    PabloAST * u8valid = it.createNot(u8invalid, "u8valid");
174    //
175    //
176
177    it.createAssign(valid_pfx, it.createAnd(u8pfx, u8valid));
178    it.createAssign(mNonFinal, it.createAnd(it.createOr(it.createOr(u8pfx, u8scope32), u8scope4nonfinal), u8valid));
179
180
181    PabloAST * LB_chars = mPB.createOr(LF_VT_FF_CR, NEL_LS_PS);
182    PabloAST * u8single = mPB.createAnd(mCCCompiler.compileCC(makeCC(0x00, 0x7F)), mPB.createNot(u8invalid));
183    mInitial = mPB.createOr(u8single, valid_pfx, "initial");
184    mFinal = mPB.createNot(mPB.createOr(mNonFinal, u8invalid), "final");
185    PabloAST * UnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
186    PabloAST * lb = UNICODE_LINE_BREAK ? UnicodeLineBreak : LF;
187    PabloAST * unterminatedLineAtEOF = mPB.createAtEOF(mPB.createAdvance(mPB.createNot(LB_chars), 1));
188    mLineBreak = mPB.createOr(lb, unterminatedLineAtEOF);
189    mAny = mPB.createNot(lb, "any");
190}
191
192
193RE * RE_Compiler::resolveUnicodeProperties(RE * re) {
194    Name * ZeroWidth = nullptr;
195    mCompiledName = &mBaseMap;
196
197    auto nameMap = resolveNames(re, ZeroWidth);
198    if (LLVM_LIKELY(nameMap.size() > 0)) {
199        UCD::UCDCompiler ucdCompiler(mCCCompiler);
200        if (LLVM_UNLIKELY(AlgorithmOptionIsSet(DisableIfHierarchy))) {
201            ucdCompiler.generateWithoutIfHierarchy(nameMap, mPB);
202        } else {
203            ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
204        }
205        for (auto t : nameMap) {
206            if (t.second) {
207                mCompiledName->add(t.first, makeMarker(MarkerPosition::FinalMatchUnit, mPB.createAnd(t.second, mAny)));
208            }
209        }
210    }
211
212    // Now precompile any grapheme segmentation rules
213    if (ZeroWidth) {
214        mCompiledName->add(ZeroWidth, compileName(ZeroWidth, mPB));
215    }
216    return re;
217}
218
219void RE_Compiler::compileUnicodeNames(RE *& re) {
220    re = resolveUnicodeProperties(re);
221}
222
223void RE_Compiler::finalizeMatchResult(MarkerType match_result, bool InvertMatches) {
224    PabloAST * match_follow = mPB.createMatchStar(markerVar(match_result), mAny);
225    if (InvertMatches) {
226        match_follow = mPB.createNot(match_follow);
227    }
228    PabloAST * matches = mPB.createAnd(match_follow, mLineBreak, "matches");
229    if (mCountOnly) {
230        Var * const output = mKernel->addOutput("matchedLineCount", mKernel->getSizeTy());
231        PabloBuilder nestedCount = PabloBuilder::Create(mPB);
232        mPB.createIf(matches, nestedCount);
233        nestedCount.createAssign(output, nestedCount.createCount(matches));
234    } else {
235        Var * const output = mKernel->addOutput("output", mKernel->getStreamSetTy(2));
236        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(0)), matches);
237        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(1)), mLineBreak);
238    }
239}
240
241MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
242    return process(re, makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createOnes()), pb);
243}
244
245MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
246    if (isa<Name>(re)) {
247        return compileName(cast<Name>(re), marker, pb);
248    } else if (isa<Seq>(re)) {
249        return compileSeq(cast<Seq>(re), marker, pb);
250    } else if (isa<Alt>(re)) {
251        return compileAlt(cast<Alt>(re), marker, pb);
252    } else if (isa<Rep>(re)) {
253        return compileRep(cast<Rep>(re), marker, pb);
254    } else if (isa<Assertion>(re)) {
255        return compileAssertion(cast<Assertion>(re), marker, pb);
256    } else if (isa<Any>(re)) {
257        return compileAny(marker, pb);
258    } else if (isa<Diff>(re)) {
259        return compileDiff(cast<Diff>(re), marker, pb);
260    } else if (isa<Intersect>(re)) {
261        return compileIntersect(cast<Intersect>(re), marker, pb);
262    } else if (isa<Start>(re)) {
263        return compileStart(marker, pb);
264    } else if (isa<End>(re)) {
265        return compileEnd(marker, pb);
266    }
267    UnsupportedRE("RE Compiler failed to process " + Printer_RE::PrintRE(re));
268}
269
270inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
271    PabloAST * nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionUnit, pb));
272    PabloAST * lb = mLineBreak;
273    if (UNICODE_LINE_BREAK) {
274        lb = pb.createOr(mLineBreak, mCRLF);
275    }
276    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(nextFinalByte, pb.createNot(lb), "dot"));
277}
278
279inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
280    if (isUnicodeUnitLength(name)) {
281        MarkerType nameMarker = compileName(name, pb);
282        MarkerType nextPos;
283        if (markerPos(marker) == MarkerPosition::FinalPostPositionUnit) {
284            nextPos = marker;
285        } else {
286            nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
287        }
288        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
289        return nameMarker;
290    } else if (name->getType() == Name::Type::ZeroWidth) {
291        RE * zerowidth = name->getDefinition();
292        MarkerType zero = compile(zerowidth, pb);
293        AlignMarkers(marker, zero, pb);
294        PabloAST * ze = markerVar(zero);
295        const std::string value = name->getName();
296        if (value == "NonGCB") {
297            ze = pb.createNot(ze);
298        }
299        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
300    } else {
301        return process(name->getDefinition(), marker, pb);
302    }
303}
304
305inline MarkerType RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
306    MarkerType m;
307    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
308        return m;
309    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
310        m = compile(name->getDefinition(), pb);
311        mCompiledName->add(name, m);
312        return m;
313    }
314    UnsupportedRE("Unresolved name " + name->getName());
315}
316
317MarkerType RE_Compiler::compileSeq(Seq * seq, MarkerType marker, PabloBuilder & pb) {
318    // if-hierarchies are not inserted within unbounded repetitions
319    if (mStarDepth > 0) {
320        for (RE * re : *seq) {
321            marker = process(re, marker, pb);
322        }
323        return marker;
324    } else {
325        return compileSeqTail(seq->begin(), seq->end(), 0, marker, pb);
326    }
327}
328
329MarkerType RE_Compiler::compileSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
330    if (current == end) {
331        return marker;
332    } else if (matchLenSoFar < IfInsertionGap) {
333        RE * r = *current;
334        marker = process(r, marker, pb);
335        current++;
336        return compileSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
337    } else {
338        Var * m = pb.createVar("m", pb.createZeroes());
339        NameMap nestedMap(mCompiledName);
340        mCompiledName = &nestedMap;
341        PabloBuilder nested = PabloBuilder::Create(pb);
342        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
343        nested.createAssign(m, markerVar(m1));
344        pb.createIf(markerVar(marker), nested);
345        mCompiledName = nestedMap.getParent();
346        return makeMarker(m1.pos, m);
347    }
348}
349
350MarkerType RE_Compiler::compileAlt(Alt * alt, MarkerType marker, PabloBuilder & pb) {
351    std::vector<PabloAST *>  accum(3, pb.createZeroes());
352    MarkerType const base = marker;
353    // The following may be useful to force a common Advance rather than separate
354    // Advances in each alternative.
355    for (RE * re : *alt) {
356        MarkerType m = process(re, base, pb);
357        MarkerPosition p = markerPos(m);
358        accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
359    }
360    if (isa<Zeroes>(accum[MarkerPosition::FinalPostPositionUnit])) {
361        return makeMarker(MarkerPosition::FinalMatchUnit, accum[MarkerPosition::FinalMatchUnit]);
362    }
363    PabloAST * combine = pb.createAdvance(accum[MarkerPosition::FinalMatchUnit], 1);
364    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[MarkerPosition::FinalPostPositionUnit], "alt");
365    return makeMarker(MarkerPosition::FinalPostPositionUnit, combine);
366}
367
368MarkerType RE_Compiler::compileAssertion(Assertion * a, MarkerType marker, PabloBuilder & pb) {
369    RE * asserted = a->getAsserted();
370    if (a->getKind() == Assertion::Kind::Lookbehind) {
371        MarkerType lookback = compile(asserted, pb);
372        AlignMarkers(marker, lookback, pb);
373        PabloAST * lb = markerVar(lookback);
374        if (a->getSense() == Assertion::Sense::Negative) {
375            lb = pb.createNot(lb);
376        }
377        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), lb, "lookback"));
378    } else if (a->getKind() == Assertion::Kind::Boundary) {
379        MarkerType cond = compile(asserted, pb);
380        if (LLVM_LIKELY(markerPos(cond) == MarkerPosition::FinalMatchUnit)) {
381            MarkerType postCond = AdvanceMarker(cond, MarkerPosition::FinalPostPositionUnit, pb);
382            PabloAST * boundaryCond = pb.createAnd(mAny, pb.createXor(markerVar(cond), markerVar(postCond)));
383            if (a->getSense() == Assertion::Sense::Negative) {
384                boundaryCond = pb.createNot(boundaryCond);
385            }
386            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
387            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
388        }
389        else UnsupportedRE("Unsupported boundary assertion");
390    } else if (isUnicodeUnitLength(asserted)) {
391        MarkerType lookahead = compile(asserted, pb);
392        if (LLVM_LIKELY(markerPos(lookahead) == MarkerPosition::FinalMatchUnit)) {
393            PabloAST * la = markerVar(lookahead);
394            if (a->getSense() == Assertion::Sense::Negative) {
395                la = pb.createNot(la);
396            }
397            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
398            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
399        }
400    }
401    UnsupportedRE("Unsupported lookahead assertion.");
402}
403
404inline bool alignedUnicodeLength(const RE * lh, const RE * rh) {
405    const auto lhl = getUnicodeUnitLengthRange(lh);
406    const auto rhl = getUnicodeUnitLengthRange(rh);
407    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
408}
409
410MarkerType RE_Compiler::compileDiff(Diff * diff, MarkerType marker, PabloBuilder & pb) {
411    RE * lh = diff->getLH();
412    RE * rh = diff->getRH();
413    if (alignedUnicodeLength(lh, rh)) {
414        MarkerType t1 = process(lh, marker, pb);
415        MarkerType t2 = process(rh, marker, pb);
416        AlignMarkers(t1, t2, pb);
417        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
418    }
419    UnsupportedRE("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
420}
421
422MarkerType RE_Compiler::compileIntersect(Intersect * x, MarkerType marker, PabloBuilder & pb) {
423    RE * lh = x->getLH();
424    RE * rh = x->getRH();
425    if (alignedUnicodeLength(lh, rh)) {
426        MarkerType t1 = process(lh, marker, pb);
427        MarkerType t2 = process(rh, marker, pb);
428        AlignMarkers(t1, t2, pb);
429        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
430    }
431    UnsupportedRE("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
432}
433
434MarkerType RE_Compiler::compileRep(Rep * rep, MarkerType marker, PabloBuilder & pb) {
435    int lb = rep->getLB();
436    int ub = rep->getUB();
437    if (lb > 0) {
438        marker = processLowerBound(rep->getRE(), lb, marker, pb);
439    }
440    if (ub == Rep::UNBOUNDED_REP) {
441        marker = processUnboundedRep(rep->getRE(), marker, pb);
442    } else if (lb < ub) {
443        marker = processBoundedRep(rep->getRE(), ub - lb, marker, pb);
444    }
445    return marker;
446}
447
448/*
449   Given a stream |repeated| marking positions associated with matches to an item
450   of length |repeated_lgth|, compute a stream marking |repeat_count| consecutive
451   occurrences of such items.
452*/
453
454inline PabloAST * RE_Compiler::consecutive_matches(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
455    int i = length;
456    int total = repeat_count * length;
457    PabloAST * consecutive_i = repeated;
458    while (i * 2 < total) {
459        PabloAST * v = consecutive_i;
460        PabloAST * v2 =  pb.createAdvance(v, i);
461        i *= 2;
462        consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "of" + std::to_string(total));
463    }
464    if (i < total) {
465        PabloAST * v = consecutive_i;
466        consecutive_i = pb.createAnd(v, pb.createAdvance(v, total - i), "at" + std::to_string(total));
467    }
468    return consecutive_i;
469}
470
471inline PabloAST * RE_Compiler::reachable(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
472    int i = length;
473    int total_lgth = repeat_count * length;
474    if (repeat_count == 0) {
475        return repeated;
476    }
477    PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
478    while (i * 2 < total_lgth) {
479        PabloAST * v = reachable_i;
480        PabloAST * v2 =  pb.createAdvance(v, i);
481        i *= 2;
482        reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
483    }
484    if (i < total_lgth) {
485        PabloAST * v = reachable_i;
486        reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
487    }
488    return reachable_i;
489}
490
491MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, PabloBuilder & pb) {
492    if (lb == 0) return marker;
493    if (!mGraphemeBoundaryRule && isByteLength(repeated) && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
494        PabloAST * cc = markerVar(compile(repeated, pb));
495        PabloAST * cc_lb = consecutive_matches(cc, 1, lb, pb);
496        PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1);
497        return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
498    }
499    // Fall through to general case.  Process the first item and insert the rest into an if-structure.   
500    marker = process(repeated, marker, pb);
501    if (mGraphemeBoundaryRule) {
502        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
503    }
504    if (lb == 1) return marker;
505    Var * m = pb.createVar("m", pb.createZeroes());
506    PabloBuilder nested = PabloBuilder::Create(pb);
507    MarkerType m1 = processLowerBound(repeated, lb - 1, marker, nested);
508    nested.createAssign(m, markerVar(m1));
509    pb.createIf(markerVar(marker), nested);
510    return makeMarker(m1.pos, m);
511}
512   
513MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, PabloBuilder & pb) {
514    if (ub == 0) return marker;
515    if (!mGraphemeBoundaryRule && isByteLength(repeated) && ub > 1 && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
516        // log2 upper bound for fixed length (=1) class
517        // Create a mask of positions reachable within ub from current marker.
518        // Use matchstar, then apply filter.
519        PabloAST * match = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
520        PabloAST * upperLimitMask = reachable(match, 1, ub, pb);
521        PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
522        PabloAST * rep_class_var = markerVar(compile(repeated, pb));
523        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(pb.createMatchStar(cursor, rep_class_var), upperLimitMask, "bounded"));
524    }
525    // Fall through to general case.  Process the first item and insert the rest into an if-structure.   
526    MarkerType a = process(repeated, marker, pb);
527    MarkerType m = marker;
528    AlignMarkers(a, m, pb);
529    marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m)));
530    if (mGraphemeBoundaryRule) {
531        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
532    }
533    if (ub == 1) return marker;
534    Var * m1a = pb.createVar("m", pb.createZeroes());
535    PabloBuilder nested = PabloBuilder::Create(pb);
536    MarkerType m1 = processBoundedRep(repeated, ub - 1, marker, nested);
537    nested.createAssign(m1a, markerVar(m1));
538    pb.createIf(markerVar(marker), nested);
539    return makeMarker(m1.pos, m1a);
540}
541
542MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
543    // always use PostPosition markers for unbounded repetition.
544    PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
545    if (!mGraphemeBoundaryRule && isByteLength(repeated)  && !AlgorithmOptionIsSet(DisableMatchStar)) {
546        PabloAST * cc = markerVar(compile(repeated, pb));
547        PabloAST * mstar = nullptr;
548        mstar = pb.createMatchStar(base, cc, "unbounded");
549        return makeMarker(MarkerPosition::FinalPostPositionUnit, mstar);
550    } else if (isUnicodeUnitLength(repeated) && !AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar)) {
551        PabloAST * cc = markerVar(compile(repeated, pb));
552        PabloAST * mstar = nullptr;
553        PabloAST * nonFinal = mNonFinal;
554        if (mGraphemeBoundaryRule) {
555            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
556        }
557        cc = pb.createOr(cc, nonFinal);
558        mstar = pb.createMatchStar(base, cc);
559        PabloAST * final = mFinal;
560        if (mGraphemeBoundaryRule) {
561            final = mGraphemeBoundaryRule;
562        }
563        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
564    } else if (mStarDepth > 0){
565        PabloBuilder * const outer = pb.getParent();
566        Var * starPending = outer->createVar("pending", outer->createZeroes());
567        Var * starAccum = outer->createVar("accum", outer->createZeroes());
568        mStarDepth++;
569        PabloAST * m1 = pb.createOr(base, starPending);
570        PabloAST * m2 = pb.createOr(base, starAccum);
571        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, m1), pb);
572        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, pb);
573        PabloAST * loopComputation = markerVar(result);
574        pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
575        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
576        mWhileTest = pb.createOr(mWhileTest, starPending);
577        mStarDepth--;     
578        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
579    } else {
580        Var * whileTest = pb.createVar("test", base);
581        Var * whilePending = pb.createVar("pending", base);
582        Var * whileAccum = pb.createVar("accum", base);
583        mWhileTest = pb.createZeroes();
584        PabloBuilder wb = PabloBuilder::Create(pb);
585        mStarDepth++;
586        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, whilePending), wb);
587        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, wb);
588        PabloAST * loopComputation = markerVar(result);
589        wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
590        wb.createAssign(whileAccum, wb.createOr(loopComputation, whileAccum));
591        wb.createAssign(whileTest, wb.createOr(mWhileTest, whilePending));
592        pb.createWhile(whileTest, wb);
593        mStarDepth--;
594        return makeMarker(markerPos(result), whileAccum);
595    }
596}
597
598inline MarkerType RE_Compiler::compileStart(const MarkerType marker, pablo::PabloBuilder & pb) {
599    MarkerType m = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
600    if (UNICODE_LINE_BREAK) {
601        PabloAST * line_end = mPB.createOr(mLineBreak, mCRLF);
602        PabloAST * sol_init = pb.createNot(pb.createOr(pb.createAdvance(pb.createNot(line_end), 1), mCRLF));
603        PabloAST * sol = pb.createScanThru(pb.createAnd(mInitial, sol_init), mNonFinal);
604        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
605    } else {
606        PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
607        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
608    }
609}
610
611inline MarkerType RE_Compiler::compileEnd(const MarkerType marker, pablo::PabloBuilder & pb) {
612    PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
613    return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(nextPos, mLineBreak, "eol"));
614}
615
616inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
617    if (marker.pos != newpos) {
618        if (marker.pos == MarkerPosition::FinalMatchUnit) {
619            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
620            PabloAST * nonFinal = mNonFinal;
621            if (mGraphemeBoundaryRule) {
622                nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
623            }
624            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), nonFinal, "fpp");
625            marker.pos = MarkerPosition::FinalPostPositionUnit;
626        }
627    }
628    return marker;
629}
630
631inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
632    if (m1.pos < m2.pos) {
633        m1 = AdvanceMarker(m1, m2.pos, pb);
634    } else if (m2.pos < m1.pos) {
635        m2 = AdvanceMarker(m2, m1.pos, pb);
636    }
637}
638   
639LLVM_ATTRIBUTE_NORETURN void RE_Compiler::UnsupportedRE(std::string errmsg) {
640    llvm::report_fatal_error(errmsg);
641}
642   
643   
644
645RE_Compiler::RE_Compiler(PabloKernel * kernel, cc::CC_Compiler & ccCompiler, bool CountOnly)
646: mKernel(kernel)
647, mCountOnly(CountOnly)
648, mCCCompiler(ccCompiler)
649, mLineBreak(nullptr)
650, mCRLF(nullptr)
651, mAny(nullptr)
652, mGraphemeBoundaryRule(nullptr)
653, mInitial(nullptr)
654, mNonFinal(nullptr)
655, mFinal(nullptr)
656, mWhileTest(nullptr)
657, mStarDepth(0)
658, mPB(ccCompiler.getBuilder())
659, mCompiledName(&mBaseMap) {
660
661}
662
663} // end of namespace re
Note: See TracBrowser for help on using the repository browser.