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

Last change on this file was 6170, checked in by cameron, 2 weeks ago

RE Transformation names and printing

File size: 25.1 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#include <set>
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
107bool isRequireNonFinal(const RE * re, bool checkByteLength) {
108    if (checkByteLength) {
109        bool allCcByteLength = isAllCcByteLength(re);
110        if (allCcByteLength) {
111            return false;
112        }
113    }
114
115    if (const Alt * alt = dyn_cast<Alt>(re)) {
116        for (unsigned i = 0; i < alt->size(); i++) {
117            if (isRequireNonFinal((*alt)[i], false)) {
118                return true;
119            }
120        }
121        return false;
122    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
123        if (seq->size() == 0) {
124            return false;
125        } else if (seq->size() == 1) {
126            return isRequireNonFinal((*seq)[0], false);
127        }
128    } else if (dyn_cast<Name>(re)) {
129        return false;
130    } else if (dyn_cast<CC>(re)) {
131        return false;
132    }
133    return true;
134}
135
136bool isAllCcByteLength(const RE * re) {
137    if (const Alt * alt = dyn_cast<Alt>(re)) {
138        for (const RE * re : *alt) {
139            if (!isAllCcByteLength(re)) {
140                return false;
141            }
142        }
143        return true;
144    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
145        for (const RE * e : *seq) {
146            if (!isAllCcByteLength(e)) return false;
147        }
148        return true;
149    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
150        return isAllCcByteLength(rep->getRE());
151    }  else if (const Name * n = dyn_cast<Name>(re)) {
152        if (n->getType() == Name::Type::ZeroWidth) {
153            return false;
154        }
155        return isAllCcByteLength(n->getDefinition());
156    } else {
157        return isByteLength(re);
158    }
159}
160
161bool isByteLength(const RE * re) {
162    if (const Alt * alt = dyn_cast<Alt>(re)) {
163        for (const RE * re : *alt) {
164            if (!isByteLength(re)) {
165                return false;
166            }
167        }
168        return true;
169    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
170        bool byteLengthSeen = false;
171        for (const RE * e : *seq) {
172            if (isa<Assertion>(e)) continue;
173            else if (byteLengthSeen) return false;
174            else if (isByteLength(e)) byteLengthSeen = true;
175            else return false;
176        }
177        return byteLengthSeen;
178    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
179        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
180    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
181        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
182    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
183        return isByteLength(e->getLH()) && isByteLength(e->getRH());
184    } else if (const CC * cc = dyn_cast<CC>(re)) {
185        const cc::Alphabet * a = cc->getAlphabet();
186        if (a == &cc::Unicode) {
187            return (cc->max_codepoint() <= 0x7F);
188        } else if (a == &cc::Byte) {
189            return true;
190        } else if (isa<cc::MultiplexedAlphabet>(a)) {
191            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
192            if (srcA == &cc::Byte) {
193                return true;
194            } else if (cc->sourceCC) {
195                return isByteLength(cc->sourceCC);
196//            } else if (srcA == &cc::Unicode) {
197//                return cast<cc::MultiplexedAlphabet>(a)->invertCC(cc)->max_codepoint() <= 0x7F;
198            } else return (a == &cc::Byte);
199        }
200        return false;
201    } else if (const Name * n = dyn_cast<Name>(re)) {
202        if (n->getType() == Name::Type::ZeroWidth) {
203            return false;
204        }
205        return isByteLength(n->getDefinition());
206    }
207    return false; // otherwise
208}
209
210bool isUnicodeUnitLength(const RE * re) {
211    if (const Alt * alt = dyn_cast<Alt>(re)) {
212        for (const RE * re : *alt) {
213            if (!isUnicodeUnitLength(re)) {
214                return false;
215            }
216        }
217        return true;
218    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
219        bool unitLengthSeen = false;
220        for (const RE * e : *seq) {
221            if (isa<Assertion>(e)) continue;
222            else if (unitLengthSeen) return false;
223            else if (isUnicodeUnitLength(e)) unitLengthSeen = true;
224            else return false;
225        }
226        return unitLengthSeen;
227    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
228        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
229    } else if (isa<Assertion>(re)) {
230        return false;
231    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
232        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
233    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
234        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
235    } else if (isa<Any>(re)) {
236        return true;
237    } else if (isa<CC>(re)) {
238        return true;
239    } else if (const Name * n = dyn_cast<Name>(re)) {
240        // Eventually names might be set up for not unit length items.
241        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty) {
242            return true;
243        } else if (n->getType() == Name::Type::ZeroWidth) {
244            return false;
245        }
246        return isUnicodeUnitLength(n->getDefinition());
247    }
248    return false; // otherwise
249}
250
251std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
252    if (const Alt * alt = dyn_cast<Alt>(re)) {
253        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
254        for (const RE * re : *alt) {
255            auto r = getUnicodeUnitLengthRange(re);
256            range.first = std::min<int>(range.first, r.first);
257            range.second = std::max<int>(range.second, r.second);
258        }
259        return range;
260    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
261        std::pair<int, int> range = std::make_pair(0, 0);
262        for (const RE * re : *seq) {
263            auto tmp = getUnicodeUnitLengthRange(re);
264            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
265                range.first += tmp.first;
266            } else {
267                range.first = INT_MAX;
268            }
269            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
270                range.second += tmp.second;
271            } else {
272                range.second = INT_MAX;
273            }
274        }
275        return range;
276    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
277        auto range = getUnicodeUnitLengthRange(rep->getRE());
278        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
279            range.first *= rep->getLB();
280        } else {
281            range.first = INT_MAX;
282        }
283        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
284            range.second *= rep->getUB();
285        } else {
286            range.second = INT_MAX;
287        }
288        return range;
289    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
290        return std::make_pair(0, 0);
291    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
292        // The range is determined by the first operand only.
293        return getUnicodeUnitLengthRange(diff->getLH());
294    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
295        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
296        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
297        // The matched string cannot be shorter than the largest of the min lengths
298        // nor can it be longer than the smallest of the max lengths.
299        return std::make_pair(std::max(r1.first, r2.first), std::min(r1.second, r2.second));
300    } else if (isa<CC>(re)) {
301        return std::make_pair(1, 1);
302    } else if (const Name * n = dyn_cast<Name>(re)) {
303        // Eventually names might be set up for not unit length items.
304        switch (n->getType()) {
305            case Name::Type::Unicode:
306            case Name::Type::UnicodeProperty:
307                return std::make_pair(1, 1);
308            case Name::Type::Capture:
309            case Name::Type::Reference:
310                return getUnicodeUnitLengthRange(n->getDefinition());
311            case Name::Type::ZeroWidth:
312                return std::make_pair(0, 0);
313            case Name::Type::Unknown:
314                return std::make_pair(0, INT_MAX);
315        }
316    } 
317    return std::make_pair(1, 1);
318}
319   
320bool isFixedLength(const RE * re) {
321    if (isa<Alt>(re)) {
322        auto range = getUnicodeUnitLengthRange(re);
323        return range.first == range.second;
324    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
325        for (const RE * e : *seq) {
326            if (!isFixedLength(e)) return false;
327        }
328        return true;
329    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
330        return (rep->getLB() == rep->getUB()) && isFixedLength(rep->getRE());
331    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
332        return isFixedLength(diff->getLH());
333    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
334        return isFixedLength(e->getLH()) || isFixedLength(e->getRH());
335    } else if (const Group * g = dyn_cast<Group>(re)) {
336        return isFixedLength(g->getRE());
337    } else if (const Name * n = dyn_cast<Name>(re)) {
338        return isFixedLength(n->getDefinition());
339    }
340    return true; // otherwise = CC, Any, Start, End, Range, Assertion
341}
342
343   
344int minMatchLength(const RE * re) {
345    if (const Alt * alt = dyn_cast<Alt>(re)) {
346        int minAltLength = INT_MAX;
347        for (RE * re : *alt) {
348            minAltLength = std::min(minAltLength, minMatchLength(re));
349        }
350        return minAltLength;
351    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
352        int minSeqLength = 0;
353        for (RE * re : *seq) {
354            minSeqLength += minMatchLength(re);
355        }
356        return minSeqLength;
357    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
358        if (rep->getLB() == 0) return 0;
359        else return (rep->getLB()) * minMatchLength(rep->getRE());
360    } else if (isa<Assertion>(re)) {
361        return 0;
362    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
363        return minMatchLength(diff->getLH());
364    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
365        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
366    } else if (isa<Any>(re)) {
367        return 1;
368    } else if (isa<CC>(re)) {
369        return 1;
370    } else if (const Name * n = dyn_cast<Name>(re)) {
371        // Eventually names might be set up for not unit length items.
372        switch (n->getType()) {
373            case Name::Type::Unicode:
374            case Name::Type::UnicodeProperty:
375                return 1;
376            case Name::Type::Capture:
377            case Name::Type::Reference:
378                return minMatchLength(n->getDefinition());
379            default:
380                return 0;
381        }
382    }
383    return 0; // otherwise
384}
385   
386//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
387bool unitBoundedRep(const RE * re) {
388    if (const Alt * alt = dyn_cast<Alt>(re)) {
389        for (const RE * re : *alt) {
390            if (unitBoundedRep(re)) {
391                return true;
392            }
393        }
394        return false;
395    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
396        for (const RE * re : *seq) {
397            if (unitBoundedRep(re)) {
398                return true;
399            }
400        }
401        return false;
402    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
403        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
404            return false;
405        } else {
406            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
407        }
408    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
409        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
410    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
411        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
412    } else if (const Name * n = dyn_cast<Name>(re)) {
413        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
414            return unitBoundedRep(n->getDefinition());
415        }
416        return false;
417    }
418    return false; // otherwise
419 
420}
421
422//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
423bool isTypeForLocal(const RE * re) {
424    if (const Name * n = dyn_cast<Name>(re)) {
425        return isTypeForLocal(n->getDefinition());
426    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
427        for (const RE * re : *alt) {
428            if (!isTypeForLocal(re)) {
429                return false;
430            }
431        }
432        return true;
433    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
434        if (seq->empty()) return false;
435        for (const RE * re : *seq) {
436            if (!isTypeForLocal(re)) {
437                return false;
438            }
439        }
440        return true;
441    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
442        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
443            return false;
444        }
445        return true;
446    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
447        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
448    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
449        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
450    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
451        return false;
452    }
453    return true; // otherwise
454}
455
456bool hasAssertion(const RE * re) {
457    if (isa<CC>(re)) {
458        return false;
459    } else if (const Name * n = dyn_cast<Name>(re)) {
460        return hasAssertion(n->getDefinition());
461    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
462        for (const RE * re : *alt) {
463            if (hasAssertion(re)) return true;
464        }
465        return false;
466    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
467        for (const RE * re : *seq) {
468            if (hasAssertion(re)) return true;
469        }
470        return false;
471    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
472        return hasAssertion(rep->getRE());
473    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
474        return hasAssertion(diff->getLH()) || hasAssertion(diff->getRH());
475    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
476        return hasAssertion(e->getLH()) || hasAssertion(e->getRH());
477    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
478        return true;
479    } else if (const Group * g = dyn_cast<Group>(re)) {
480        if ((g->getMode() == Group::Mode::GraphemeMode) && (g->getSense() == Group::Sense::On)) {
481            return true;
482        }
483        else {
484            return hasAssertion(g->getRE());
485        }
486    }
487    else llvm_unreachable("Unknown RE type");
488}
489
490struct ByteTestComplexity {
491   
492    void gatherTests(RE * re);
493   
494    UCD::UnicodeSet equalityTests;
495    UCD::UnicodeSet lessThanTests;
496    unsigned testCount;
497    unsigned testLimit;
498};
499
500void ByteTestComplexity::gatherTests(RE * re) {
501    if (const CC * cc = dyn_cast<CC>(re)) {
502        if (cc->getAlphabet() == &cc::Unicode) {
503            gatherTests(UTF8_Transformer().transformRE(re));
504        } else {
505            for (const auto range : *cc) {
506                const auto lo = re::lo_codepoint(range);
507                const auto hi = re::hi_codepoint(range);
508                if (lo == hi) {
509                    if (!equalityTests.contains(lo)) {
510                        equalityTests.insert(lo);
511                        testCount++;
512                    }
513                } else {
514                    if (lo > 0) {
515                        if (!lessThanTests.contains(lo)) {
516                            lessThanTests.insert(lo);
517                            testCount++;
518                        }
519                    }
520                    if (hi < 0xFF) {
521                        if (!lessThanTests.contains(hi+1)) {
522                            lessThanTests.insert(hi+1);
523                            testCount++;
524                        }
525                    }
526                }
527                if (testCount > testLimit) return;
528            }
529        }
530    } else if (const Name * n = dyn_cast<Name>(re)) {
531        gatherTests(n->getDefinition());
532    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
533        for (RE * item : *alt) {
534            gatherTests(item);
535        }
536    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
537        for (RE * item : *seq) {
538            gatherTests(item);
539        }
540    } else if (const Assertion * a = dyn_cast<Assertion>(re)) {
541        gatherTests(a->getAsserted());
542    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
543        gatherTests(rep->getRE());
544    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
545        gatherTests(diff->getLH());
546        gatherTests(diff->getRH());
547    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
548        gatherTests(e->getLH());
549        gatherTests(e->getRH());
550    } else if (const Group * g = dyn_cast<Group>(re)) {
551        gatherTests(g->getRE());
552    }
553}
554
555bool byteTestsWithinLimit(RE * re, unsigned limit) {
556    ByteTestComplexity btc_object;
557    btc_object.testCount = 0;
558    btc_object.testLimit = limit;
559    btc_object.gatherTests(re);
560    return btc_object.testCount <= btc_object.testLimit;
561}
562
563bool hasTriCCwithinLimit(RE * r, unsigned byteCClimit, RE * & prefixRE, RE * & suffixRE) {
564    if (const Seq * seq = dyn_cast<Seq>(r)) {
565        if (seq->size() < 4) return false;
566        if (!isa<CC>(*seq->begin())) return false;
567        if (!isa<CC>(*seq->begin()+1)) return false;
568        if (!isa<CC>(*seq->begin()+2)) return false;
569        prefixRE = makeSeq(seq->begin(), seq->begin()+3);
570        if (byteTestsWithinLimit(prefixRE, byteCClimit)) {
571            suffixRE = makeSeq(seq->begin()+3, seq->end());
572            errs() << "prefixRE: " << Printer_RE::PrintRE(prefixRE) << "\n";
573            errs() << "suffixRE: " << Printer_RE::PrintRE(suffixRE) << "\n";
574            return true;
575        }
576        return false;
577    }
578    return false;
579}
580
581   
582bool hasEndAnchor(const RE * re) {
583    if (const Alt * alt = dyn_cast<Alt>(re)) {
584        for (const RE * re : *alt) {
585            if (!hasEndAnchor(re)) {
586                return false;
587            }
588        }
589        return true;
590    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
591        return (!seq->empty()) && isa<End>(seq->back());
592    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
593        return hasEndAnchor(rep->getRE());
594    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
595        return hasEndAnchor(diff->getLH()) && !hasEndAnchor(diff->getRH());
596    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
597        return hasEndAnchor(e->getLH()) && hasEndAnchor(e->getRH());
598    } else if (isa<End>(re)) {
599        return true;
600    }
601    return false; // otherwise
602}
603   
604//
605//  Back Reference Analysis
606//
607//  The definite-length back-reference implementation strategy requires that
608//  each capture that has a back-reference be fixed in length and that
609//  that each back-reference is a fixed length from its corresponding capture.
610//
611//   In analyzing a sequences of regular expression elements
612//   e_0, e_1, ..., e_i, ..., e_j, ..., e_n
613//   we say that e_j is within fixed-length range of e_i if
614//   for all k: i < k < j, e_k is fixed length.
615//
616
617bool DefiniteLengthBackReferencesOnly(const RE * re) {
618    if (const Alt * alt = dyn_cast<Alt>(re)) {
619        for (const RE * a : *alt) {
620            if (!DefiniteLengthBackReferencesOnly(a)) return false;
621        }
622        return true;
623    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
624        // As we iterate through sequence elements, we keep track of captures
625        // that are encountered and are still reachable through a series of
626        // fixed length elements back from the current position.  As soon as
627        // a variable length element is encounterd, the list of available_captures
628        // is cleared.
629        //
630        std::set<const Name *> available_captures;
631        for (const RE * e : *seq) {
632            if (const Name * n = dyn_cast<Name>(e)) {
633                auto T = n->getType();
634                auto defn = n->getDefinition();
635                if (T == Name::Type::Reference) {
636                    if (available_captures.find(cast<Name>(defn)) == available_captures.end()) {
637                        // Capture is not available.
638                        return false;
639                    } else {
640                        continue;
641                    }
642                } else {
643                    if (!DefiniteLengthBackReferencesOnly(defn)) return false;
644                    if (isFixedLength(defn)) {
645                        if (T == Name::Type::Capture) {
646                            available_captures.emplace(n);
647                        }
648                    } else {
649                        available_captures.clear();
650                    }
651                }
652            }
653            if (!DefiniteLengthBackReferencesOnly(e)) return false;
654            if (!isFixedLength(e)) available_captures.clear();
655        }
656        return true;
657    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
658        return DefiniteLengthBackReferencesOnly(rep->getRE());
659    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
660        return DefiniteLengthBackReferencesOnly(diff->getLH()) && DefiniteLengthBackReferencesOnly(diff->getRH());
661    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
662        return DefiniteLengthBackReferencesOnly(e->getLH()) && DefiniteLengthBackReferencesOnly(e->getRH());
663    } else if (const Assertion * a = dyn_cast<Assertion>(re)) {
664        return DefiniteLengthBackReferencesOnly(a->getAsserted());
665    } else if (const Group * g = dyn_cast<Group>(re)) {
666        return DefiniteLengthBackReferencesOnly(g->getRE());
667    } else if (const Name * n = dyn_cast<Name>(re)) {
668        if (n->getType() == Name::Type::Reference) return false;
669        return DefiniteLengthBackReferencesOnly(n->getDefinition());
670    }
671    return true; // otherwise = CC, Any, Start, End, Range
672}
673
674void UndefinedNameError(const Name * n) {
675    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
676}
677}
Note: See TracBrowser for help on using the repository browser.