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

Last change on this file since 5045 was 5045, checked in by xuedongx, 3 years ago

Support over UTF-16 representation of Unicode

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