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

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

Modified memory alignment mechanism for GetPropertyValueGrepString? + misc. changes.

File size: 28.7 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#include <assert.h>
29#include <stdexcept>
30#include <iostream>
31#include <pablo/printer_pablos.h>
32#include "llvm/Support/CommandLine.h"
33#include <sstream>
34#include <unordered_set>
35
36
37#define UNICODE_LINE_BREAK (!AlgorithmOptionIsSet(DisableUnicodeLineBreak))
38
39using namespace pablo;
40
41namespace re {
42
43void RE_Compiler::initializeRequiredStreams(const unsigned encodingBits) {
44    if (encodingBits == 8) {
45      RE_Compiler::initializeRequiredStreams_utf8();
46    }
47    else if (encodingBits == 16) {
48      RE_Compiler::initializeRequiredStreams_utf16();
49    }
50}
51
52void RE_Compiler::initializeRequiredStreams_utf16() {
53
54
55
56    PabloAST * LF = mCCCompiler.compileCC("LF", makeCC(0x000A), mPB);
57    PabloAST * CR = mCCCompiler.compileCC("CR", makeCC(0x000D), mPB);
58    PabloAST * LF_VT_FF_CR = mCCCompiler.compileCC(makeCC(0x000A, 0x000D));
59    PabloAST * NEL = mCCCompiler.compileCC("NEL", makeCC(0x0085), mPB);
60    PabloAST * LS_PS = mCCCompiler.compileCC("LS_PS", makeCC(0x2028, 0x2029), mPB);
61    PabloAST * NEL_LS_PS = mPB.createOr(NEL, LS_PS, "NEL_LS_PS");
62
63    PabloAST * cr1 = mPB.createAdvance(CR, 1, "cr1");
64    mCRLF = mPB.createAnd(cr1, LF, "crlf");
65
66    PabloAST * hi_surrogate = mCCCompiler.compileCC(makeCC(0xD800, 0xDBFF));
67    //PabloAST * lo_surrogate = mCCCompiler.compileCC(makeCC(0xDC00, 0xDFFF));
68    PabloAST * u16hi_hi_surrogate = mCCCompiler.compileCC(makeCC(0xD800, 0xDB00));    //u16hi_hi_surrogate = [\xD8-\xDB]
69    PabloAST * u16hi_lo_surrogate = mCCCompiler.compileCC(makeCC(0xDC00, 0xDF00));    //u16hi_lo_surrogate = [\xDC-\xDF]
70
71    PabloAST * invalidTemp = mPB.createAdvance(u16hi_hi_surrogate, 1, "InvalidTemp");
72    PabloAST * u16invalid = mPB.createXor(invalidTemp, u16hi_lo_surrogate, "u16invalid");
73    // errors.Unicode=pablo.Advance(u16hi_hi_surrogate) ^ u16hi_lo_surrogate
74    PabloAST * u16valid = mPB.createNot(u16invalid, "u16valid");
75
76    PabloAST * u16single_temp = mPB.createOr(mCCCompiler.compileCC(makeCC(0x0000, 0xD7FF)), mCCCompiler.compileCC(makeCC(0xE000, 0xFFFF)));
77    PabloAST * u16single = mPB.createAnd(u16single_temp, mPB.createNot(u16invalid));
78   
79    mNonFinal = mPB.createAnd(hi_surrogate, u16valid, "nonfinal");
80    mFinal = mPB.createNot(mPB.createOr(mNonFinal, u16invalid), "final");
81    mInitial = mPB.createOr(u16single, hi_surrogate, "initial");
82   
83    PabloAST * LB_chars = mPB.createOr(LF_VT_FF_CR, NEL_LS_PS);
84    PabloAST * UnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
85    PabloAST * lb = UNICODE_LINE_BREAK ? UnicodeLineBreak : LF;
86    PabloAST * unterminatedLineAtEOF = mPB.createAtEOF(mPB.createAdvance(mPB.createNot(LB_chars), 1));
87    mLineBreak = mPB.createOr(lb, unterminatedLineAtEOF);
88    mAny = mPB.createNot(lb, "any");
89}
90void RE_Compiler::initializeRequiredStreams_utf8() {
91    PabloAST * LF = mCCCompiler.compileCC("LF", makeCC(0x0A), mPB);
92    PabloAST * CR = mCCCompiler.compileCC(makeCC(0x0D));
93    PabloAST * LF_VT_FF_CR = mCCCompiler.compileCC(makeCC(0x0A, 0x0D));
94
95    Zeroes * const zero = mPB.createZeroes();
96    Var * crlf = mPB.createVar("crlf", zero);
97    PabloBuilder crb = PabloBuilder::Create(mPB);
98    PabloAST * cr1 = crb.createAdvance(CR, 1, "cr1");
99    crb.createAssign(crlf, crb.createAnd(cr1, LF));
100    mPB.createIf(CR, crb);
101
102    mCRLF = crlf;
103
104    Var * u8invalid = mPB.createVar("u8invalid", zero);
105    Var * valid_pfx = mPB.createVar("valid_pfx", zero);
106    Var * nonFinal = mPB.createVar("nonfinal", zero);
107    Var * NEL_LS_PS = mPB.createVar("NEL_LS_PS", zero);
108
109    PabloAST * u8pfx = mCCCompiler.compileCC(makeCC(0xC0, 0xFF));
110    PabloBuilder it = PabloBuilder::Create(mPB);
111    mPB.createIf(u8pfx, it);
112
113    mNonFinal = nonFinal;
114
115    PabloAST * u8pfx2 = mCCCompiler.compileCC(makeCC(0xC2, 0xDF), it);
116    PabloAST * u8pfx3 = mCCCompiler.compileCC(makeCC(0xE0, 0xEF), it);
117    PabloAST * u8pfx4 = mCCCompiler.compileCC(makeCC(0xF0, 0xF4), it);
118    PabloAST * u8suffix = mCCCompiler.compileCC("u8suffix", makeCC(0x80, 0xBF), it);
119
120    //
121    // Two-byte sequences
122    Var * u8scope22 = it.createVar("u8scope22", zero);
123    Var * NEL = it.createVar("NEL", zero);
124    PabloBuilder it2 = PabloBuilder::Create(it);
125    it2.createAssign(u8scope22, it2.createAdvance(u8pfx2, 1));
126    it2.createAssign(NEL, it2.createAnd(it2.createAdvance(mCCCompiler.compileCC(makeCC(0xC2), it2), 1), mCCCompiler.compileCC(makeCC(0x85), it2)));
127    it.createIf(u8pfx2, it2);
128
129    //
130    // Three-byte sequences
131    Var * u8scope32 = it.createVar("u8scope32", zero);
132    Var * u8scope3X = it.createVar("u8scope3X", zero);
133    Var * LS_PS = it.createVar("LS_PS", zero);
134    Var * EX_invalid = it.createVar("EX_invalid", zero);
135
136    PabloBuilder it3 = PabloBuilder::Create(it);
137    it.createIf(u8pfx3, it3);
138
139    it3.createAssign(u8scope32, it3.createAdvance(u8pfx3, 1));
140    PabloAST * u8scope33 = it3.createAdvance(u8pfx3, 2);
141    it3.createAssign(u8scope3X, it3.createOr(u8scope32, u8scope33));
142    PabloAST * E2_80 = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE2), it3), 1), mCCCompiler.compileCC(makeCC(0x80), it3));
143    it3.createAssign(LS_PS, it3.createAnd(it3.createAdvance(E2_80, 1), mCCCompiler.compileCC(makeCC(0xA8,0xA9), it3)));
144    PabloAST * E0_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE0), it3), 1), mCCCompiler.compileCC(makeCC(0x80, 0x9F), it3));
145    PabloAST * ED_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xED), it3), 1), mCCCompiler.compileCC(makeCC(0xA0, 0xBF), it3));
146    it3.createAssign(EX_invalid, it3.createOr(E0_invalid, ED_invalid));
147
148    it.createAssign(NEL_LS_PS, it.createOr(NEL, LS_PS));
149
150    //
151    // Four-byte sequences
152    Var * u8scope4nonfinal = it.createVar("u8scope4nonfinal", zero);
153    Var * u8scope4X = it.createVar("u8scope4X", zero);
154    Var * FX_invalid = it.createVar("FX_invalid", zero);
155    PabloBuilder it4 = PabloBuilder::Create(it);
156    it.createIf(u8pfx4, it4);
157    PabloAST * u8scope42 = it4.createAdvance(u8pfx4, 1, "u8scope42");
158    PabloAST * u8scope43 = it4.createAdvance(u8scope42, 1, "u8scope43");
159    PabloAST * u8scope44 = it4.createAdvance(u8scope43, 1, "u8scope44");
160    it4.createAssign(u8scope4nonfinal, it4.createOr(u8scope42, u8scope43));
161    it4.createAssign(u8scope4X, it4.createOr(u8scope4nonfinal, u8scope44));
162    PabloAST * F0_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF0), it4), 1), mCCCompiler.compileCC(makeCC(0x80, 0x8F), it4));
163    PabloAST * F4_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF4), it4), 1), mCCCompiler.compileCC(makeCC(0x90, 0xBF), it4));
164    it4.createAssign(FX_invalid, it4.createOr(F0_invalid, F4_invalid));
165
166    //
167    // Invalid cases
168    PabloAST * anyscope = it.createOr(u8scope22, it.createOr(u8scope3X, u8scope4X));
169    PabloAST * legalpfx = it.createOr(it.createOr(u8pfx2, u8pfx3), u8pfx4);
170    //  Any scope that does not have a suffix byte, and any suffix byte that is not in
171    //  a scope is a mismatch, i.e., invalid UTF-8.
172    PabloAST * mismatch = it.createXor(anyscope, u8suffix);
173    //
174    PabloAST * EF_invalid = it.createOr(EX_invalid, FX_invalid);
175    PabloAST * pfx_invalid = it.createXor(u8pfx, legalpfx);
176    it.createAssign(u8invalid, it.createOr(pfx_invalid, it.createOr(mismatch, EF_invalid)));
177    PabloAST * u8valid = it.createNot(u8invalid, "u8valid");
178    //
179    //
180
181    it.createAssign(valid_pfx, it.createAnd(u8pfx, u8valid));
182    it.createAssign(mNonFinal, it.createAnd(it.createOr(it.createOr(u8pfx, u8scope32), u8scope4nonfinal), u8valid));
183
184
185    PabloAST * LB_chars = mPB.createOr(LF_VT_FF_CR, NEL_LS_PS);
186    PabloAST * u8single = mPB.createAnd(mCCCompiler.compileCC(makeCC(0x00, 0x7F)), mPB.createNot(u8invalid));
187    mInitial = mPB.createOr(u8single, valid_pfx, "initial");
188    mFinal = mPB.createNot(mPB.createOr(mNonFinal, u8invalid), "final");
189    PabloAST * UnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
190    PabloAST * lb = UNICODE_LINE_BREAK ? UnicodeLineBreak : LF;
191    PabloAST * unterminatedLineAtEOF = mPB.createAtEOF(mPB.createAdvance(mPB.createNot(LB_chars), 1));
192    mLineBreak = mPB.createOr(lb, unterminatedLineAtEOF);
193    mAny = mPB.createNot(lb, "any");
194}
195
196
197RE * RE_Compiler::resolveUnicodeProperties(RE * re) {
198    Name * ZeroWidth = nullptr;
199    mCompiledName = &mBaseMap;
200
201    auto nameMap = resolveNames(re, ZeroWidth);
202    if (LLVM_LIKELY(nameMap.size() > 0)) {
203        UCD::UCDCompiler ucdCompiler(mCCCompiler);
204        if (LLVM_UNLIKELY(AlgorithmOptionIsSet(DisableIfHierarchy))) {
205            ucdCompiler.generateWithoutIfHierarchy(nameMap, mPB);
206        } else {
207            ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
208        }
209        for (auto t : nameMap) {
210            if (t.second) {
211                mCompiledName->add(t.first, makeMarker(MarkerPosition::FinalMatchUnit, mPB.createAnd(t.second, mAny)));
212            }
213        }
214    }
215
216    // Now precompile any grapheme segmentation rules
217    if (ZeroWidth) {
218        mCompiledName->add(ZeroWidth, compileName(ZeroWidth, mPB));
219    }
220    return re;
221}
222
223void RE_Compiler::compileUnicodeNames(RE *& re) {
224    re = resolveUnicodeProperties(re);
225}
226
227void RE_Compiler::finalizeMatchResult(MarkerType match_result, bool InvertMatches) {
228    PabloAST * match_follow = mPB.createMatchStar(markerVar(match_result), mAny);
229    if (InvertMatches) {
230        match_follow = mPB.createNot(match_follow);
231    }
232    PabloAST * matches = mPB.createAnd(match_follow, mLineBreak, "matches");
233    if (mCountOnly) {
234        Var * const output = mKernel->addOutput("matchedLineCount", mKernel->getSizeTy());
235        PabloBuilder nestedCount = PabloBuilder::Create(mPB);
236        mPB.createIf(matches, nestedCount);
237        nestedCount.createAssign(output, nestedCount.createCount(matches));
238    } else {
239        Var * const output = mKernel->addOutput("output", mKernel->getStreamSetTy(2));
240        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(0)), matches);
241        mPB.createAssign(mPB.createExtract(output, mPB.getInteger(1)), mLineBreak);
242    }
243}
244
245MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
246    return process(re, makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createOnes()), pb);
247}
248
249MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
250    if (isa<Name>(re)) {
251        return compileName(cast<Name>(re), marker, pb);
252    } else if (isa<Seq>(re)) {
253        return compileSeq(cast<Seq>(re), marker, pb);
254    } else if (isa<Alt>(re)) {
255        return compileAlt(cast<Alt>(re), marker, pb);
256    } else if (isa<Rep>(re)) {
257        return compileRep(cast<Rep>(re), marker, pb);
258    } else if (isa<Assertion>(re)) {
259        return compileAssertion(cast<Assertion>(re), marker, pb);
260    } else if (isa<Any>(re)) {
261        return compileAny(marker, pb);
262    } else if (isa<Diff>(re)) {
263        return compileDiff(cast<Diff>(re), marker, pb);
264    } else if (isa<Intersect>(re)) {
265        return compileIntersect(cast<Intersect>(re), marker, pb);
266    } else if (isa<Start>(re)) {
267        return compileStart(marker, pb);
268    } else if (isa<End>(re)) {
269        return compileEnd(marker, pb);
270    }
271    throw std::runtime_error("RE Compiler failed to process " + Printer_RE::PrintRE(re));
272}
273
274inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
275    PabloAST * nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionUnit, pb));
276    PabloAST * lb = mLineBreak;
277    if (UNICODE_LINE_BREAK) {
278        lb = pb.createOr(mLineBreak, mCRLF);
279    }
280    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(nextFinalByte, pb.createNot(lb), "dot"));
281}
282
283inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
284    if (isUnicodeUnitLength(name)) {
285        MarkerType nameMarker = compileName(name, pb);
286        MarkerType nextPos;
287        if (markerPos(marker) == MarkerPosition::FinalPostPositionUnit) {
288            nextPos = marker;
289        } else {
290            nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
291        }
292        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
293        return nameMarker;
294    } else if (name->getType() == Name::Type::ZeroWidth) {
295        RE * zerowidth = name->getDefinition();
296        MarkerType zero = compile(zerowidth, pb);
297        AlignMarkers(marker, zero, pb);
298        PabloAST * ze = markerVar(zero);
299        const std::string value = name->getName();
300        if (value == "NonGCB") {
301            ze = pb.createNot(ze);
302        }
303        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
304    } else {
305        return process(name->getDefinition(), marker, pb);
306    }
307}
308
309inline MarkerType RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
310    MarkerType m;
311    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
312        return m;
313    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
314        m = compile(name->getDefinition(), pb);
315        mCompiledName->add(name, m);
316        return m;
317    }
318    throw std::runtime_error("Unresolved name " + name->getName());
319}
320
321MarkerType RE_Compiler::compileSeq(Seq * seq, MarkerType marker, PabloBuilder & pb) {
322    // if-hierarchies are not inserted within unbounded repetitions
323    if (mStarDepth > 0) {
324        for (RE * re : *seq) {
325            marker = process(re, marker, pb);
326        }
327        return marker;
328    } else {
329        return compileSeqTail(seq->begin(), seq->end(), 0, marker, pb);
330    }
331}
332
333MarkerType RE_Compiler::compileSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
334    if (current == end) {
335        return marker;
336    } else if (matchLenSoFar < IfInsertionGap) {
337        RE * r = *current;
338        marker = process(r, marker, pb);
339        current++;
340        return compileSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
341    } else {
342        Var * m = pb.createVar("m", pb.createZeroes());
343        NameMap nestedMap(mCompiledName);
344        mCompiledName = &nestedMap;
345        PabloBuilder nested = PabloBuilder::Create(pb);
346        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
347        nested.createAssign(m, markerVar(m1));
348        pb.createIf(markerVar(marker), nested);
349        mCompiledName = nestedMap.getParent();
350        return makeMarker(m1.pos, m);
351    }
352}
353
354MarkerType RE_Compiler::compileAlt(Alt * alt, MarkerType marker, PabloBuilder & pb) {
355    std::vector<PabloAST *>  accum(3, 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 m = process(re, base, pb);
361        MarkerPosition p = markerPos(m);
362        accum[p] = pb.createOr(accum[p], markerVar(m), "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(PabloKernel * kernel, cc::CC_Compiler & ccCompiler, bool CountOnly)
632: mKernel(kernel)
633, mCountOnly(CountOnly)
634, mCCCompiler(ccCompiler)
635, mLineBreak(nullptr)
636, mCRLF(nullptr)
637, mAny(nullptr)
638, mGraphemeBoundaryRule(nullptr)
639, mInitial(nullptr)
640, mNonFinal(nullptr)
641, mFinal(nullptr)
642, mWhileTest(nullptr)
643, mStarDepth(0)
644, mPB(ccCompiler.getBuilder())
645, mCompiledName(&mBaseMap) {
646
647}
648
649} // end of namespace re
Note: See TracBrowser for help on using the repository browser.