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

Last change on this file was 5936, checked in by cameron, 3 months ago

Bug fix

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