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

Last change on this file since 6141 was 6133, checked in by xwa163, 13 months ago
  1. Add sourceCC in multiplexed CC
  2. Remove workaround FakeBasisBits? from ICGrep
  3. Implement Swizzled version of LZParabix
  4. Init checkin for SwizzleByGather? Kernel
File size: 30.3 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, mBasisSetNumbering));
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, cc::BitNumbering basisSetNumbering)
631: mEntryScope(scope)
632, mCCCompiler(ccCompiler)
633, mLineBreak(nullptr)
634, mWhileTest(nullptr)
635, mStarDepth(0)
636, mCompiledName(&mBaseMap)
637, mBasisSetNumbering(basisSetNumbering) {
638    PabloBuilder pb(mEntryScope);
639    mLineBreak = pb.createZeroes();  // default so "^/$" matches start/end of text only
640    mNonFinalName = makeName("u8NonFinal", makeAlt({makeByte(0xC2, 0xF4),
641                               makeSeq({makeByte(0xE0, 0xF4), makeByte(0x80, 0xBF)}),
642                               makeSeq({makeByte(0xF0, 0xF4), makeByte(0x80, 0xBF), makeByte(0x80, 0xBF)})}));
643}
644
645} // end of namespace re
Note: See TracBrowser for help on using the repository browser.