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

Last change on this file since 6130 was 6130, checked in by xwa163, 11 months ago

Decompress u8NoFinalStream in lzparabix_grep

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