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

Last change on this file was 5736, checked in by cameron, 5 days ago

Bug fixes for empty sequences

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