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

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

Flattening if-hierarchy for bounded repetitions, allowing CCs to pass through to re_compiler

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