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

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