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

Last change on this file was 5730, checked in by cameron, 10 days ago

Generic indexed advance

File size: 32.1 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
7
8
9#include "re_compiler.h"
10#include <pablo/pe_ones.h>          // for Ones
11#include <pablo/pe_var.h>           // for Var
12#include <pablo/pe_zeroes.h>        // for Zeroes
13#include <re/printer_re.h>
14#include <re/re_alt.h>
15#include <re/re_analysis.h>         // for isByteLength, isUnicodeUnitLength
16#include <re/re_any.h>
17#include <re/re_assertion.h>        // for Assertion, Assertion::Sense, Asse...
18#include <re/re_cc.h>               // for makeCC
19#include <re/re_diff.h>             // for Diff
20#include <re/re_end.h>
21#include <re/re_intersect.h>        // for Intersect
22#include <re/re_name.h>             // for Name, Name::Type, Name::Type::Zer...
23#include <re/re_name_resolve.h>     // for resolveNames
24#include <re/re_name_gather.h>      // for gatherNames
25#include <re/re_rep.h>              // for Rep, Rep::::UNBOUNDED_REP
26#include <re/re_seq.h>              // for Seq
27#include <re/re_start.h>
28#include <re/re_local.h>
29#include <re/re_toolchain.h>        // for AlgorithmOptionIsSet, RE_Algorith...
30#include "cc/cc_compiler.h"         // for CC_Compiler
31#include "pablo/builder.hpp"        // for PabloBuilder
32#include "toolchain/toolchain.h"    // for AVX2_available
33#include <llvm/Support/ErrorHandling.h>
34
35namespace pablo { class PabloAST; }
36namespace pablo { class PabloKernel; }
37namespace re { class Alt; }
38namespace re { class RE; }
39
40
41#define UNICODE_LINE_BREAK (!AlgorithmOptionIsSet(DisableUnicodeLineBreak))
42
43using namespace pablo;
44using namespace llvm;
45
46namespace re {
47
48RE * RE_Compiler::resolveUnicodeProperties(RE * re) {
49    Name * ZeroWidth = nullptr;
50    mCompiledName = &mBaseMap;
51    gatherNames(re, ZeroWidth);
52    // Now precompile any grapheme segmentation rules
53    if (ZeroWidth) {
54        mCompiledName->add(ZeroWidth, compileName(ZeroWidth, mPB));
55    }
56    return re;
57}
58
59RE * RE_Compiler::compileUnicodeNames(RE * re) {
60    return resolveUnicodeProperties(re);
61}
62
63PabloAST * RE_Compiler::compile(RE * re) {
64    return markerVar(AdvanceMarker(compile(re, mPB), MarkerPosition::FinalPostPositionUnit, mPB));
65}
66   
67MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
68    return process(re, makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createOnes()), pb);
69}
70   
71MarkerType RE_Compiler::compile_local(RE * re, MarkerType marker, PabloBuilder & pb) {
72    CC * first = RE_Local::first(re);
73    CC * final = RE_Local::final(re);
74
75    if (first == nullptr || final == nullptr) {
76        mLocal = false;
77        return process(re, marker, pb);
78    }
79
80    PabloAST * pablo_first = mCCCompiler.compileCC(first);
81    PabloAST * pablo_final = mCCCompiler.compileCC(final);
82    std::map<CC*, CC*> follow_map;
83    RE_Local::follow(re, follow_map);
84
85    PabloAST * pablo_follow = pb.createZeroes();
86    for (auto i = follow_map.begin(); i != follow_map.end(); i++) {
87        CC * one = makeCC(std::move(*i->first));
88        CC * two = makeCC(std::move(*i->second));
89        PabloAST * pablo_one = pb.createAnd(mCCCompiler.compileCC(one), mAny);
90        PabloAST * pablo_two = pb.createAnd(mCCCompiler.compileCC(two), mAny);
91        PabloAST * one1 = pb.createAdvance(pablo_one, 1, "one1");
92        PabloAST * follow = pb.createAnd(pb.createScanThru(pb.createAnd(mInitial, one1), mNonFinal), pablo_two);
93        pablo_follow = pb.createOr(pablo_follow, follow);
94    }
95    PabloAST * result = pb.createAnd(pb.createMatchStar(pb.createAdvance(pablo_first, 1),
96                                                        pb.createOr(pablo_follow, mNonFinal)),
97                                     pb.createAdvance(pablo_final, 1));
98    return makeMarker(MarkerPosition::FinalPostPositionUnit, result);
99}
100
101   
102MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
103    if (mLocal) {
104        if (isa<Name>(re) || isa<Seq>(re) || isa<Alt>(re) || isa<Rep>(re) || isa<CC>(re)) {
105            return compile_local(re, marker, pb);
106        } else if (isa<Any>(re)) {
107            return compileAny(marker, pb);
108        } else if (isa<Diff>(re)) {
109            return compileDiff(cast<Diff>(re), marker, pb);
110        } else if (isa<Intersect>(re)) {
111            return compileIntersect(cast<Intersect>(re), marker, pb);
112        } else {
113            UnsupportedRE("RE Compiler for local language failed to process " + Printer_RE::PrintRE(re));
114        }
115    } else {
116        if (isa<Name>(re)) {
117            return compileName(cast<Name>(re), marker, pb);
118        } else if (isa<Seq>(re)) {
119            return compileSeq(cast<Seq>(re), marker, pb);
120        } else if (isa<Alt>(re)) {
121            return compileAlt(cast<Alt>(re), marker, pb);
122        } else if (isa<Rep>(re)) {
123            return compileRep(cast<Rep>(re), marker, pb);
124        } else if (isa<Assertion>(re)) {
125            return compileAssertion(cast<Assertion>(re), marker, pb);
126        } else if (isa<Any>(re)) {
127            return compileAny(marker, pb);
128        } else if (isa<Diff>(re)) {
129            return compileDiff(cast<Diff>(re), marker, pb);
130        } else if (isa<Intersect>(re)) {
131            return compileIntersect(cast<Intersect>(re), marker, pb);
132        } else if (isa<Start>(re)) {
133            return compileStart(marker, pb);
134        } else if (isa<End>(re)) {
135            return compileEnd(marker, pb);
136        } else if (isa<CC>(re)) {
137            // CCs may be passed through the toolchain directly to the compiler.
138            return compileCC(cast<CC>(re), marker, pb);
139        } else {
140            UnsupportedRE("RE Compiler failed to process " + Printer_RE::PrintRE(re));
141        }
142    }
143}
144
145inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
146    PabloAST * nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionUnit, pb));
147    PabloAST * lb = mLineBreak;
148    if (UNICODE_LINE_BREAK) {
149        lb = pb.createOr(mLineBreak, mCRLF);
150    }
151    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(nextFinalByte, pb.createNot(lb), "dot"));
152}
153
154MarkerType RE_Compiler::compileCC(CC * cc, MarkerType marker, PabloBuilder & pb) {
155    MarkerType nextPos;
156    if (markerPos(marker) == MarkerPosition::FinalPostPositionUnit) {
157        nextPos = marker;
158    } else {
159        nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
160    }
161    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(markerVar(marker), pb.createAnd(mCCCompiler.compileCC(cc, pb), mAny)));
162}
163
164inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
165    const std::string nameString = name->getName();
166    if (nameString == ".") {
167        return compileAny(marker, pb);
168    } else if (nameString == "^"){
169        return compileStart(marker, pb);
170    } else if (nameString == "$"){
171        return compileEnd(marker, pb);
172    } else if (isUnicodeUnitLength(name)) {
173        MarkerType nameMarker = compileName(name, pb);
174        MarkerType nextPos;
175        if (markerPos(marker) == MarkerPosition::FinalPostPositionUnit) {
176            nextPos = marker;
177        } else {
178            nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
179        }
180        nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
181        return nameMarker;
182    } else if (name->getType() == Name::Type::ZeroWidth) {
183        RE * zerowidth = name->getDefinition();
184        MarkerType zero = compile(zerowidth, pb);
185        AlignMarkers(marker, zero, pb);
186        PabloAST * ze = markerVar(zero);
187        if (nameString == "NonGCB") {
188            ze = pb.createNot(ze);
189        }
190        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), ze, "zerowidth"));
191    } else {
192        return process(name->getDefinition(), marker, pb);
193    }
194}
195
196inline MarkerType RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
197    MarkerType m;
198    if (LLVM_LIKELY(mCompiledName->get(name, m))) {
199        return m;
200    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
201        m = compile(name->getDefinition(), pb);
202        mCompiledName->add(name, m);
203        return m;
204    }
205    UnsupportedRE("Unresolved name " + name->getName());
206}
207
208MarkerType RE_Compiler::compileSeq(Seq * seq, MarkerType marker, PabloBuilder & pb) {
209    // if-hierarchies are not inserted within unbounded repetitions
210    if (mStarDepth > 0) {
211        for (RE * re : *seq) {
212            marker = process(re, marker, pb);
213        }
214        return marker;
215    } else {
216        return compileSeqTail(seq->begin(), seq->end(), 0, marker, pb);
217    }
218}
219
220MarkerType RE_Compiler::compileSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
221    if (current == end) {
222        return marker;
223    } else if (matchLenSoFar < IfInsertionGap) {
224        RE * r = *current;
225        marker = process(r, marker, pb);
226        current++;
227        return compileSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
228    } else {
229        Var * m = pb.createVar("m", pb.createZeroes());
230        NameMap nestedMap(mCompiledName);
231        mCompiledName = &nestedMap;
232        PabloBuilder nested = PabloBuilder::Create(pb);
233        MarkerType m1 = compileSeqTail(current, end, 0, marker, nested);
234        nested.createAssign(m, markerVar(m1));
235        pb.createIf(markerVar(marker), nested);
236        mCompiledName = nestedMap.getParent();
237        return makeMarker(m1.pos, m);
238    }
239}
240
241MarkerType RE_Compiler::compileAlt(Alt * alt, MarkerType marker, PabloBuilder & pb) {
242    std::vector<PabloAST *>  accum(3, pb.createZeroes());
243    MarkerType const base = marker;
244    // The following may be useful to force a common Advance rather than separate
245    // Advances in each alternative.
246    for (RE * re : *alt) {
247        MarkerType m = process(re, base, pb);
248        MarkerPosition p = markerPos(m);
249        accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
250    }
251    if (isa<Zeroes>(accum[MarkerPosition::FinalPostPositionUnit])) {
252        return makeMarker(MarkerPosition::FinalMatchUnit, accum[MarkerPosition::FinalMatchUnit]);
253    }
254    PabloAST * combine = pb.createAdvance(accum[MarkerPosition::FinalMatchUnit], 1, "combine");
255    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[MarkerPosition::FinalPostPositionUnit], "alt");
256    return makeMarker(MarkerPosition::FinalPostPositionUnit, combine);
257}
258
259MarkerType RE_Compiler::compileAssertion(Assertion * a, MarkerType marker, PabloBuilder & pb) {
260    RE * asserted = a->getAsserted();
261    if (a->getKind() == Assertion::Kind::Lookbehind) {
262        MarkerType lookback = compile(asserted, pb);
263        AlignMarkers(marker, lookback, pb);
264        PabloAST * lb = markerVar(lookback);
265        if (a->getSense() == Assertion::Sense::Negative) {
266            lb = pb.createNot(lb);
267        }
268        return makeMarker(markerPos(marker), pb.createAnd(markerVar(marker), lb, "lookback"));
269    } else if (a->getKind() == Assertion::Kind::Boundary) {
270        MarkerType cond = compile(asserted, pb);
271        if (LLVM_LIKELY(markerPos(cond) == MarkerPosition::FinalMatchUnit)) {
272            MarkerType postCond = AdvanceMarker(cond, MarkerPosition::FinalPostPositionUnit, pb);
273            PabloAST * boundaryCond = pb.createAnd(mAny, pb.createXor(markerVar(cond), markerVar(postCond)));
274            if (a->getSense() == Assertion::Sense::Negative) {
275                boundaryCond = pb.createNot(boundaryCond);
276            }
277            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
278            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
279        }
280        else UnsupportedRE("Unsupported boundary assertion");
281    } else if (isUnicodeUnitLength(asserted)) {
282        MarkerType lookahead = compile(asserted, pb);
283        if (LLVM_LIKELY(markerPos(lookahead) == MarkerPosition::FinalMatchUnit)) {
284            PabloAST * la = markerVar(lookahead);
285            if (a->getSense() == Assertion::Sense::Negative) {
286                la = pb.createNot(la);
287            }
288            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
289            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
290        }
291    }
292    UnsupportedRE("Unsupported lookahead assertion.");
293}
294
295inline bool alignedUnicodeLength(const RE * lh, const RE * rh) {
296    const auto lhl = getUnicodeUnitLengthRange(lh);
297    const auto rhl = getUnicodeUnitLengthRange(rh);
298    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
299}
300
301MarkerType RE_Compiler::compileDiff(Diff * diff, MarkerType marker, PabloBuilder & pb) {
302    RE * lh = diff->getLH();
303    RE * rh = diff->getRH();
304    if (alignedUnicodeLength(lh, rh)) {
305        MarkerType t1 = process(lh, marker, pb);
306        MarkerType t2 = process(rh, marker, pb);
307        AlignMarkers(t1, t2, pb);
308        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
309    }
310    UnsupportedRE("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
311}
312
313MarkerType RE_Compiler::compileIntersect(Intersect * x, MarkerType marker, PabloBuilder & pb) {
314    RE * lh = x->getLH();
315    RE * rh = x->getRH();
316    if (alignedUnicodeLength(lh, rh)) {
317        MarkerType t1 = process(lh, marker, pb);
318        MarkerType t2 = process(rh, marker, pb);
319        AlignMarkers(t1, t2, pb);
320        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
321    }
322    UnsupportedRE("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
323}
324
325MarkerType RE_Compiler::compileRep(Rep * rep, MarkerType marker, PabloBuilder & pb) {
326    int lb = rep->getLB();
327    int ub = rep->getUB();
328    if (lb > 0) {
329        marker = processLowerBound(rep->getRE(), lb, marker, IfInsertionGap, pb);
330    }
331    if (ub == Rep::UNBOUNDED_REP) {
332        marker = processUnboundedRep(rep->getRE(), marker, pb);
333    } else if (lb < ub) {
334        marker = processBoundedRep(rep->getRE(), ub - lb, marker, IfInsertionGap, pb);
335    }
336    return marker;
337}
338
339/*
340   Given a stream |repeated_j| marking positions associated with |j| conecutive matches to an item
341   compute a stream marking |repeat_count| consecutive occurrences of such items.
342*/
343   
344PabloAST * RE_Compiler::consecutive_matches(PabloAST * repeated_j, int j, int repeat_count, PabloAST * indexStream, PabloBuilder & pb) {
345    if (j == repeat_count) return repeated_j;
346    int i = std::min(j, repeat_count - j);
347    int k = j + i;
348    if (/*j > IfInsertionGap*/ false) {
349        Var * repeated = pb.createVar("repeated", pb.createZeroes());
350        PabloBuilder nested = PabloBuilder::Create(pb);
351        NameMap nestedMap(mCompiledName);
352        mCompiledName = &nestedMap;
353       
354        PabloAST * adv_i = nullptr;
355        if (indexStream == nullptr) adv_i = nested.createAdvance(repeated_j, i);
356        else adv_i = nested.createIndexedAdvance(repeated_j, indexStream, i);
357        PabloAST * repeated_k = nested.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
358        nested.createAssign(repeated, consecutive_matches(repeated_k, k, repeat_count, indexStream, nested));
359        pb.createIf(repeated_j, nested);
360        mCompiledName = nestedMap.getParent();
361        return repeated;
362    }
363    else {
364        PabloAST * adv_i = nullptr;
365        if (indexStream == nullptr) adv_i = pb.createAdvance(repeated_j, i);
366        else adv_i = pb.createIndexedAdvance(repeated_j, indexStream, i);
367        PabloAST * repeated_k = pb.createAnd(repeated_j, adv_i, "at" + std::to_string(k) + "of" + std::to_string(repeat_count));
368        return consecutive_matches(repeated_k, k, repeat_count, indexStream, pb);
369    }
370}
371
372
373inline PabloAST * RE_Compiler::reachable(PabloAST * repeated, int length, int repeat_count, PabloAST * indexStream, PabloBuilder & pb) {
374    int i = length;
375    int total_lgth = repeat_count * length;
376    if (repeat_count == 0) {
377        return repeated;
378    }
379    PabloAST * reachable = nullptr;
380    if (indexStream == nullptr) reachable = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
381    else reachable = pb.createOr(repeated, pb.createIndexedAdvance(repeated, indexStream, 1), "within1");
382    while ((i * 2) < total_lgth) {
383        PabloAST * v = reachable;
384        PabloAST * v2 = nullptr;
385        if (indexStream == nullptr) v2 = pb.createAdvance(v, i);
386        else v2 = pb.createIndexedAdvance(v, indexStream, i);
387        i *= 2;
388        reachable = pb.createOr(v, v2, "within" + std::to_string(i));
389    }
390    if (LLVM_LIKELY(i < total_lgth)) {
391        PabloAST * v = reachable;
392        PabloAST * v2 = nullptr;
393        if (indexStream == nullptr) v2 = pb.createAdvance(v, total_lgth - i);
394        else v2 = pb.createIndexedAdvance(v, indexStream, total_lgth - i);
395        reachable = pb.createOr(v, v2, "within" + std::to_string(total_lgth));
396    }
397    return reachable;
398}
399
400MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, int ifGroupSize, PabloBuilder & pb) {
401    if (LLVM_UNLIKELY(lb == 0)) return marker;
402    else if (LLVM_UNLIKELY(lb == 1)) return process(repeated, marker, pb);
403    //
404    // A bounded repetition with an upper bound of at least 2.
405    if (!mGraphemeBoundaryRule && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
406        // Check for a regular expression that satisfies on of the special conditions that
407        // allow implementation using the log2 technique.
408        if (isByteLength(repeated)) {
409            PabloAST * cc = markerVar(compile(repeated, pb));
410            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, nullptr, pb);
411            const auto pos = markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1;
412            PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), pos);
413            return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
414        }
415        else if (isUnicodeUnitLength(repeated)) {
416            PabloAST * cc = markerVar(compile(repeated, pb));
417            PabloAST * cc_lb = consecutive_matches(cc, 1, lb, mFinal, pb);
418            const auto pos = markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1;
419            PabloAST * marker_fwd = pb.createIndexedAdvance(markerVar(marker), mFinal, pos);
420            return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
421        }
422        else if (isTypeForLocal(repeated)) {
423            CC * firstSymSet = RE_Local::first(repeated);
424            std::map<CC *, CC*> followMap;
425            RE_Local::follow(repeated, followMap);
426            bool firstSymSet_found_in_follow = false;
427            for (auto & entry : followMap) {
428                if (entry.second->intersects(*firstSymSet)) {
429                    firstSymSet_found_in_follow = true;
430                }
431            }
432            if (!firstSymSet_found_in_follow) {
433                // When the first symbol is unique, we can use it as an index stream.
434                PabloAST * firstCCstream = markerVar(compile(firstSymSet, pb));
435                // Find all matches to the repeated regexp.
436                PabloAST * submatch = markerVar(AdvanceMarker(compile(repeated, pb), MarkerPosition::FinalPostPositionUnit, pb));
437                // Consecutive submatches require that the symbol following the end of one submatch is the first symbol for
438                // the next submatch.   lb-1 such submatches are required.
439                PabloAST * consecutive_submatch = consecutive_matches(submatch, 1, lb-1, firstCCstream, pb);
440                // Find submatch positions which are lb-2 start symbols forward from the current marker position.
441                PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
442                PabloAST * marker_fwd = pb.createIndexedAdvance(base, firstCCstream, lb - 1);
443                PabloAST * consecutive_lb_1 = pb.createAnd(marker_fwd, consecutive_submatch);
444                // From any of these positions, any position reachable by one more occurrence of the
445                // regexp is a match.
446                return process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, consecutive_lb_1), pb);
447            }
448        }
449    }
450    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
451    auto group = ifGroupSize < lb ? ifGroupSize : lb;
452    for (auto i = 0; i < group; i++) {
453        marker = process(repeated, marker, pb);
454        if (mGraphemeBoundaryRule) {
455            marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
456        }
457    }
458    if (lb == group) {
459        return marker;
460    }
461    Var * m = pb.createVar("m", pb.createZeroes());
462    PabloBuilder nested = PabloBuilder::Create(pb);
463    NameMap nestedMap(mCompiledName);
464    mCompiledName = &nestedMap;
465    MarkerType m1 = processLowerBound(repeated, lb - group, marker, ifGroupSize * 2, nested);
466    nested.createAssign(m, markerVar(m1));
467    pb.createIf(markerVar(marker), nested);
468    mCompiledName = nestedMap.getParent();
469    return makeMarker(m1.pos, m);
470}
471   
472MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  PabloBuilder & pb) {
473    if (LLVM_UNLIKELY(ub == 0)) return marker;
474    //
475    // A bounded repetition with an upper bound of at least 2.
476    if (!mGraphemeBoundaryRule && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition) && (ub > 1)) {
477        // Check for a regular expression that satisfies on of the special conditions that
478        // allow implementation using the log2 technique.
479        if (isByteLength(repeated)) {
480            // log2 upper bound for fixed length (=1) class
481            // Create a mask of positions reachable within ub from current marker.
482            // Use matchstar, then apply filter.
483            PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
484            // If we've advanced the cursor to the post position unit, cursor begins on the first masked bit of the bounded mask.
485            // Extend the mask by ub - 1 byte positions to ensure the mask ends on the FinalMatchUnit of the repeated region.
486            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, nullptr, pb);
487            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask);
488            // MatchStar deposits any cursors on the post position. However those cursors may may land on the initial "byte" of a
489            // "multi-byte" character. Combine the masked range with any nonFinals.
490            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
491            return makeMarker(MarkerPosition::FinalPostPositionUnit, bounded);
492        }
493        else if (isUnicodeUnitLength(repeated)) {
494            // For a regexp which represent a single Unicode codepoint, we can use the mFinal stream
495            // as an index stream for an indexed advance operation.
496            PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
497            PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, mFinal, pb);
498            PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask, "masked");
499            PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
500            return makeMarker(MarkerPosition::FinalPostPositionUnit, bounded);
501        }
502        else if (isTypeForLocal(repeated)) {
503            CC * firstSymSet = RE_Local::first(repeated);
504            std::map<CC *, CC*> followMap;
505            RE_Local::follow(repeated, followMap);
506            bool firstSymSet_found_in_follow = false;
507            for (auto & entry : followMap) {
508                if (entry.second->intersects(*firstSymSet)) {
509                    firstSymSet_found_in_follow = true;
510                }
511            }
512            if (!firstSymSet_found_in_follow) {
513                // When the first symbol is unique, we can use it as an index stream.
514                PabloAST * firstCCstream = markerVar(compile(firstSymSet, pb));
515                PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
516                PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, firstCCstream, pb);
517                PabloAST * masked = pb.createAnd(markerVar(AdvanceMarker(compile(repeated, pb), MarkerPosition::FinalPostPositionUnit, pb)), upperLimitMask, "masked");
518                PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
519                return makeMarker(MarkerPosition::FinalPostPositionUnit, bounded);
520            }
521        }
522    }
523    // Fall through to general case.  Process the first item and insert the rest into an if-structure.
524    auto group = ifGroupSize < ub ? ifGroupSize : ub;
525    for (auto i = 0; i < group; i++) {
526        MarkerType a = process(repeated, marker, pb);
527        MarkerType m = marker;
528        AlignMarkers(a, m, pb);
529        marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m)));
530        if (mGraphemeBoundaryRule) {
531            marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
532        }
533    }
534    if (ub == group) {
535        return marker;
536    }
537    Var * m1a = pb.createVar("m", pb.createZeroes());
538    PabloBuilder nested = PabloBuilder::Create(pb);
539    NameMap nestedMap(mCompiledName);
540    mCompiledName = &nestedMap;
541    MarkerType m1 = processBoundedRep(repeated, ub - group, marker, ifGroupSize * 2, nested);
542    nested.createAssign(m1a, markerVar(m1));
543    pb.createIf(markerVar(marker), nested);
544    mCompiledName = nestedMap.getParent();
545    return makeMarker(m1.pos, m1a);
546}
547
548MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
549    // always use PostPosition markers for unbounded repetition.
550    PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
551    if (!mGraphemeBoundaryRule && isByteLength(repeated)  && !AlgorithmOptionIsSet(DisableMatchStar)) {
552        PabloAST * mask = markerVar(compile(repeated, pb));
553        PabloAST * nonFinal = mNonFinal;
554        if (mGraphemeBoundaryRule) {
555            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
556        }
557        // The post position character may land on the initial byte of a multi-byte character. Combine them with the masked range.
558        PabloAST * unbounded = pb.createMatchStar(base, pb.createOr(mask, nonFinal), "unbounded");
559        return makeMarker(MarkerPosition::FinalPostPositionUnit, unbounded);
560    } else if (isUnicodeUnitLength(repeated) && !AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar)) {
561        PabloAST * cc = markerVar(compile(repeated, pb));
562        PabloAST * mstar = nullptr;
563        PabloAST * nonFinal = mNonFinal;
564        if (mGraphemeBoundaryRule) {
565            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
566        }
567        cc = pb.createOr(cc, nonFinal);
568        mstar = pb.createMatchStar(base, cc);
569        PabloAST * final = mFinal;
570        if (mGraphemeBoundaryRule) {
571            final = mGraphemeBoundaryRule;
572        }
573        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
574    } else if (mStarDepth > 0){
575        PabloBuilder * const outer = pb.getParent();
576        Var * starPending = outer->createVar("pending", outer->createZeroes());
577        Var * starAccum = outer->createVar("accum", outer->createZeroes());
578        mStarDepth++;
579        PabloAST * m1 = pb.createOr(base, starPending);
580        PabloAST * m2 = pb.createOr(base, starAccum);
581        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, m1), pb);
582        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, pb);
583        PabloAST * loopComputation = markerVar(result);
584        pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
585        pb.createAssign(starAccum, pb.createOr(loopComputation, m2));
586        mWhileTest = pb.createOr(mWhileTest, starPending);
587        mStarDepth--;     
588        return makeMarker(markerPos(result), pb.createOr(base, starAccum, "unbounded"));
589    } else {
590        Var * whileTest = pb.createVar("test", base);
591        Var * whilePending = pb.createVar("pending", base);
592        Var * whileAccum = pb.createVar("accum", base);
593        mWhileTest = pb.createZeroes();
594        PabloBuilder wb = PabloBuilder::Create(pb);
595        NameMap nestedMap(mCompiledName);
596        mCompiledName = &nestedMap;
597        mStarDepth++;
598        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, whilePending), wb);
599        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, wb);
600        PabloAST * loopComputation = markerVar(result);
601        wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
602        wb.createAssign(whileAccum, wb.createOr(loopComputation, whileAccum));
603        wb.createAssign(whileTest, wb.createOr(mWhileTest, whilePending));
604        pb.createWhile(whileTest, wb);
605        mStarDepth--;
606        mCompiledName = nestedMap.getParent();
607        return makeMarker(markerPos(result), whileAccum);
608    }
609}
610
611inline MarkerType RE_Compiler::compileStart(const MarkerType marker, pablo::PabloBuilder & pb) {
612    MarkerType m = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
613    if (UNICODE_LINE_BREAK) {
614        PabloAST * line_end = mPB.createOr(mLineBreak, mCRLF);
615        PabloAST * sol_init = pb.createNot(pb.createOr(pb.createAdvance(pb.createNot(line_end), 1), mCRLF));
616        PabloAST * sol = pb.createScanThru(pb.createAnd(mInitial, sol_init), mNonFinal);
617        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
618    } else {
619        PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
620        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
621    }
622}
623
624inline MarkerType RE_Compiler::compileEnd(const MarkerType marker, pablo::PabloBuilder & pb) {
625    PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
626    return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(nextPos, mLineBreak, "eol"));
627}
628
629inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
630    if (marker.pos != newpos) {
631        if (marker.pos == MarkerPosition::FinalMatchUnit) {
632            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
633            PabloAST * nonFinal = mNonFinal;
634            if (mGraphemeBoundaryRule) {
635                nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
636            }
637            PabloAST * starts = pb.createAnd(mInitial, marker.stream);
638            marker.stream = pb.createScanThru(starts, nonFinal, "fpp");
639            marker.pos = MarkerPosition::FinalPostPositionUnit;
640        }
641    }
642    return marker;
643}
644
645inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
646    if (m1.pos < m2.pos) {
647        m1 = AdvanceMarker(m1, m2.pos, pb);
648    } else if (m2.pos < m1.pos) {
649        m2 = AdvanceMarker(m2, m1.pos, pb);
650    }
651}
652   
653LLVM_ATTRIBUTE_NORETURN void RE_Compiler::UnsupportedRE(std::string errmsg) {
654    llvm::report_fatal_error(errmsg);
655}
656   
657   
658
659RE_Compiler::RE_Compiler(PabloKernel * kernel, cc::CC_Compiler & ccCompiler, bool local)
660: mKernel(kernel)
661, mCCCompiler(ccCompiler)
662, mLocal(local)
663, mLineBreak(nullptr)
664, mCRLF(nullptr)
665, mAny(nullptr)
666, mGraphemeBoundaryRule(nullptr)
667, mInitial(nullptr)
668, mNonFinal(nullptr)
669, mFinal(nullptr)
670, mWhileTest(nullptr)
671, mStarDepth(0)
672, mPB(ccCompiler.getBuilder())
673, mCompiledName(&mBaseMap) {
674    Var * const linebreak = mKernel->getInputStreamVar("linebreak");
675    mLineBreak = mPB.createExtract(linebreak, mPB.getInteger(0));
676    mAny = mPB.createNot(mLineBreak, "any");
677    Var * const required = mKernel->getInputStreamVar("required");
678    mInitial = mPB.createExtract(required, mPB.getInteger(0));
679    mNonFinal = mPB.createExtract(required, mPB.getInteger(1));
680    mFinal = mPB.createExtract(required, mPB.getInteger(2));
681    mCRLF = mPB.createExtract(required, mPB.getInteger(3));
682}
683
684} // end of namespace re
Note: See TracBrowser for help on using the repository browser.