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

Last change on this file since 4809 was 4809, checked in by nmedfort, 4 years ago

Refactored UCD property resolution.

File size: 29.3 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6#include <re/re_compiler.h>
7//Regular Expressions
8#include <re/re_name.h>
9#include <re/re_any.h>
10#include <re/re_start.h>
11#include <re/re_end.h>
12#include <re/re_alt.h>
13#include <re/re_cc.h>
14#include <re/re_seq.h>
15#include <re/re_rep.h>
16#include <re/re_diff.h>
17#include <re/re_intersect.h>
18#include <re/re_assertion.h>
19#include <re/re_analysis.h>
20#include <cc/cc_namemap.hpp>
21#include <pablo/codegenstate.h>
22#include <UCD/ucd_compiler.hpp>
23#include <UCD/resolve_properties.h>
24#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
25#include <UCD/precompiled_properties.h>
26#endif
27#include <assert.h>
28#include <stdexcept>
29#include <iostream>
30#include <pablo/printer_pablos.h>
31
32#include "llvm/Support/CommandLine.h"
33static cl::OptionCategory fREcompilationOptions("Regex Compilation Options",
34                                      "These options control the compilation of regular expressions to Pablo.");
35
36static cl::opt<bool> DisableLog2BoundedRepetition("disable-log2-bounded-repetition", cl::init(false),
37                     cl::desc("disable log2 optimizations for bounded repetition of bytes"), cl::cat(fREcompilationOptions));
38static cl::opt<int> IfInsertionGap("if-insertion-gap", cl::init(3), cl::desc("minimum number of nonempty elements between inserted if short-circuit tests"), cl::cat(fREcompilationOptions));
39static cl::opt<bool> DisableMatchStar("disable-matchstar", cl::init(false),
40                     cl::desc("disable MatchStar optimization"), cl::cat(fREcompilationOptions));
41static cl::opt<bool> DisableUnicodeMatchStar("disable-unicode-matchstar", cl::init(false),
42                     cl::desc("disable Unicode MatchStar optimization"), cl::cat(fREcompilationOptions));
43static cl::opt<bool> DisableUnicodeLineBreak("disable-unicode-linebreak", cl::init(false),
44                     cl::desc("disable Unicode line breaks - use LF only"), cl::cat(fREcompilationOptions));
45static cl::opt<bool> SetMod64Approximation("mod64-approximate", cl::init(false),
46                     cl::desc("set mod64 approximate mode"), cl::cat(fREcompilationOptions));
47#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
48static cl::opt<bool> UsePregeneratedUnicode("use-pregenerated-unicode", cl::init(true),
49                     cl::desc("use fixed pregenerated Unicode character class sets instead"), cl::cat(fREcompilationOptions));
50#endif
51using namespace pablo;
52
53namespace re {
54
55RE_Compiler::RE_Compiler(pablo::PabloFunction & function, cc::CC_Compiler & ccCompiler)
56: mCCCompiler(ccCompiler)
57, mLineFeed(nullptr)
58, mCRLF(nullptr)
59, mUnicodeLineBreak(nullptr)
60, mInitial(nullptr)
61, mNonFinal(nullptr)
62, mFinal(nullptr)
63, mWhileTest(nullptr)
64, mStarDepth(0)
65, mLoopVariants()
66, mPB(*ccCompiler.getBuilder().getPabloBlock(), ccCompiler.getBuilder())
67, mFunction(function)
68{
69
70}
71   
72MarkerType RE_Compiler::AdvanceMarker(MarkerType m, MarkerPosition newpos, PabloBuilder & pb) {
73    if (m.pos == newpos) return m;
74    PabloAST * a = m.stream;
75    if (m.pos == MarkerPosition::FinalMatchByte) {
76        // Must advance at least to InitialPostPositionByte
77        a = pb.createAdvance(a, 1, "adv");
78    }
79    // Now at InitialPostPositionByte; is a further advance needed?
80    if (newpos == MarkerPosition::FinalPostPositionByte) {
81        // Must advance through nonfinal bytes
82        a = pb.createScanThru(pb.createAnd(mInitial, a), mNonFinal, "scanToFinal");
83    }
84    return {newpos, a};
85}
86
87void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
88    if (m1.pos < m2.pos) {
89        m1 = AdvanceMarker(m1, m2.pos, pb); 
90    }
91    else if (m2.pos < m1.pos) {
92        m2 = AdvanceMarker(m2, m1.pos, pb); 
93    }
94}
95
96#define UNICODE_LINE_BREAK (!DisableUnicodeLineBreak)
97
98void RE_Compiler::initializeRequiredStreams() {
99
100    Assign * LF = mPB.createAssign("LF", mCCCompiler.compileCC(makeCC(0x0A)));
101    mLineFeed = LF;
102    PabloAST * CR = mCCCompiler.compileCC(makeCC(0x0D));
103    PabloAST * LF_VT_FF_CR = mCCCompiler.compileCC(makeCC(0x0A, 0x0D));
104
105    PabloBuilder crb = PabloBuilder::Create(mPB);
106    PabloAST * cr1 = crb.createAdvance(CR, 1, "cr1");
107    Assign * acrlf = crb.createAssign("crlf", crb.createAnd(cr1, LF));
108    mPB.createIf(CR, {acrlf}, crb);
109    mCRLF = acrlf;
110
111    PabloAST * u8pfx = mCCCompiler.compileCC(makeCC(0xC0, 0xFF));
112    PabloBuilder it = PabloBuilder::Create(mPB);
113    PabloAST * u8pfx2 = mCCCompiler.compileCC(makeCC(0xC2, 0xDF), it);
114    PabloAST * u8pfx3 = mCCCompiler.compileCC(makeCC(0xE0, 0xEF), it);
115    PabloAST * u8pfx4 = mCCCompiler.compileCC(makeCC(0xF0, 0xF4), it);
116    Assign * u8suffix = it.createAssign("u8suffix", mCCCompiler.compileCC(makeCC(0x80, 0xBF)));
117   
118    //
119    // Two-byte sequences
120    PabloBuilder it2 = PabloBuilder::Create(it);
121    Assign * u8scope22 = it2.createAssign("u8scope22", it2.createAdvance(u8pfx2, 1));
122    Assign * NEL = it2.createAssign("NEL", it2.createAnd(it2.createAdvance(mCCCompiler.compileCC(makeCC(0xC2), it2), 1), mCCCompiler.compileCC(makeCC(0x85), it2)));
123    it.createIf(u8pfx2, {u8scope22, NEL}, it2);
124   
125    //
126    // Three-byte sequences
127    PabloBuilder it3 = PabloBuilder::Create(it);
128    Assign * u8scope32 = it3.createAssign("u8scope32", it3.createAdvance(u8pfx3, 1));
129    PabloAST * u8scope33 = it3.createAdvance(u8pfx3, 2);
130    Assign * u8scope3X = it3.createAssign("u8scope3X", it3.createOr(u8scope32, u8scope33));
131    PabloAST * E2_80 = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE2), it3), 1), mCCCompiler.compileCC(makeCC(0x80), it3));
132    Assign * LS_PS = it3.createAssign("LS_PS", it3.createAnd(it3.createAdvance(E2_80, 1), mCCCompiler.compileCC(makeCC(0xA8,0xA9), it3)));
133    PabloAST * E0_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xE0), it3), 1), mCCCompiler.compileCC(makeCC(0x80, 0x9F), it3));
134    PabloAST * ED_invalid = it3.createAnd(it3.createAdvance(mCCCompiler.compileCC(makeCC(0xED), it3), 1), mCCCompiler.compileCC(makeCC(0xA0, 0xBF), it3));
135    Assign * EX_invalid = it3.createAssign("EX_invalid", it3.createOr(E0_invalid, ED_invalid));
136    it.createIf(u8pfx3, {u8scope32, u8scope3X, LS_PS, EX_invalid}, it3);
137 
138    //
139    // Four-byte sequences
140    PabloBuilder it4 = PabloBuilder::Create(it);
141    PabloAST * u8scope42 = it4.createAdvance(u8pfx4, 1, "u8scope42");
142    PabloAST * u8scope43 = it4.createAdvance(u8scope42, 1, "u8scope43");
143    PabloAST * u8scope44 = it4.createAdvance(u8scope43, 1, "u8scope44");
144    Assign * u8scope4nonfinal = it4.createAssign("u8scope4nonfinal", it4.createOr(u8scope42, u8scope43));
145    Assign * u8scope4X = it4.createAssign("u8scope4X", it4.createOr(u8scope4nonfinal, u8scope44));
146    PabloAST * F0_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF0), it4), 1), mCCCompiler.compileCC(makeCC(0x80, 0x8F), it4));
147    PabloAST * F4_invalid = it4.createAnd(it4.createAdvance(mCCCompiler.compileCC(makeCC(0xF4), it4), 1), mCCCompiler.compileCC(makeCC(0x90, 0xBF), it4));
148    Assign * FX_invalid = it4.createAssign("FX_invalid", it4.createOr(F0_invalid, F4_invalid));
149    it.createIf(u8pfx4, {u8scope4nonfinal, u8scope4X, FX_invalid}, it4);
150
151    //
152    // Invalid cases
153    PabloAST * anyscope = it.createOr(u8scope22, it.createOr(u8scope3X, u8scope4X));
154    PabloAST * legalpfx = it.createOr(it.createOr(u8pfx2, u8pfx3), u8pfx4);
155    //  Any scope that does not have a suffix byte, and any suffix byte that is not in
156    //  a scope is a mismatch, i.e., invalid UTF-8.
157    PabloAST * mismatch = it.createXor(anyscope, u8suffix);
158    //
159    PabloAST * EF_invalid = it.createOr(EX_invalid, FX_invalid);
160    PabloAST * pfx_invalid = it.createXor(u8pfx, legalpfx);
161    Assign * u8invalid = it.createAssign("u8invalid", it.createOr(pfx_invalid, it.createOr(mismatch, EF_invalid)));
162    Assign * u8valid = it.createAssign("u8valid", it.createNot(u8invalid));
163    //
164    //
165   
166    Assign * valid_pfx = it.createAssign("valid_pfx", it.createAnd(u8pfx, u8valid));
167    mNonFinal = it.createAssign("nonfinal", it.createAnd(it.createOr(it.createOr(u8pfx, u8scope32), u8scope4nonfinal), u8valid));
168   
169    Assign * NEL_LS_PS = it.createAssign("NEL_LS_PS", it.createOr(NEL, LS_PS));
170    mPB.createIf(u8pfx, {u8invalid, valid_pfx, mNonFinal, NEL_LS_PS}, it);
171   
172    PabloAST * LB_chars = mPB.createOr(LF_VT_FF_CR, NEL_LS_PS);
173    PabloAST * u8single = mPB.createAnd(mCCCompiler.compileCC(makeCC(0x00, 0x7F)), mPB.createNot(u8invalid));
174    mInitial = mPB.createOr(u8single, valid_pfx, "initial");
175    mFinal = mPB.createNot(mPB.createOr(mNonFinal, u8invalid), "final");
176    mUnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
177    PabloAST * const lb = UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed;
178    mFunction.setResult(1, mPB.createAssign("lf", mPB.createAnd(lb, mPB.createNot(mCRLF))));
179}
180
181void RE_Compiler::gatherUnicodePropertyNames(RE * re, NameSet & nameSet) {
182
183    struct UnicodePropertyNameMap {
184        using PropertyMap = std::map<std::string, Name *>;
185        using NamespacedPropertyMap = std::map<std::pair<std::string, std::string>, Name *>;
186        void process(RE * re) {
187            if (Name * name = dyn_cast<Name>(re)) {
188                if (name->getDefinition()) {
189                    process(name->getDefinition());
190                    return;
191                }
192                if (name->hasNamespace()) {
193                    const auto f = mNamespacedPropertyMap.find(std::make_pair(name->getNamespace(), name->getName()));
194                    if (f != mNamespacedPropertyMap.end()) {
195                        if (f->second != name) {
196                            name->setDefinition(f->second);
197                        }
198                        return;
199                    }
200                    mNamespacedPropertyMap.insert(std::make_pair(std::make_pair(name->getNamespace(), name->getName()), name));
201                } else {
202                    const auto f = mPropertyMap.find(name->getName());
203                    if (f != mPropertyMap.end()) {
204                        if (f->second != name) {
205                            name->setDefinition(f->second);
206                        }
207                        return;
208                    }
209                    mPropertyMap.insert(std::make_pair(name->getName(), name));
210                }
211                if (name->getType() == Name::Type::UnicodeProperty) {
212                    RE * definition = UCD::resolvePropertyDefinition(name);
213                    if (definition) {
214                        process(definition);
215                    } else {
216                        mNameSet.insert(name);
217                    }
218                }
219            } else if (Seq* seq = dyn_cast<Seq>(re)) {
220                for (RE * re : *seq) {
221                    process(re);
222                }
223            } else if (Alt * alt = dyn_cast<Alt>(re)) {
224                for (RE * re : *alt) {
225                    process(re);
226                }
227            } else if (Rep * rep = dyn_cast<Rep>(re)) {
228                process(rep->getRE());
229            } else if (Assertion * a = dyn_cast<Assertion>(re)) {
230                process(a->getAsserted());
231            } else if (Diff * diff = dyn_cast<Diff>(re)) {
232                process(diff->getLH());
233                process(diff->getRH());
234            } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
235                process(ix->getLH());
236                process(ix->getRH());
237            }
238
239        }
240
241        UnicodePropertyNameMap(NameSet & nameSet) : mNameSet(nameSet) {}
242
243    private:
244        NameSet &                   mNameSet;
245        PropertyMap                 mPropertyMap;
246        NamespacedPropertyMap       mNamespacedPropertyMap;
247    } ;
248
249    UnicodePropertyNameMap(nameSet).process(re);
250}
251
252void RE_Compiler::compileUnicodeNames(RE * re) {
253    NameSet nameSet;
254    gatherUnicodePropertyNames(re, nameSet);
255#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
256    if (UsePregeneratedUnicode) {
257        for (Name * name : nameSet) {
258            const std::string functionName = UCD::resolvePropertyFunction(name);
259            const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(functionName);
260            Call * call = mPB.createCall(Prototype::Create(functionName, std::get<1>(ep), std::get<2>(ep), std::get<0>(ep)), mCCCompiler.getBasisBits());
261            name->setCompiled(mPB.createAnd(call, mPB.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
262        }
263    } else {
264#endif
265        std::vector<UCD::UnicodeSet> sets;
266        for (Name * name : nameSet) {
267            sets.push_back(std::move(UCD::resolveUnicodeSet(name)));
268        }
269        if (sets.size() > 0) {
270            UCD::UCDCompiler ucdCompiler(mCCCompiler);
271            std::vector<PabloAST *> classes(std::move(ucdCompiler.generateWithDefaultIfHierarchy(sets, mPB)));
272            auto value = classes.begin();
273            for (Name * name : nameSet) {
274                name->setCompiled(mPB.createAnd(*value++, mPB.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
275            }
276        }
277#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
278    }
279#endif
280}
281
282void RE_Compiler::finalizeMatchResult(MarkerType match_result) {
283    //These three lines are specifically for grep.
284    PabloAST * lb = UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed;
285    PabloAST * v = markerVar(match_result);
286    mFunction.setResult(0, mPB.createAssign("matches", mPB.createAnd(mPB.createMatchStar(v, mPB.createNot(lb)), lb)));
287}
288
289MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
290    return process(re, makeMarker(MarkerPosition::FinalPostPositionByte, pb.createOnes()), pb);
291}
292
293PabloAST * RE_Compiler::nextUnicodePosition(MarkerType m, PabloBuilder & pb) {
294    if (markerPos(m) == MarkerPosition::FinalPostPositionByte) {
295        return markerVar(m);
296    }
297    else if (markerPos(m) == MarkerPosition::InitialPostPositionByte) {
298        return pb.createScanThru(pb.createAnd(mInitial, markerVar(m)), mNonFinal);
299    }
300    else {
301        return pb.createScanThru(pb.createAnd(mInitial, pb.createAdvance(markerVar(m), 1)), mNonFinal);
302    }
303}
304
305MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
306    if (Name * name = dyn_cast<Name>(re)) {
307        return process(name, marker, pb);
308    }
309    else if (Seq* seq = dyn_cast<Seq>(re)) {
310        return process(seq, marker, pb);
311    }
312    else if (Alt * alt = dyn_cast<Alt>(re)) {
313        return process(alt, marker, pb);
314    }
315    else if (Rep * rep = dyn_cast<Rep>(re)) {
316        return process(rep, marker, pb);
317    }
318    else if (Assertion * a = dyn_cast<Assertion>(re)) {
319        return process(a, marker, pb);
320    }
321    else if (isa<Any>(re)) {
322        PabloAST * nextPos = nextUnicodePosition(marker, pb);
323        PabloAST * dot = pb.createNot(UNICODE_LINE_BREAK ? pb.createOr(mUnicodeLineBreak, mCRLF) : mLineFeed);
324        return makeMarker(MarkerPosition::FinalMatchByte, pb.createAnd(nextPos, dot, "dot"));
325    }
326    else if (Diff * diff = dyn_cast<Diff>(re)) {
327        return process(diff, marker, pb);
328    }
329    else if (Intersect * ix = dyn_cast<Intersect>(re)) {
330        return process(ix, marker, pb);
331    }
332    else if (isa<Start>(re)) {
333        MarkerType m = AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb);
334        if (UNICODE_LINE_BREAK) {
335            PabloAST * line_end = mPB.createOr(mUnicodeLineBreak, mCRLF);
336            PabloAST * sol = pb.createNot(pb.createOr(pb.createAdvance(pb.createNot(line_end), 1), mCRLF));
337            return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAnd(markerVar(m), sol, "sol"));
338        }
339        else {
340            PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineFeed), 1));
341            return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(markerVar(m), sol, "sol"));
342        }
343    }
344    else if (isa<End>(re)) {
345        if (UNICODE_LINE_BREAK) {
346            PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb));
347            return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(nextPos, mUnicodeLineBreak, "end"));
348        }
349        PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));  // For LF match
350        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(nextPos, mLineFeed, "eol"));
351    }
352    return marker;
353}
354
355MarkerType RE_Compiler::process(Name * name, MarkerType marker, PabloBuilder & pb) {
356    MarkerType nextPos;
357    if (markerPos(marker) == MarkerPosition::FinalPostPositionByte) {
358        nextPos = marker;
359    }
360    else if (name->getType() == Name::Type::Byte) {
361        nextPos = AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb);
362    }
363    else {
364        nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb);
365    }
366    return makeMarker(MarkerPosition::FinalMatchByte, pb.createAnd(markerVar(nextPos), getNamedCharacterClassStream(name, pb), "m"));
367}
368
369PabloAST * RE_Compiler::getNamedCharacterClassStream(Name * name, PabloBuilder & pb) {
370    PabloAST * var = name->getCompiled();
371    if (LLVM_LIKELY(var != nullptr)) {
372        return var;
373    } else if (name->getDefinition() != nullptr) {
374        MarkerType m = compile(name->getDefinition(), pb);
375        assert(markerPos(m) == MarkerPosition::FinalMatchByte);
376        var = markerVar(m);
377    } else {
378        throw std::runtime_error("Unresolved name " + name->getName());
379    }
380    var = pb.createAnd(var, pb.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed));
381    name->setCompiled(var);
382    return var;
383}
384
385MarkerType RE_Compiler::process(Seq * seq, MarkerType marker, PabloBuilder & pb) {
386    // if-hierarchies are not inserted within unbounded repetitions
387    if (mStarDepth > 0) {
388        for (RE * re : *seq) {
389            marker = process(re, marker, pb);
390        }
391        return marker;
392    }
393    else {
394        return processSeqTail(seq->begin(), seq->end(), 0, marker, pb);
395    }
396}
397
398MarkerType RE_Compiler::processSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBuilder & pb) {
399    if (current == end) return marker;
400    if (matchLenSoFar < IfInsertionGap) {
401        RE * r = *current;
402        marker = process(r, marker, pb);
403        current++;
404        return processSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
405    }
406    else {
407        PabloBuilder nested = PabloBuilder::Create(pb);
408        MarkerType m1 = processSeqTail(current, end, 0, marker, nested);
409        Assign * m1a = nested.createAssign("m", markerVar(m1));
410        pb.createIf(markerVar(marker), {m1a}, nested);
411        return makeMarker(m1.pos, m1a);
412    }
413}
414
415MarkerType RE_Compiler::process(Alt * alt, MarkerType marker, PabloBuilder & pb) {
416    std::vector<PabloAST *>  accum = {pb.createZeroes(), pb.createZeroes(), pb.createZeroes()};
417    MarkerType const base = marker;
418    // The following may be useful to force a common Advance rather than separate
419    // Advances in each alternative.
420    // MarkerType const base = makeMarker(InitialPostPositionByte, postPositionVar(marker, pb), pb);
421    for (RE * re : *alt) {
422        MarkerType rslt = process(re, base, pb);
423        MarkerPosition p = markerPos(rslt);
424        accum[p] = pb.createOr(accum[p], markerVar(rslt), "alt");
425    }
426    if (isa<Zeroes>(accum[MarkerPosition::InitialPostPositionByte]) && isa<Zeroes>(accum[MarkerPosition::FinalPostPositionByte])) {
427        return makeMarker(MarkerPosition::FinalMatchByte, accum[MarkerPosition::FinalMatchByte]);
428    }
429    PabloAST * combine = pb.createOr(accum[InitialPostPositionByte], pb.createAdvance(accum[MarkerPosition::FinalMatchByte], 1), "alt");
430    if (isa<Zeroes>(accum[FinalPostPositionByte])) {
431        return makeMarker(InitialPostPositionByte, combine);
432    }
433    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[MarkerPosition::FinalPostPositionByte], "alt");
434    return makeMarker(MarkerPosition::FinalPostPositionByte, combine);
435}
436
437MarkerType RE_Compiler::process(Assertion * a, MarkerType marker, PabloBuilder & pb) {
438    RE * asserted = a->getAsserted();
439    if (a->getKind() == Assertion::Kind::Lookbehind) {
440        MarkerType m = marker;
441        MarkerType lookback = compile(asserted, pb);
442        AlignMarkers(m, lookback, pb);
443        PabloAST * lb = markerVar(lookback);
444        if (a->getSense() == Assertion::Sense::Negative) {
445            lb = pb.createNot(lb);
446        }
447        return makeMarker(markerPos(m), pb.createAnd(markerVar(marker), lb, "lookback"));
448    }
449    else if (isUnicodeUnitLength(asserted)) {
450        MarkerType lookahead = compile(asserted, pb);
451        assert(markerPos(lookahead) == MarkerPosition::FinalMatchByte);
452        PabloAST * la = markerVar(lookahead);
453        if (a->getSense() == Assertion::Sense::Negative) {
454            la = pb.createNot(la);
455        }
456        MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb);
457        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(markerVar(fbyte), la, "lookahead"));
458    }
459    else {
460        throw std::runtime_error("Unsupported lookahead assertion.");
461    }
462}
463
464MarkerType RE_Compiler::process(Diff * diff, MarkerType marker, PabloBuilder & pb) {
465    RE * lh = diff->getLH();
466    RE * rh = diff->getRH();
467    if (isUnicodeUnitLength(lh) && isUnicodeUnitLength(rh)) {
468        MarkerType t1 = process(lh, marker, pb);
469        MarkerType t2 = process(rh, marker, pb);
470        AlignMarkers(t1, t2, pb);
471        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), pb.createNot(markerVar(t2)), "diff"));
472    }
473    throw std::runtime_error("Unsupported Diff operands: " + Printer_RE::PrintRE(diff));
474}
475
476MarkerType RE_Compiler::process(Intersect * x, MarkerType marker, PabloBuilder & pb) {
477    RE * lh = x->getLH();
478    RE * rh = x->getRH();
479    if (isUnicodeUnitLength(lh) && isUnicodeUnitLength(rh)) {
480        MarkerType t1 = process(lh, marker, pb);
481        MarkerType t2 = process(rh, marker, pb);
482        AlignMarkers(t1, t2, pb);
483        return makeMarker(markerPos(t1), pb.createAnd(markerVar(t1), markerVar(t2), "intersect"));
484    }
485    throw std::runtime_error("Unsupported Intersect operands: " + Printer_RE::PrintRE(x));
486}
487
488MarkerType RE_Compiler::process(Rep * rep, MarkerType marker, PabloBuilder & pb) {
489    int lb = rep->getLB();
490    int ub = rep->getUB();
491    if (lb > 0) {
492        marker = processLowerBound(rep->getRE(), lb, marker, pb);
493    }
494    if (ub == Rep::UNBOUNDED_REP) {
495        return processUnboundedRep(rep->getRE(), marker, pb);
496    }
497    else if (ub == lb) { // if (rep->getUB() != Rep::UNBOUNDED_REP)
498        return marker;
499    }
500    else { // if (rep->getUB() != Rep::UNBOUNDED_REP)
501        return processBoundedRep(rep->getRE(), ub - lb, marker, pb);
502    }
503}
504
505/*
506   Given a stream |repeated| marking positions associated with matches to an item
507   of length |repeated_lgth|, compute a stream marking |repeat_count| consecutive
508   occurrences of such items.
509*/
510
511inline PabloAST * RE_Compiler::consecutive1(PabloAST * repeated, int repeated_lgth, int repeat_count, PabloBuilder & pb) {
512        int i = repeated_lgth;
513        int total_lgth = repeat_count * repeated_lgth;
514        PabloAST * consecutive_i = repeated;
515        while (i * 2 <= total_lgth) {
516            PabloAST * v = consecutive_i;
517            PabloAST * v2 =  pb.createAdvance(v, i);
518            i *= 2;
519            consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "inarow");
520        }       
521        if (i < total_lgth) {
522            PabloAST * v = consecutive_i;
523            consecutive_i = pb.createAnd(v, pb.createAdvance(v, total_lgth - i), "at" + std::to_string(total_lgth) + "inarow");
524        }
525        return consecutive_i;
526}
527
528inline PabloAST * RE_Compiler::reachable(PabloAST *repeated, int repeated_lgth, int repeat_count, PabloBuilder & pb) {
529        int i = repeated_lgth;
530        int total_lgth = repeat_count * repeated_lgth;
531        if (repeat_count == 0) {
532            return repeated;
533        }
534        PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
535        while (i * 2 < total_lgth) {
536            PabloAST * v = reachable_i;
537            PabloAST * v2 =  pb.createAdvance(v, i);
538            i *= 2;
539            reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
540        }       
541        if (i < total_lgth) {
542            PabloAST * v = reachable_i;
543            reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
544        }
545        return reachable_i;
546}
547
548MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, PabloBuilder & pb) {
549    if (isByteLength(repeated) && !DisableLog2BoundedRepetition) {
550        PabloAST * cc = markerVar(compile(repeated, pb));
551        PabloAST * cc_lb = consecutive1(cc, 1, lb, pb);
552        PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), markerPos(marker) == MarkerPosition::FinalMatchByte ? lb : lb - 1);
553        return makeMarker(MarkerPosition::FinalMatchByte, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
554    }
555    // Fall through to general case.
556    while (lb-- != 0) {
557        marker = process(repeated, marker, pb);
558    }
559    return marker;
560}
561
562MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, PabloBuilder & pb) {
563    if (isByteLength(repeated) && ub > 1 && !DisableLog2BoundedRepetition) {
564        // log2 upper bound for fixed length (=1) class
565        // Create a mask of positions reachable within ub from current marker.
566        // Use matchstar, then apply filter.
567        PabloAST * match = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));
568        PabloAST * upperLimitMask = reachable(match, 1, ub, pb);
569        PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));
570        PabloAST * rep_class_var = markerVar(compile(repeated, pb));
571        return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAnd(pb.createMatchStar(cursor, rep_class_var), upperLimitMask, "bounded"));
572    }
573    // Fall through to general case.
574    while (ub-- != 0) {
575        MarkerType a = process(repeated, marker, pb);
576        MarkerType m = marker;
577        AlignMarkers(a, m, pb);
578        marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m), "m"));
579    }
580    return marker;
581}
582
583MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
584    // always use PostPosition markers for unbounded repetition.
585    PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));
586   
587    if (isByteLength(repeated)  && !DisableMatchStar) {
588        PabloAST * cc = markerVar(compile(repeated, pb)); 
589        PabloAST * mstar = SetMod64Approximation ? pb.createMod64MatchStar(base, cc) : pb.createMatchStar(base, cc, "unbounded");
590        return makeMarker(MarkerPosition::InitialPostPositionByte, mstar);
591    }
592    else if (isUnicodeUnitLength(repeated) && !DisableMatchStar && !DisableUnicodeMatchStar) {
593        PabloAST * cc = markerVar(compile(repeated, pb));
594        PabloAST * mstar = SetMod64Approximation ? pb.createMod64MatchStar(base, pb.createOr(mNonFinal, cc)) : pb.createMatchStar(base, pb.createOr(mNonFinal, cc));
595        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(mstar, mFinal, "unbounded"));
596    }
597    else if (mStarDepth > 0){
598       
599        PabloBuilder * outerb = pb.getParent();
600       
601        Assign * starPending = outerb->createAssign("pending", outerb->createZeroes());
602        Assign * starAccum = outerb->createAssign("accum", outerb->createZeroes());
603       
604        mStarDepth++;
605        PabloAST * m1 = pb.createOr(base, starPending);
606        PabloAST * m2 = pb.createOr(base, starAccum);
607        PabloAST * loopComputation = markerVar(AdvanceMarker(process(repeated, makeMarker(MarkerPosition::InitialPostPositionByte, m1), pb), MarkerPosition::InitialPostPositionByte, pb));
608        Next * nextPending = pb.createNext(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
609        Next * nextStarAccum = pb.createNext(starAccum, pb.createOr(loopComputation, m2));
610        mWhileTest = pb.createOr(mWhileTest, nextPending);
611        mLoopVariants.push_back(nextPending);
612        mLoopVariants.push_back(nextStarAccum);
613        mStarDepth--;
614       
615        return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAssign("unbounded", pb.createOr(base, nextStarAccum)));
616    }   
617    else {
618        Assign * whileTest = pb.createAssign("test", base);
619        Assign * whilePending = pb.createAssign("pending", base);
620        Assign * whileAccum = pb.createAssign("accum", base);
621        mWhileTest = pb.createZeroes();
622
623        PabloBuilder wb = PabloBuilder::Create(pb);
624        mStarDepth++;
625
626        PabloAST * loopComputation = markerVar(AdvanceMarker(process(repeated, makeMarker(MarkerPosition::InitialPostPositionByte, whilePending), wb), MarkerPosition::InitialPostPositionByte, wb));
627        Next * nextWhilePending = wb.createNext(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
628        Next * nextWhileAccum = wb.createNext(whileAccum, wb.createOr(loopComputation, whileAccum));
629        Next * nextWhileTest = wb.createNext(whileTest, wb.createOr(mWhileTest, nextWhilePending));
630        mLoopVariants.push_back(nextWhilePending);
631        mLoopVariants.push_back(nextWhileAccum);
632        mLoopVariants.push_back(nextWhileTest);
633        pb.createWhile(nextWhileTest, mLoopVariants, wb);
634        mStarDepth--;
635        mLoopVariants.clear();
636        return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAssign("unbounded", nextWhileAccum));
637    }   
638} // end of namespace re
639}
Note: See TracBrowser for help on using the repository browser.