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

Last change on this file since 5780 was 5780, checked in by cameron, 17 months ago

Strip out local mode from RE compiler

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