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

Last change on this file since 4978 was 4978, checked in by cameron, 4 years ago

-invert-matches/-v option

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