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

Last change on this file since 5083 was 5083, checked in by xuedongx, 3 years ago

separate module for resolve names

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