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

Last change on this file was 6297, checked in by cameron, 4 weeks ago

Merge branch 'master' of https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel

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