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

Last change on this file since 5808 was 5808, checked in by cameron, 15 months ago

Fix for CRLF issue

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