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

Last change on this file was 5951, checked in by cameron, 2 months ago

Back reference analysis in support of future back reference compilation mode

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