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

Last change on this file since 5217 was 5217, checked in by nmedfort, 3 years ago

Merged PabloFunction? and PabloKernel? classes. Updated projects where necessary.

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