source: icGREP/icgrep-devel/icgrep/re/re_analysis.cpp @ 5801

Last change on this file since 5801 was 5801, checked in by cameron, 14 months ago

Additional Alphabet analysis and transformation

File size: 14.9 KB
RevLine 
[4393]1#include "re_analysis.h"
[5682]2#include <UCD/unicode_set.h>
[4835]3#include <re/re_cc.h>
4#include <re/re_name.h>
5#include <re/re_start.h>
6#include <re/re_end.h>
7#include <re/re_any.h>
8#include <re/re_seq.h>
9#include <re/re_alt.h>
10#include <re/re_rep.h>
11#include <re/re_diff.h>
12#include <re/re_intersect.h>
13#include <re/re_assertion.h>
[5770]14#include <re/re_group.h>
[5649]15#include <re/re_nullable.h>
[4829]16#include <re/printer_re.h>
[5801]17#include <cc/alphabet.h>
18#include <cc/multiplex_CCs.h>
[4442]19#include <limits.h>
[5649]20#include <llvm/Support/ErrorHandling.h>
[4393]21
[5267]22using namespace llvm;
23
[4393]24namespace re {
[5682]25   
26bool matchesEmptyString(const RE * re) {
27    if (const Alt * alt = dyn_cast<Alt>(re)) {
28        for (const RE * re : *alt) {
29            if (matchesEmptyString(re)) {
30                return true;
31            }
32        }
33        return false;
34    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
35        for (const RE * re : *seq) {
36            if (!matchesEmptyString(re)) {
37                return false;
38            }
39        }
40        return true;
41    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
42        return (rep->getLB() == 0) || matchesEmptyString(rep->getRE());
43    } else if (isa<Start>(re)) {
44        return true;
45    } else if (isa<End>(re)) {
46        return true;
47    } else if (isa<Assertion>(re)) {
48        return false;
49    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
50        return matchesEmptyString(diff->getLH()) && !matchesEmptyString(diff->getRH());
51    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
52        return matchesEmptyString(e->getLH()) && matchesEmptyString(e->getRH());
53    } else if (isa<Any>(re)) {
54        return false;
55    } else if (isa<CC>(re)) {
56        return false;
[5770]57    } else if (const Group * g = dyn_cast<Group>(re)) {
58        return matchesEmptyString(g->getRE());
[5682]59    } else if (const Name * n = dyn_cast<Name>(re)) {
60        return matchesEmptyString(n->getDefinition());
61    }
62    return false; // otherwise
63}
[4393]64
[5682]65const CC* matchableCodepoints(const RE * re) {
66    if (const CC * cc = dyn_cast<CC>(re)) {
67        return cc;
68    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
69        CC * matchable = makeCC();
70        for (const RE * re : *alt) {
71            matchable = makeCC(matchable, matchableCodepoints(re));
72        }
73        return matchable;
74    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
75        CC * matchable = makeCC();
76        bool pastCC = false;
77        for (const RE * re : *seq) {
78            if (pastCC) {
79                if (!(isa<End>(re) || matchesEmptyString(re))) return makeCC();
80            }
81            else if (isa<End>(re)) return makeCC();
82            else {
83                matchable = makeCC(matchable, matchableCodepoints(re));
84                pastCC = !matchesEmptyString(re);
85            }
86        }
87        return matchable;
88    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
89        if ((rep->getLB() <= 1) || matchesEmptyString(rep->getRE())) {
90            return matchableCodepoints(rep->getRE());
91        }
92        else return makeCC();
93    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
94        return subtractCC(matchableCodepoints(diff->getLH()), matchableCodepoints(diff->getRH()));
95    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
[5727]96        return intersectCC(matchableCodepoints(e->getLH()), matchableCodepoints(e->getRH()));
[5682]97    } else if (isa<Any>(re)) {
98        return makeCC(0, 0x10FFFF);
99    } else if (const Name * n = dyn_cast<Name>(re)) {
100        return matchableCodepoints(n->getDefinition());
101    }
102    return makeCC(); // otherwise = Start, End, Assertion
103}
104
105
106
[4829]107bool isByteLength(const RE * re) {
108    if (const Alt * alt = dyn_cast<Alt>(re)) {
109        for (const RE * re : *alt) {
[4415]110            if (!isByteLength(re)) {
111                return false;
112            }
[4393]113        }
114        return true;
[4835]115    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
[4393]116        return (seq->size() == 1) && isByteLength(&seq[0]);
[4835]117    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
[4393]118        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
[4835]119    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
[4393]120        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
[4835]121    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
[4393]122        return isByteLength(e->getLH()) && isByteLength(e->getRH());
[5801]123    } else if (const CC * cc = dyn_cast<CC>(re)) {
124        const cc::Alphabet * a = cc->getAlphabet();
125        if (a == &cc::Unicode) return (cc->max_codepoint() <= 0x7F);
126        else if (a == &cc::Byte) return true;
127        else if (isa<cc::MultiplexedAlphabet>(a)) {
128            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
129            if (srcA == &cc::Byte) {
130                return true;
131//            } else if (srcA == &cc::Unicode) {
132//                return cast<cc::MultiplexedAlphabet>(a)->invertCC(cc)->max_codepoint() <= 0x7F;
133            } else return (a == &cc::Byte);
134        }
135        return false;
[4835]136    } else if (const Name * n = dyn_cast<Name>(re)) {
[5801]137        if (n->getType() == Name::Type::ZeroWidth) {
138            return false;
[5080]139        }
[5801]140        return isByteLength(n->getDefinition());
[4393]141    }
142    return false; // otherwise
143}
144
[4829]145bool isUnicodeUnitLength(const RE * re) {
146    if (const Alt * alt = dyn_cast<Alt>(re)) {
147        for (const RE * re : *alt) {
[4415]148            if (!isUnicodeUnitLength(re)) {
149                return false;
150            }
[4393]151        }
152        return true;
[4835]153    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
[4393]154        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
[4835]155    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
[4393]156        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
[4835]157    } else if (isa<Assertion>(re)) {
[4405]158        return false;
[4835]159    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
[4393]160        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
[4835]161    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
[4393]162        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
[4835]163    } else if (isa<Any>(re)) {
[4415]164        return true;
[5557]165    } else if (isa<CC>(re)) {
166        return true;
[4835]167    } else if (const Name * n = dyn_cast<Name>(re)) {
[4393]168        // Eventually names might be set up for not unit length items.
[5080]169        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
170            return true;
[5267]171        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
[5080]172            return isUnicodeUnitLength(n->getDefinition());
173        }
174        return false;
[4393]175    }
176    return false; // otherwise
177}
[4829]178
179std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
180    if (const Alt * alt = dyn_cast<Alt>(re)) {
[5267]181        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
[4829]182        for (const RE * re : *alt) {
183            auto r = getUnicodeUnitLengthRange(re);
184            range.first = std::min<int>(range.first, r.first);
185            range.second = std::max<int>(range.second, r.second);
186        }
187        return range;
188    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
189        std::pair<int, int> range = std::make_pair(0, 0);
190        for (const RE * re : *seq) {
191            auto tmp = getUnicodeUnitLengthRange(re);
[5267]192            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
[4829]193                range.first += tmp.first;
194            } else {
[5267]195                range.first = INT_MAX;
[4829]196            }
[5267]197            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
[4829]198                range.second += tmp.second;
199            } else {
[5267]200                range.second = INT_MAX;
[4829]201            }
202        }
203        return range;
204    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
205        auto range = getUnicodeUnitLengthRange(rep->getRE());
[5267]206        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
[4829]207            range.first *= rep->getLB();
208        } else {
[5267]209            range.first = INT_MAX;
[4829]210        }
[5267]211        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
[4829]212            range.second *= rep->getUB();
213        } else {
[5267]214            range.second = INT_MAX;
[4829]215        }
216        return range;
217    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
218        return std::make_pair(0, 0);
219    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
220        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
221        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
222        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
223    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
224        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
225        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
226        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
[5557]227    } else if (isa<CC>(re)) {
228        return std::make_pair(1, 1);
[4829]229    } else if (const Name * n = dyn_cast<Name>(re)) {
230        // Eventually names might be set up for not unit length items.
231        switch (n->getType()) {
232            case Name::Type::Byte:
233            case Name::Type::Unicode:
234            case Name::Type::UnicodeProperty:
235                return std::make_pair(1, 1);
[5080]236            case Name::Type::Capture:
237            case Name::Type::Reference:
238                return getUnicodeUnitLengthRange(n->getDefinition());
[5091]239            case Name::Type::ZeroWidth:
240                return std::make_pair(0, 0);
[4829]241            case Name::Type::Unknown:
[5267]242                return std::make_pair(0, INT_MAX);
[4829]243        }
[5091]244    } 
[4829]245    return std::make_pair(1, 1);
246}
[4442]247   
248int minMatchLength(RE * re) {
249    if (Alt * alt = dyn_cast<Alt>(re)) {
250        int minAltLength = INT_MAX;
251        for (RE * re : *alt) {
252            minAltLength = std::min(minAltLength, minMatchLength(re));
253        }
254        return minAltLength;
[5267]255    } else if (Seq * seq = dyn_cast<Seq>(re)) {
[4442]256        int minSeqLength = 0;
257        for (RE * re : *seq) {
258            minSeqLength += minMatchLength(re);
259        }
260        return minSeqLength;
[5267]261    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4442]262        if (rep->getLB() == 0) return 0;
263        else return (rep->getLB()) * minMatchLength(rep->getRE());
[5267]264    } else if (isa<Assertion>(re)) {
[4442]265        return 0;
[5267]266    } else if (Diff * diff = dyn_cast<Diff>(re)) {
[4442]267        return minMatchLength(diff->getLH());
[5267]268    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
[4442]269        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
[5267]270    } else if (isa<Any>(re)) {
[4442]271        return 1;
[5557]272    } else if (isa<CC>(re)) {
273        return 1;
[5233]274    } else if (const Name * n = dyn_cast<Name>(re)) {
275        // Eventually names might be set up for not unit length items.
[5080]276        switch (n->getType()) {
277            case Name::Type::Byte:
278            case Name::Type::Unicode:
279            case Name::Type::UnicodeProperty:
280                return 1;
281            case Name::Type::Capture:
282            case Name::Type::Reference:
283                return minMatchLength(n->getDefinition());
[5233]284            default:
[5080]285                return 0;
286        }
[4442]287    }
288    return 0; // otherwise
[4393]289}
[5649]290   
[5604]291//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
292bool unitBoundedRep(const RE * re) {
293    if (const Alt * alt = dyn_cast<Alt>(re)) {
294        for (const RE * re : *alt) {
295            if (unitBoundedRep(re)) {
296                return true;
297            }
298        }
299        return false;
300    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
301        for (const RE * re : *seq) {
302            if (unitBoundedRep(re)) {
303                return true;
304            }
305        }
306        return false;
307    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
308        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
309            return false;
310        } else {
311            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
312        }
313    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
314        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
315    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
316        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
317    } else if (const Name * n = dyn_cast<Name>(re)) {
318        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
319            return unitBoundedRep(n->getDefinition());
320        }
321        return false;
322    }
323    return false; // otherwise
324 
325}
[4442]326
[5604]327//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
328bool isTypeForLocal(const RE * re) {
[5720]329    if (const Name * n = dyn_cast<Name>(re)) {
330        return isTypeForLocal(n->getDefinition());
331    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
[5604]332        for (const RE * re : *alt) {
333            if (!isTypeForLocal(re)) {
334                return false;
335            }
336        }
337        return true;
338    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
[5736]339        if (seq->empty()) return false;
[5723]340        for (const RE * re : *seq) {
341            if (!isTypeForLocal(re)) {
342                return false;
343            }
[5604]344        }
345        return true;
346    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
347        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
348            return false;
[5723]349        }
[5604]350        return true;
351    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
352        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
353    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
354        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
355    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
356        return false;
357    }
358    return true; // otherwise
[4442]359}
[5604]360
[5723]361bool hasAssertion(const RE * re) {
362    if (isa<CC>(re)) {
363        return false;
364    } else if (const Name * n = dyn_cast<Name>(re)) {
365        return hasAssertion(n->getDefinition());
366    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
367        for (const RE * re : *alt) {
368            if (hasAssertion(re)) return true;
369        }
370        return false;
371    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
372        for (const RE * re : *seq) {
373            if (hasAssertion(re)) return true;
374        }
375        return false;
376    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
377        return hasAssertion(rep->getRE());
378    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
379        return hasAssertion(diff->getLH()) || hasAssertion(diff->getRH());
380    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
381        return hasAssertion(e->getLH()) || hasAssertion(e->getRH());
382    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
383        return true;
[5770]384    } else if (const Group * g = dyn_cast<Group>(re)) {
385        if ((g->getMode() == Group::Mode::GraphemeMode) && (g->getSense() == Group::Sense::On)) {
386            return true;
387        }
388        else {
389            return hasAssertion(g->getRE());
390        }
[5723]391    }
392    else llvm_unreachable("Unknown RE type");
393}
394
[5649]395void UndefinedNameError(const Name * n) {
396    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
[5604]397}
[5649]398}
Note: See TracBrowser for help on using the repository browser.