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

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

More 32-bit fixes.

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