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

Last change on this file since 5910 was 5910, checked in by cameron, 11 months ago

hasEndAnchor

File size: 18.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/to_utf8.h>
17#include <re/printer_re.h>
18#include <cc/alphabet.h>
19#include <cc/multiplex_CCs.h>
20#include <limits.h>
21#include <llvm/Support/ErrorHandling.h>
22#include <llvm/Support/raw_ostream.h>
23
24using namespace llvm;
25
26namespace re {
27   
28bool matchesEmptyString(const RE * re) {
29    if (const Alt * alt = dyn_cast<Alt>(re)) {
30        for (const RE * re : *alt) {
31            if (matchesEmptyString(re)) {
32                return true;
33            }
34        }
35        return false;
36    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
37        for (const RE * re : *seq) {
38            if (!matchesEmptyString(re)) {
39                return false;
40            }
41        }
42        return true;
43    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
44        return (rep->getLB() == 0) || matchesEmptyString(rep->getRE());
45    } else if (isa<Start>(re)) {
46        return true;
47    } else if (isa<End>(re)) {
48        return true;
49    } else if (isa<Assertion>(re)) {
50        return false;
51    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
52        return matchesEmptyString(diff->getLH()) && !matchesEmptyString(diff->getRH());
53    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
54        return matchesEmptyString(e->getLH()) && matchesEmptyString(e->getRH());
55    } else if (isa<Any>(re)) {
56        return false;
57    } else if (isa<CC>(re)) {
58        return false;
59    } else if (const Group * g = dyn_cast<Group>(re)) {
60        return matchesEmptyString(g->getRE());
61    } else if (const Name * n = dyn_cast<Name>(re)) {
62        return matchesEmptyString(n->getDefinition());
63    }
64    return false; // otherwise
65}
66
67const CC* matchableCodepoints(const RE * re) {
68    if (const CC * cc = dyn_cast<CC>(re)) {
69        return cc;
70    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
71        CC * matchable = makeCC();
72        for (const RE * re : *alt) {
73            matchable = makeCC(matchable, matchableCodepoints(re));
74        }
75        return matchable;
76    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
77        CC * matchable = makeCC();
78        bool pastCC = false;
79        for (const RE * re : *seq) {
80            if (pastCC) {
81                if (!(isa<End>(re) || matchesEmptyString(re))) return makeCC();
82            }
83            else if (isa<End>(re)) return makeCC();
84            else {
85                matchable = makeCC(matchable, matchableCodepoints(re));
86                pastCC = !matchesEmptyString(re);
87            }
88        }
89        return matchable;
90    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
91        if ((rep->getLB() <= 1) || matchesEmptyString(rep->getRE())) {
92            return matchableCodepoints(rep->getRE());
93        }
94        else return makeCC();
95    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
96        return subtractCC(matchableCodepoints(diff->getLH()), matchableCodepoints(diff->getRH()));
97    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
98        return intersectCC(matchableCodepoints(e->getLH()), matchableCodepoints(e->getRH()));
99    } else if (isa<Any>(re)) {
100        return makeCC(0, 0x10FFFF);
101    } else if (const Name * n = dyn_cast<Name>(re)) {
102        return matchableCodepoints(n->getDefinition());
103    }
104    return makeCC(); // otherwise = Start, End, Assertion
105}
106
107
108
109bool isByteLength(const RE * re) {
110    if (const Alt * alt = dyn_cast<Alt>(re)) {
111        for (const RE * re : *alt) {
112            if (!isByteLength(re)) {
113                return false;
114            }
115        }
116        return true;
117    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
118        bool byteLengthSeen = false;
119        for (const RE * e : *seq) {
120            if (isa<Assertion>(e)) continue;
121            else if (byteLengthSeen) return false;
122            else if (isByteLength(e)) byteLengthSeen = true;
123            else return false;
124        }
125        return byteLengthSeen;
126    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
127        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
128    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
129        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
130    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
131        return isByteLength(e->getLH()) && isByteLength(e->getRH());
132    } else if (const CC * cc = dyn_cast<CC>(re)) {
133        const cc::Alphabet * a = cc->getAlphabet();
134        if (a == &cc::Unicode) {
135            return (cc->max_codepoint() <= 0x7F);
136        } else if (a == &cc::Byte) {
137            return true;
138        } else if (isa<cc::MultiplexedAlphabet>(a)) {
139            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
140            if (srcA == &cc::Byte) {
141                return true;
142//            } else if (srcA == &cc::Unicode) {
143//                return cast<cc::MultiplexedAlphabet>(a)->invertCC(cc)->max_codepoint() <= 0x7F;
144            } else return (a == &cc::Byte);
145        }
146        return false;
147    } else if (const Name * n = dyn_cast<Name>(re)) {
148        if (n->getType() == Name::Type::ZeroWidth) {
149            return false;
150        }
151        return isByteLength(n->getDefinition());
152    }
153    return false; // otherwise
154}
155
156bool isUnicodeUnitLength(const RE * re) {
157    if (const Alt * alt = dyn_cast<Alt>(re)) {
158        for (const RE * re : *alt) {
159            if (!isUnicodeUnitLength(re)) {
160                return false;
161            }
162        }
163        return true;
164    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
165        bool unitLengthSeen = false;
166        for (const RE * e : *seq) {
167            if (isa<Assertion>(e)) continue;
168            else if (unitLengthSeen) return false;
169            else if (isUnicodeUnitLength(e)) unitLengthSeen = true;
170            else return false;
171        }
172        return unitLengthSeen;
173    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
174        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
175    } else if (isa<Assertion>(re)) {
176        return false;
177    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
178        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
179    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
180        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
181    } else if (isa<Any>(re)) {
182        return true;
183    } else if (isa<CC>(re)) {
184        return true;
185    } else if (const Name * n = dyn_cast<Name>(re)) {
186        // Eventually names might be set up for not unit length items.
187        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty) {
188            return true;
189        } else if (n->getType() == Name::Type::ZeroWidth) {
190            return false;
191        }
192        return isUnicodeUnitLength(n->getDefinition());
193    }
194    return false; // otherwise
195}
196
197std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
198    if (const Alt * alt = dyn_cast<Alt>(re)) {
199        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
200        for (const RE * re : *alt) {
201            auto r = getUnicodeUnitLengthRange(re);
202            range.first = std::min<int>(range.first, r.first);
203            range.second = std::max<int>(range.second, r.second);
204        }
205        return range;
206    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
207        std::pair<int, int> range = std::make_pair(0, 0);
208        for (const RE * re : *seq) {
209            auto tmp = getUnicodeUnitLengthRange(re);
210            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
211                range.first += tmp.first;
212            } else {
213                range.first = INT_MAX;
214            }
215            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
216                range.second += tmp.second;
217            } else {
218                range.second = INT_MAX;
219            }
220        }
221        return range;
222    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
223        auto range = getUnicodeUnitLengthRange(rep->getRE());
224        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
225            range.first *= rep->getLB();
226        } else {
227            range.first = INT_MAX;
228        }
229        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
230            range.second *= rep->getUB();
231        } else {
232            range.second = INT_MAX;
233        }
234        return range;
235    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
236        return std::make_pair(0, 0);
237    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
238        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
239        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
240        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
241    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
242        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
243        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
244        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
245    } else if (isa<CC>(re)) {
246        return std::make_pair(1, 1);
247    } else if (const Name * n = dyn_cast<Name>(re)) {
248        // Eventually names might be set up for not unit length items.
249        switch (n->getType()) {
250            case Name::Type::Unicode:
251            case Name::Type::UnicodeProperty:
252                return std::make_pair(1, 1);
253            case Name::Type::Capture:
254            case Name::Type::Reference:
255                return getUnicodeUnitLengthRange(n->getDefinition());
256            case Name::Type::ZeroWidth:
257                return std::make_pair(0, 0);
258            case Name::Type::Unknown:
259                return std::make_pair(0, INT_MAX);
260        }
261    } 
262    return std::make_pair(1, 1);
263}
264   
265int minMatchLength(RE * re) {
266    if (Alt * alt = dyn_cast<Alt>(re)) {
267        int minAltLength = INT_MAX;
268        for (RE * re : *alt) {
269            minAltLength = std::min(minAltLength, minMatchLength(re));
270        }
271        return minAltLength;
272    } else if (Seq * seq = dyn_cast<Seq>(re)) {
273        int minSeqLength = 0;
274        for (RE * re : *seq) {
275            minSeqLength += minMatchLength(re);
276        }
277        return minSeqLength;
278    } else if (Rep * rep = dyn_cast<Rep>(re)) {
279        if (rep->getLB() == 0) return 0;
280        else return (rep->getLB()) * minMatchLength(rep->getRE());
281    } else if (isa<Assertion>(re)) {
282        return 0;
283    } else if (Diff * diff = dyn_cast<Diff>(re)) {
284        return minMatchLength(diff->getLH());
285    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
286        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
287    } else if (isa<Any>(re)) {
288        return 1;
289    } else if (isa<CC>(re)) {
290        return 1;
291    } else if (const Name * n = dyn_cast<Name>(re)) {
292        // Eventually names might be set up for not unit length items.
293        switch (n->getType()) {
294            case Name::Type::Unicode:
295            case Name::Type::UnicodeProperty:
296                return 1;
297            case Name::Type::Capture:
298            case Name::Type::Reference:
299                return minMatchLength(n->getDefinition());
300            default:
301                return 0;
302        }
303    }
304    return 0; // otherwise
305}
306   
307//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
308bool unitBoundedRep(const RE * re) {
309    if (const Alt * alt = dyn_cast<Alt>(re)) {
310        for (const RE * re : *alt) {
311            if (unitBoundedRep(re)) {
312                return true;
313            }
314        }
315        return false;
316    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
317        for (const RE * re : *seq) {
318            if (unitBoundedRep(re)) {
319                return true;
320            }
321        }
322        return false;
323    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
324        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
325            return false;
326        } else {
327            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
328        }
329    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
330        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
331    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
332        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
333    } else if (const Name * n = dyn_cast<Name>(re)) {
334        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
335            return unitBoundedRep(n->getDefinition());
336        }
337        return false;
338    }
339    return false; // otherwise
340 
341}
342
343//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
344bool isTypeForLocal(const RE * re) {
345    if (const Name * n = dyn_cast<Name>(re)) {
346        return isTypeForLocal(n->getDefinition());
347    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
348        for (const RE * re : *alt) {
349            if (!isTypeForLocal(re)) {
350                return false;
351            }
352        }
353        return true;
354    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
355        if (seq->empty()) return false;
356        for (const RE * re : *seq) {
357            if (!isTypeForLocal(re)) {
358                return false;
359            }
360        }
361        return true;
362    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
363        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
364            return false;
365        }
366        return true;
367    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
368        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
369    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
370        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
371    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
372        return false;
373    }
374    return true; // otherwise
375}
376
377bool hasAssertion(const RE * re) {
378    if (isa<CC>(re)) {
379        return false;
380    } else if (const Name * n = dyn_cast<Name>(re)) {
381        return hasAssertion(n->getDefinition());
382    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
383        for (const RE * re : *alt) {
384            if (hasAssertion(re)) return true;
385        }
386        return false;
387    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
388        for (const RE * re : *seq) {
389            if (hasAssertion(re)) return true;
390        }
391        return false;
392    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
393        return hasAssertion(rep->getRE());
394    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
395        return hasAssertion(diff->getLH()) || hasAssertion(diff->getRH());
396    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
397        return hasAssertion(e->getLH()) || hasAssertion(e->getRH());
398    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
399        return true;
400    } else if (const Group * g = dyn_cast<Group>(re)) {
401        if ((g->getMode() == Group::Mode::GraphemeMode) && (g->getSense() == Group::Sense::On)) {
402            return true;
403        }
404        else {
405            return hasAssertion(g->getRE());
406        }
407    }
408    else llvm_unreachable("Unknown RE type");
409}
410
411struct ByteTestComplexity {
412   
413    void gatherTests(RE * re);
414   
415    UCD::UnicodeSet equalityTests;
416    UCD::UnicodeSet lessThanTests;
417    unsigned testCount;
418    unsigned testLimit;
419};
420
421void ByteTestComplexity::gatherTests(RE * re) {
422    if (CC * cc = dyn_cast<CC>(re)) {
423        if (cc->getAlphabet() == &cc::Unicode) {
424            gatherTests(toUTF8(re));
425        } else {
426            for (const auto range : *cc) {
427                const auto lo = re::lo_codepoint(range);
428                const auto hi = re::hi_codepoint(range);
429                if (lo == hi) {
430                    if (!equalityTests.contains(lo)) {
431                        equalityTests.insert(lo);
432                        testCount++;
433                    }
434                } else {
435                    if (lo > 0) {
436                        if (!lessThanTests.contains(lo)) {
437                            lessThanTests.insert(lo);
438                            testCount++;
439                        }
440                    }
441                    if (hi < 0xFF) {
442                        if (!lessThanTests.contains(hi+1)) {
443                            lessThanTests.insert(hi+1);
444                            testCount++;
445                        }
446                    }
447                }
448                if (testCount > testLimit) return;
449            }
450        }
451    } else if (const Name * n = dyn_cast<Name>(re)) {
452        gatherTests(n->getDefinition());
453    } else if (Alt * alt = dyn_cast<Alt>(re)) {
454        for (RE * item : *alt) {
455            gatherTests(item);
456        }
457    } else if (Seq * seq = dyn_cast<Seq>(re)) {
458        for (RE * item : *seq) {
459            gatherTests(item);
460        }
461    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
462        gatherTests(a->getAsserted());
463    } else if (Rep * rep = dyn_cast<Rep>(re)) {
464        gatherTests(rep->getRE());
465    } else if (Diff * diff = dyn_cast<Diff>(re)) {
466        gatherTests(diff->getLH());
467        gatherTests(diff->getRH());
468    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
469        gatherTests(e->getLH());
470        gatherTests(e->getRH());
471    } else if (Group * g = dyn_cast<Group>(re)) {
472        gatherTests(g->getRE());
473    }
474}
475
476bool byteTestsWithinLimit(RE * re, unsigned limit) {
477    ByteTestComplexity btc_object;
478    btc_object.testCount = 0;
479    btc_object.testLimit = limit;
480    btc_object.gatherTests(re);
481    return btc_object.testCount <= btc_object.testLimit;
482}
483
484bool hasTriCCwithinLimit(RE * r, unsigned byteCClimit, RE * & prefixRE, RE * & suffixRE) {
485    if (Seq * seq = dyn_cast<Seq>(r)) {
486        if (seq->size() < 4) return false;
487        prefixRE = makeSeq(seq->begin(), seq->begin()+3);
488        if (byteTestsWithinLimit(prefixRE, byteCClimit)) {
489            suffixRE = makeSeq(seq->begin()+3, seq->end());
490            return true;
491        }
492        return false;
493    }
494    return false;
495}
496
497   
498bool hasEndAnchor(const RE * re) {
499    if (const Alt * alt = dyn_cast<Alt>(re)) {
500        for (const RE * re : *alt) {
501            if (!hasEndAnchor(re)) {
502                return false;
503            }
504        }
505        return true;
506    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
507        return (!seq->empty()) && isa<End>(seq->back());
508    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
509        return hasEndAnchor(rep->getRE());
510    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
511        return hasEndAnchor(diff->getLH()) && !hasEndAnchor(diff->getRH());
512    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
513        return hasEndAnchor(e->getLH()) && hasEndAnchor(e->getRH());
514    } else if (isa<End>(re)) {
515        return true;
516    }
517    return false; // otherwise
518}
519   
520
521void UndefinedNameError(const Name * n) {
522    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
523}
524}
Note: See TracBrowser for help on using the repository browser.