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

Last change on this file was 5835, checked in by nmedfort, 6 weeks ago

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File size: 14.8 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) {
126            return (cc->max_codepoint() <= 0x7F);
127        } else if (a == &cc::Byte) {
128            return true;
129        } else if (isa<cc::MultiplexedAlphabet>(a)) {
130            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
131            if (srcA == &cc::Byte) {
132                return true;
133//            } else if (srcA == &cc::Unicode) {
134//                return cast<cc::MultiplexedAlphabet>(a)->invertCC(cc)->max_codepoint() <= 0x7F;
135            } else return (a == &cc::Byte);
136        }
137        return false;
138    } else if (const Name * n = dyn_cast<Name>(re)) {
139        if (n->getType() == Name::Type::ZeroWidth) {
140            return false;
141        }
142        return isByteLength(n->getDefinition());
143    }
144    return false; // otherwise
145}
146
147bool isUnicodeUnitLength(const RE * re) {
148    if (const Alt * alt = dyn_cast<Alt>(re)) {
149        for (const RE * re : *alt) {
150            if (!isUnicodeUnitLength(re)) {
151                return false;
152            }
153        }
154        return true;
155    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
156        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
157    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
158        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
159    } else if (isa<Assertion>(re)) {
160        return false;
161    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
162        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
163    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
164        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
165    } else if (isa<Any>(re)) {
166        return true;
167    } else if (isa<CC>(re)) {
168        return true;
169    } else if (const Name * n = dyn_cast<Name>(re)) {
170        // Eventually names might be set up for not unit length items.
171        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty) {
172            return true;
173        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
174            return isUnicodeUnitLength(n->getDefinition());
175        }
176        return false;
177    }
178    return false; // otherwise
179}
180
181std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
182    if (const Alt * alt = dyn_cast<Alt>(re)) {
183        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
184        for (const RE * re : *alt) {
185            auto r = getUnicodeUnitLengthRange(re);
186            range.first = std::min<int>(range.first, r.first);
187            range.second = std::max<int>(range.second, r.second);
188        }
189        return range;
190    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
191        std::pair<int, int> range = std::make_pair(0, 0);
192        for (const RE * re : *seq) {
193            auto tmp = getUnicodeUnitLengthRange(re);
194            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
195                range.first += tmp.first;
196            } else {
197                range.first = INT_MAX;
198            }
199            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
200                range.second += tmp.second;
201            } else {
202                range.second = INT_MAX;
203            }
204        }
205        return range;
206    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
207        auto range = getUnicodeUnitLengthRange(rep->getRE());
208        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
209            range.first *= rep->getLB();
210        } else {
211            range.first = INT_MAX;
212        }
213        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
214            range.second *= rep->getUB();
215        } else {
216            range.second = INT_MAX;
217        }
218        return range;
219    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
220        return std::make_pair(0, 0);
221    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
222        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
223        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
224        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
225    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
226        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
227        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
228        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
229    } else if (isa<CC>(re)) {
230        return std::make_pair(1, 1);
231    } else if (const Name * n = dyn_cast<Name>(re)) {
232        // Eventually names might be set up for not unit length items.
233        switch (n->getType()) {
234            case Name::Type::Unicode:
235            case Name::Type::UnicodeProperty:
236                return std::make_pair(1, 1);
237            case Name::Type::Capture:
238            case Name::Type::Reference:
239                return getUnicodeUnitLengthRange(n->getDefinition());
240            case Name::Type::ZeroWidth:
241                return std::make_pair(0, 0);
242            case Name::Type::Unknown:
243                return std::make_pair(0, INT_MAX);
244        }
245    } 
246    return std::make_pair(1, 1);
247}
248   
249int minMatchLength(RE * re) {
250    if (Alt * alt = dyn_cast<Alt>(re)) {
251        int minAltLength = INT_MAX;
252        for (RE * re : *alt) {
253            minAltLength = std::min(minAltLength, minMatchLength(re));
254        }
255        return minAltLength;
256    } else if (Seq * seq = dyn_cast<Seq>(re)) {
257        int minSeqLength = 0;
258        for (RE * re : *seq) {
259            minSeqLength += minMatchLength(re);
260        }
261        return minSeqLength;
262    } else if (Rep * rep = dyn_cast<Rep>(re)) {
263        if (rep->getLB() == 0) return 0;
264        else return (rep->getLB()) * minMatchLength(rep->getRE());
265    } else if (isa<Assertion>(re)) {
266        return 0;
267    } else if (Diff * diff = dyn_cast<Diff>(re)) {
268        return minMatchLength(diff->getLH());
269    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
270        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
271    } else if (isa<Any>(re)) {
272        return 1;
273    } else if (isa<CC>(re)) {
274        return 1;
275    } else if (const Name * n = dyn_cast<Name>(re)) {
276        // Eventually names might be set up for not unit length items.
277        switch (n->getType()) {
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.