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

Last change on this file since 5899 was 5899, checked in by cameron, 14 months ago

Fixes for Unix line break mode

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