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

Last change on this file was 6292, checked in by cameron, 28 hours ago

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

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