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

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

Bug fixes for Carry Manager and issues reported by Fahad

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    mCompiledName = &mBaseMap;
203
204    auto nameMap = resolveNames(re, ZeroWidth);
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->add(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        mCompiledName->add(ZeroWidth, compileName(ZeroWidth, mPB));
222    }
223    return re;
224}
225
226void RE_Compiler::compileUnicodeNames(RE *& re) {
227    re = resolveUnicodeProperties(re);
228}
229
230void RE_Compiler::finalizeMatchResult(MarkerType match_result, bool InvertMatches) {
231    PabloAST * match_follow = mPB.createMatchStar(markerVar(match_result), mAny);
232    if (InvertMatches) {
233        match_follow = mPB.createNot(match_follow);
234    }
235    PabloAST * matches = mPB.createAnd(match_follow, mLineBreak, "matches");
236    if (mCountOnly) {
237        Var * const output = mKernel->addOutput("matchedLineCount", mKernel->getSizeTy());
238        PabloBuilder nestedCount = PabloBuilder::Create(mPB);
239        mPB.createIf(matches, nestedCount);
240        nestedCount.createAssign(output, nestedCount.createCount(matches));
241    } else {
242        Var * const output = mKernel->addOutput("output", mKernel->getStreamSetTy(2));
243        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(0)), matches);
244        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(1)), mLineBreak);
245    }
246}
247
248MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
249    return process(re, makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createOnes()), pb);
250}
251
252MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
253    if (isa<Name>(re)) {
254        return compileName(cast<Name>(re), marker, pb);
255    } else if (isa<Seq>(re)) {
256        return compileSeq(cast<Seq>(re), marker, pb);
257    } else if (isa<Alt>(re)) {
258        return compileAlt(cast<Alt>(re), marker, pb);
259    } else if (isa<Rep>(re)) {
260        return compileRep(cast<Rep>(re), marker, pb);
261    } else if (isa<Assertion>(re)) {
262        return compileAssertion(cast<Assertion>(re), marker, pb);
263    } else if (isa<Any>(re)) {
264        return compileAny(marker, pb);
265    } else if (isa<Diff>(re)) {
266        return compileDiff(cast<Diff>(re), marker, pb);
267    } else if (isa<Intersect>(re)) {
268        return compileIntersect(cast<Intersect>(re), marker, pb);
269    } else if (isa<Start>(re)) {
270        return compileStart(marker, pb);
271    } else if (isa<End>(re)) {
272        return compileEnd(marker, pb);
273    }
274    throw std::runtime_error("RE Compiler failed to process " + Printer_RE::PrintRE(re));
275}
276
277inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
278    PabloAST * nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionUnit, pb));
279    PabloAST * lb = mLineBreak;
280    if (UNICODE_LINE_BREAK) {
281        lb = pb.createOr(mLineBreak, mCRLF);
282    }
283    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(nextFinalByte, pb.createNot(lb), "dot"));
284}
285
286inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
287    if (isUnicodeUnitLength(name)) {
288        MarkerType nameMarker = compileName(name, pb);
289        MarkerType nextPos;
290        if (markerPos(marker) == MarkerPosition::FinalPostPositionUnit) {
291            nextPos = marker;
292        } else {
293            nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
294        }
295        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
296        return nameMarker;
297    } else if (name->getType() == Name::Type::ZeroWidth) {
298        RE * zerowidth = name->getDefinition();
299        MarkerType zero = compile(zerowidth, pb);
300        AlignMarkers(marker, zero, pb);
301        PabloAST * ze = markerVar(zero);
302        const std::string value = name->getName();
303        if (value == "NonGCB") {
304            ze = pb.createNot(ze);
305        }
306        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
307    } else {
308        return process(name->getDefinition(), marker, pb);
309    }
310}
311
312inline MarkerType RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
313    MarkerType m;
314    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
315        return m;
316    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
317        m = compile(name->getDefinition(), pb);
318        mCompiledName->add(name, m);
319        return m;
320    }
321    throw std::runtime_error("Unresolved name " + name->getName());
322}
323
324MarkerType RE_Compiler::compileSeq(Seq * seq, MarkerType marker, PabloBuilder & pb) {
325    // if-hierarchies are not inserted within unbounded repetitions
326    if (mStarDepth > 0) {
327        for (RE * re : *seq) {
328            marker = process(re, marker, pb);
329        }
330        return marker;
331    } else {
332        return compileSeqTail(seq->begin(), seq->end(), 0, marker, pb);
333    }
334}
335
336MarkerType RE_Compiler::compileSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
337    if (current == end) {
338        return marker;
339    } else if (matchLenSoFar < IfInsertionGap) {
340        RE * r = *current;
341        marker = process(r, marker, pb);
342        current++;
343        return compileSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
344    } else {
345        Var * m = pb.createVar("m", pb.createZeroes());
346        NameMap nestedMap(mCompiledName);
347        mCompiledName = &nestedMap;
348        PabloBuilder nested = PabloBuilder::Create(pb);
349        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
350        nested.createAssign(m, markerVar(m1));
351        pb.createIf(markerVar(marker), nested);
352        mCompiledName = nestedMap.getParent();
353        return makeMarker(m1.pos, m);
354    }
355}
356
357MarkerType RE_Compiler::compileAlt(Alt * alt, MarkerType marker, PabloBuilder & pb) {
358    std::vector<PabloAST *>  accum(3, pb.createZeroes());
359    MarkerType const base = marker;
360    // The following may be useful to force a common Advance rather than separate
361    // Advances in each alternative.
362    for (RE * re : *alt) {
363        MarkerType m = process(re, base, pb);
364        MarkerPosition p = markerPos(m);
365        accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
366    }
367    if (isa<Zeroes>(accum[MarkerPosition::FinalPostPositionUnit])) {
368        return makeMarker(MarkerPosition::FinalMatchUnit, accum[MarkerPosition::FinalMatchUnit]);
369    }
370    PabloAST * combine = pb.createAdvance(accum[MarkerPosition::FinalMatchUnit], 1);
371    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[MarkerPosition::FinalPostPositionUnit], "alt");
372    return makeMarker(MarkerPosition::FinalPostPositionUnit, combine);
373}
374
375MarkerType RE_Compiler::compileAssertion(Assertion * a, MarkerType marker, PabloBuilder & pb) {
376    RE * asserted = a->getAsserted();
377    if (a->getKind() == Assertion::Kind::Lookbehind) {
378        MarkerType lookback = compile(asserted, pb);
379        AlignMarkers(marker, lookback, pb);
380        PabloAST * lb = markerVar(lookback);
381        if (a->getSense() == Assertion::Sense::Negative) {
382            lb = pb.createNot(lb);
383        }
384        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), lb, "lookback"));
385    } else if (isUnicodeUnitLength(asserted)) {
386        MarkerType lookahead = compile(asserted, pb);
387        if (LLVM_LIKELY(markerPos(lookahead) == MarkerPosition::FinalMatchUnit)) {
388            PabloAST * la = markerVar(lookahead);
389            if (a->getSense() == Assertion::Sense::Negative) {
390                la = pb.createNot(la);
391            }
392            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
393            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
394        }
395    }
396    throw std::runtime_error("Unsupported lookahead assertion.");
397}
398
399inline bool alignedUnicodeLength(const RE * lh, const RE * rh) {
400    const auto lhl = getUnicodeUnitLengthRange(lh);
401    const auto rhl = getUnicodeUnitLengthRange(rh);
402    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
403}
404
405MarkerType RE_Compiler::compileDiff(Diff * diff, MarkerType marker, PabloBuilder & pb) {
406    RE * lh = diff->getLH();
407    RE * rh = diff->getRH();
408    if (alignedUnicodeLength(lh, rh)) {
409        MarkerType t1 = process(lh, marker, pb);
410        MarkerType t2 = process(rh, marker, pb);
411        AlignMarkers(t1, t2, pb);
412        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
413    }
414    throw std::runtime_error("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
415}
416
417MarkerType RE_Compiler::compileIntersect(Intersect * x, MarkerType marker, PabloBuilder & pb) {
418    RE * lh = x->getLH();
419    RE * rh = x->getRH();
420    if (alignedUnicodeLength(lh, rh)) {
421        MarkerType t1 = process(lh, marker, pb);
422        MarkerType t2 = process(rh, marker, pb);
423        AlignMarkers(t1, t2, pb);
424        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
425    }
426    throw std::runtime_error("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
427}
428
429MarkerType RE_Compiler::compileRep(Rep * rep, MarkerType marker, PabloBuilder & pb) {
430    int lb = rep->getLB();
431    int ub = rep->getUB();
432    if (lb > 0) {
433        marker = processLowerBound(rep->getRE(), lb, marker, pb);
434    }
435    if (ub == Rep::UNBOUNDED_REP) {
436        marker = processUnboundedRep(rep->getRE(), marker, pb);
437    } else if (lb < ub) {
438        marker = processBoundedRep(rep->getRE(), ub - lb, marker, pb);
439    }
440    return marker;
441}
442
443/*
444   Given a stream |repeated| marking positions associated with matches to an item
445   of length |repeated_lgth|, compute a stream marking |repeat_count| consecutive
446   occurrences of such items.
447*/
448
449inline PabloAST * RE_Compiler::consecutive_matches(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
450    int i = length;
451    int total = repeat_count * length;
452    PabloAST * consecutive_i = repeated;
453    while (i * 2 < total) {
454        PabloAST * v = consecutive_i;
455        PabloAST * v2 =  pb.createAdvance(v, i);
456        i *= 2;
457        consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "of" + std::to_string(total));
458    }
459    if (i < total) {
460        PabloAST * v = consecutive_i;
461        consecutive_i = pb.createAnd(v, pb.createAdvance(v, total - i), "at" + std::to_string(total));
462    }
463    return consecutive_i;
464}
465
466inline PabloAST * RE_Compiler::reachable(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
467    int i = length;
468    int total_lgth = repeat_count * length;
469    if (repeat_count == 0) {
470        return repeated;
471    }
472    PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
473    while (i * 2 < total_lgth) {
474        PabloAST * v = reachable_i;
475        PabloAST * v2 =  pb.createAdvance(v, i);
476        i *= 2;
477        reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
478    }
479    if (i < total_lgth) {
480        PabloAST * v = reachable_i;
481        reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
482    }
483    return reachable_i;
484}
485
486MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, PabloBuilder & pb) {
487    if (lb == 0) return marker;
488    if (!mGraphemeBoundaryRule && isByteLength(repeated) && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
489        PabloAST * cc = markerVar(compile(repeated, pb));
490        PabloAST * cc_lb = consecutive_matches(cc, 1, lb, pb);
491        PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1);
492        return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
493    }
494    // Fall through to general case.  Process the first item and insert the rest into an if-structure.   
495    marker = process(repeated, marker, pb);
496    if (mGraphemeBoundaryRule) {
497        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
498    }
499    if (lb == 1) return marker;
500    Var * m = pb.createVar("m", pb.createZeroes());
501    PabloBuilder nested = PabloBuilder::Create(pb);
502    MarkerType m1 = processLowerBound(repeated, lb - 1, marker, nested);
503    nested.createAssign(m, markerVar(m1));
504    pb.createIf(markerVar(marker), nested);
505    return makeMarker(m1.pos, m);
506}
507   
508MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, PabloBuilder & pb) {
509    if (ub == 0) return marker;
510    if (!mGraphemeBoundaryRule && isByteLength(repeated) && ub > 1 && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
511        // log2 upper bound for fixed length (=1) class
512        // Create a mask of positions reachable within ub from current marker.
513        // Use matchstar, then apply filter.
514        PabloAST * match = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
515        PabloAST * upperLimitMask = reachable(match, 1, ub, pb);
516        PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
517        PabloAST * rep_class_var = markerVar(compile(repeated, pb));
518        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(pb.createMatchStar(cursor, rep_class_var), upperLimitMask, "bounded"));
519    }
520    // Fall through to general case.  Process the first item and insert the rest into an if-structure.   
521    MarkerType a = process(repeated, marker, pb);
522    MarkerType m = marker;
523    AlignMarkers(a, m, pb);
524    marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m)));
525    if (mGraphemeBoundaryRule) {
526        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
527    }
528    if (ub == 1) return marker;
529    Var * m1a = pb.createVar("m", pb.createZeroes());
530    PabloBuilder nested = PabloBuilder::Create(pb);
531    MarkerType m1 = processBoundedRep(repeated, ub - 1, marker, nested);
532    nested.createAssign(m1a, markerVar(m1));
533    pb.createIf(markerVar(marker), nested);
534    return makeMarker(m1.pos, m1a);
535}
536
537MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
538    // always use PostPosition markers for unbounded repetition.
539    PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
540    if (!mGraphemeBoundaryRule && isByteLength(repeated)  && !AlgorithmOptionIsSet(DisableMatchStar)) {
541        PabloAST * cc = markerVar(compile(repeated, pb));
542        PabloAST * mstar = nullptr;
543        mstar = pb.createMatchStar(base, cc, "unbounded");
544        return makeMarker(MarkerPosition::FinalPostPositionUnit, mstar);
545    } else if (isUnicodeUnitLength(repeated) && !AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar)) {
546        PabloAST * cc = markerVar(compile(repeated, pb));
547        PabloAST * mstar = nullptr;
548        PabloAST * nonFinal = mNonFinal;
549        if (mGraphemeBoundaryRule) {
550            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
551        }
552        cc = pb.createOr(cc, nonFinal);
553        mstar = pb.createMatchStar(base, cc);
554        PabloAST * final = mFinal;
555        if (mGraphemeBoundaryRule) {
556            final = mGraphemeBoundaryRule;
557        }
558        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
559    } else if (mStarDepth > 0){
560        PabloBuilder * const outer = pb.getParent();
561        Var * starPending = outer->createVar("pending", outer->createZeroes());
562        Var * starAccum = outer->createVar("accum", outer->createZeroes());
563        mStarDepth++;
564        PabloAST * m1 = pb.createOr(base, starPending);
565        PabloAST * m2 = pb.createOr(base, starAccum);
566        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, m1), pb);
567        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, pb);
568        PabloAST * loopComputation = markerVar(result);
569        pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
570        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
571        mWhileTest = pb.createOr(mWhileTest, starPending);
572        mStarDepth--;     
573        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
574    } else {
575        Var * whileTest = pb.createVar("test", base);
576        Var * whilePending = pb.createVar("pending", base);
577        Var * whileAccum = pb.createVar("accum", base);
578        mWhileTest = pb.createZeroes();
579        PabloBuilder wb = PabloBuilder::Create(pb);
580        mStarDepth++;
581        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, whilePending), wb);
582        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, wb);
583        PabloAST * loopComputation = markerVar(result);
584        wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
585        wb.createAssign(whileAccum, wb.createOr(loopComputation, whileAccum));
586        wb.createAssign(whileTest, wb.createOr(mWhileTest, whilePending));
587        pb.createWhile(whileTest, wb);
588        mStarDepth--;
589        return makeMarker(markerPos(result), whileAccum);
590    }
591}
592
593inline MarkerType RE_Compiler::compileStart(const MarkerType marker, pablo::PabloBuilder & pb) {
594    MarkerType m = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
595    if (UNICODE_LINE_BREAK) {
596        PabloAST * line_end = mPB.createOr(mLineBreak, mCRLF);
597        PabloAST * sol_init = pb.createNot(pb.createOr(pb.createAdvance(pb.createNot(line_end), 1), mCRLF));
598        PabloAST * sol = pb.createScanThru(pb.createAnd(mInitial, sol_init), mNonFinal);
599        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
600    } else {
601        PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
602        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
603    }
604}
605
606inline MarkerType RE_Compiler::compileEnd(const MarkerType marker, pablo::PabloBuilder & pb) {
607    PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
608    return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(nextPos, mLineBreak, "eol"));
609}
610
611inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
612    if (marker.pos != newpos) {
613        if (marker.pos == MarkerPosition::FinalMatchUnit) {
614            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
615            PabloAST * nonFinal = mNonFinal;
616            if (mGraphemeBoundaryRule) {
617                nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
618            }
619            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), nonFinal, "fpp");
620            marker.pos = MarkerPosition::FinalPostPositionUnit;
621        }
622    }
623    return marker;
624}
625
626inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
627    if (m1.pos < m2.pos) {
628        m1 = AdvanceMarker(m1, m2.pos, pb);
629    } else if (m2.pos < m1.pos) {
630        m2 = AdvanceMarker(m2, m1.pos, pb);
631    }
632}
633
634RE_Compiler::RE_Compiler(PabloKernel * kernel, cc::CC_Compiler & ccCompiler, bool CountOnly)
635: mKernel(kernel)
636, mCountOnly(CountOnly)
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.