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

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

Added union/diff/intersection functionality to RE_Compiler. Removed toUTF8 pass in favour of using the UCD_Compiler.

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