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

Last change on this file was 6297, checked in by cameron, 4 months ago

Merge branch 'master' of https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel

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