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

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

Additional Alphabet analysis and transformation

File size: 14.9 KB
Line 
1#include "re_analysis.h"
2#include <UCD/unicode_set.h>
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>
14#include <re/re_group.h>
15#include <re/re_nullable.h>
16#include <re/printer_re.h>
17#include <cc/alphabet.h>
18#include <cc/multiplex_CCs.h>
19#include <limits.h>
20#include <llvm/Support/ErrorHandling.h>
21
22using namespace llvm;
23
24namespace re {
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;
57    } else if (const Group * g = dyn_cast<Group>(re)) {
58        return matchesEmptyString(g->getRE());
59    } else if (const Name * n = dyn_cast<Name>(re)) {
60        return matchesEmptyString(n->getDefinition());
61    }
62    return false; // otherwise
63}
64
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)) {
96        return intersectCC(matchableCodepoints(e->getLH()), matchableCodepoints(e->getRH()));
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
107bool isByteLength(const RE * re) {
108    if (const Alt * alt = dyn_cast<Alt>(re)) {
109        for (const RE * re : *alt) {
110            if (!isByteLength(re)) {
111                return false;
112            }
113        }
114        return true;
115    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
116        return (seq->size() == 1) && isByteLength(&seq[0]);
117    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
118        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
119    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
120        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
121    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
122        return isByteLength(e->getLH()) && isByteLength(e->getRH());
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;
136    } else if (const Name * n = dyn_cast<Name>(re)) {
137        if (n->getType() == Name::Type::ZeroWidth) {
138            return false;
139        }
140        return isByteLength(n->getDefinition());
141    }
142    return false; // otherwise
143}
144
145bool isUnicodeUnitLength(const RE * re) {
146    if (const Alt * alt = dyn_cast<Alt>(re)) {
147        for (const RE * re : *alt) {
148            if (!isUnicodeUnitLength(re)) {
149                return false;
150            }
151        }
152        return true;
153    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
154        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
155    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
156        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
157    } else if (isa<Assertion>(re)) {
158        return false;
159    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
160        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
161    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
162        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
163    } else if (isa<Any>(re)) {
164        return true;
165    } else if (isa<CC>(re)) {
166        return true;
167    } else if (const Name * n = dyn_cast<Name>(re)) {
168        // Eventually names might be set up for not unit length items.
169        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
170            return true;
171        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
172            return isUnicodeUnitLength(n->getDefinition());
173        }
174        return false;
175    }
176    return false; // otherwise
177}
178
179std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
180    if (const Alt * alt = dyn_cast<Alt>(re)) {
181        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
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);
192            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
193                range.first += tmp.first;
194            } else {
195                range.first = INT_MAX;
196            }
197            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
198                range.second += tmp.second;
199            } else {
200                range.second = INT_MAX;
201            }
202        }
203        return range;
204    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
205        auto range = getUnicodeUnitLengthRange(rep->getRE());
206        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
207            range.first *= rep->getLB();
208        } else {
209            range.first = INT_MAX;
210        }
211        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
212            range.second *= rep->getUB();
213        } else {
214            range.second = INT_MAX;
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));
227    } else if (isa<CC>(re)) {
228        return std::make_pair(1, 1);
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);
236            case Name::Type::Capture:
237            case Name::Type::Reference:
238                return getUnicodeUnitLengthRange(n->getDefinition());
239            case Name::Type::ZeroWidth:
240                return std::make_pair(0, 0);
241            case Name::Type::Unknown:
242                return std::make_pair(0, INT_MAX);
243        }
244    } 
245    return std::make_pair(1, 1);
246}
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;
255    } else if (Seq * seq = dyn_cast<Seq>(re)) {
256        int minSeqLength = 0;
257        for (RE * re : *seq) {
258            minSeqLength += minMatchLength(re);
259        }
260        return minSeqLength;
261    } else if (Rep * rep = dyn_cast<Rep>(re)) {
262        if (rep->getLB() == 0) return 0;
263        else return (rep->getLB()) * minMatchLength(rep->getRE());
264    } else if (isa<Assertion>(re)) {
265        return 0;
266    } else if (Diff * diff = dyn_cast<Diff>(re)) {
267        return minMatchLength(diff->getLH());
268    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
269        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
270    } else if (isa<Any>(re)) {
271        return 1;
272    } else if (isa<CC>(re)) {
273        return 1;
274    } else if (const Name * n = dyn_cast<Name>(re)) {
275        // Eventually names might be set up for not unit length items.
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());
284            default:
285                return 0;
286        }
287    }
288    return 0; // otherwise
289}
290   
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}
326
327//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
328bool isTypeForLocal(const RE * re) {
329    if (const Name * n = dyn_cast<Name>(re)) {
330        return isTypeForLocal(n->getDefinition());
331    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
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)) {
339        if (seq->empty()) return false;
340        for (const RE * re : *seq) {
341            if (!isTypeForLocal(re)) {
342                return false;
343            }
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;
349        }
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
359}
360
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;
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        }
391    }
392    else llvm_unreachable("Unknown RE type");
393}
394
395void UndefinedNameError(const Name * n) {
396    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
397}
398}
Note: See TracBrowser for help on using the repository browser.