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

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

Back-up check in

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