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

Last change on this file since 5308 was 5308, checked in by cameron, 2 years ago

Boundary assertions; comment out a bug with RemoveNullableAfterAssertion?

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