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

Last change on this file since 5682 was 5682, checked in by cameron, 20 months ago

String property regular expression support, including special cases for null and reflexive sets

File size: 12.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_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(diff->getLH()), matchableCodepoints(diff->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 Alt * alt = dyn_cast<Alt>(re)) {
316        for (const RE * re : *alt) {
317            if (!isTypeForLocal(re)) {
318                return false;
319            }
320        }
321        return true;
322    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
323    for (const RE * re : *seq) {
324        if (!isTypeForLocal(re)) {
325            return false;
326        }
327    }
328        return true;
329    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
330        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
331            return false;
332        } 
333        return true;
334    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
335        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
336    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
337        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
338    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
339        return false;
340    }
341    return true; // otherwise
342}
343
344void UndefinedNameError(const Name * n) {
345    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
346}
347}
Note: See TracBrowser for help on using the repository browser.