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

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

First stage of CC_NameMap removal

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