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

Last change on this file since 5792 was 5770, checked in by cameron, 18 months ago

Restructure to eliminate unnecessary dependencies on RegExpCompiler? and UCDLIB

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