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

Last change on this file was 6133, checked in by xwa163, 3 weeks 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.