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

Last change on this file since 5898 was 5898, checked in by cameron, 15 months ago

Fix Unicode unit length calculations to allow for assertions

File size: 16.8 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/printer_re.h>
17#include <cc/alphabet.h>
18#include <cc/multiplex_CCs.h>
19#include <limits.h>
20#include <llvm/Support/ErrorHandling.h>
21#include <llvm/Support/raw_ostream.h>
22
23using namespace llvm;
24
25namespace re {
26   
27bool matchesEmptyString(const RE * re) {
28    if (const Alt * alt = dyn_cast<Alt>(re)) {
29        for (const RE * re : *alt) {
30            if (matchesEmptyString(re)) {
31                return true;
32            }
33        }
34        return false;
35    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
36        for (const RE * re : *seq) {
37            if (!matchesEmptyString(re)) {
38                return false;
39            }
40        }
41        return true;
42    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
43        return (rep->getLB() == 0) || matchesEmptyString(rep->getRE());
44    } else if (isa<Start>(re)) {
45        return true;
46    } else if (isa<End>(re)) {
47        return true;
48    } else if (isa<Assertion>(re)) {
49        return false;
50    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
51        return matchesEmptyString(diff->getLH()) && !matchesEmptyString(diff->getRH());
52    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
53        return matchesEmptyString(e->getLH()) && matchesEmptyString(e->getRH());
54    } else if (isa<Any>(re)) {
55        return false;
56    } else if (isa<CC>(re)) {
57        return false;
58    } else if (const Group * g = dyn_cast<Group>(re)) {
59        return matchesEmptyString(g->getRE());
60    } else if (const Name * n = dyn_cast<Name>(re)) {
61        return matchesEmptyString(n->getDefinition());
62    }
63    return false; // otherwise
64}
65
66const CC* matchableCodepoints(const RE * re) {
67    if (const CC * cc = dyn_cast<CC>(re)) {
68        return cc;
69    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
70        CC * matchable = makeCC();
71        for (const RE * re : *alt) {
72            matchable = makeCC(matchable, matchableCodepoints(re));
73        }
74        return matchable;
75    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
76        CC * matchable = makeCC();
77        bool pastCC = false;
78        for (const RE * re : *seq) {
79            if (pastCC) {
80                if (!(isa<End>(re) || matchesEmptyString(re))) return makeCC();
81            }
82            else if (isa<End>(re)) return makeCC();
83            else {
84                matchable = makeCC(matchable, matchableCodepoints(re));
85                pastCC = !matchesEmptyString(re);
86            }
87        }
88        return matchable;
89    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
90        if ((rep->getLB() <= 1) || matchesEmptyString(rep->getRE())) {
91            return matchableCodepoints(rep->getRE());
92        }
93        else return makeCC();
94    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
95        return subtractCC(matchableCodepoints(diff->getLH()), matchableCodepoints(diff->getRH()));
96    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
97        return intersectCC(matchableCodepoints(e->getLH()), matchableCodepoints(e->getRH()));
98    } else if (isa<Any>(re)) {
99        return makeCC(0, 0x10FFFF);
100    } else if (const Name * n = dyn_cast<Name>(re)) {
101        return matchableCodepoints(n->getDefinition());
102    }
103    return makeCC(); // otherwise = Start, End, Assertion
104}
105
106
107
108bool isByteLength(const RE * re) {
109    if (const Alt * alt = dyn_cast<Alt>(re)) {
110        for (const RE * re : *alt) {
111            if (!isByteLength(re)) {
112                return false;
113            }
114        }
115        return true;
116    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
117        return (seq->size() == 1) && isByteLength(&seq[0]);
118    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
119        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
120    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
121        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
122    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
123        return isByteLength(e->getLH()) && isByteLength(e->getRH());
124    } else if (const CC * cc = dyn_cast<CC>(re)) {
125        const cc::Alphabet * a = cc->getAlphabet();
126        if (a == &cc::Unicode) {
127            return (cc->max_codepoint() <= 0x7F);
128        } else if (a == &cc::Byte) {
129            return true;
130        } else if (isa<cc::MultiplexedAlphabet>(a)) {
131            const cc::Alphabet * srcA = cast<cc::MultiplexedAlphabet>(a)->getSourceAlphabet();
132            if (srcA == &cc::Byte) {
133                return true;
134//            } else if (srcA == &cc::Unicode) {
135//                return cast<cc::MultiplexedAlphabet>(a)->invertCC(cc)->max_codepoint() <= 0x7F;
136            } else return (a == &cc::Byte);
137        }
138        return false;
139    } else if (const Name * n = dyn_cast<Name>(re)) {
140        if (n->getType() == Name::Type::ZeroWidth) {
141            return false;
142        }
143        return isByteLength(n->getDefinition());
144    }
145    return false; // otherwise
146}
147
148bool isUnicodeUnitLength(const RE * re) {
149    if (const Alt * alt = dyn_cast<Alt>(re)) {
150        for (const RE * re : *alt) {
151            if (!isUnicodeUnitLength(re)) {
152                return false;
153            }
154        }
155        return true;
156    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
157        bool unitLengthSeen = false;
158        for (const RE * e : *seq) {
159            if (isa<Assertion>(e)) continue;
160            else if (unitLengthSeen) return false;
161            else if (isUnicodeUnitLength(e)) unitLengthSeen = true;
162            else return false;
163        }
164        return unitLengthSeen;
165    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
166        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
167    } else if (isa<Assertion>(re)) {
168        return false;
169    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
170        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
171    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
172        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
173    } else if (isa<Any>(re)) {
174        return true;
175    } else if (isa<CC>(re)) {
176        return true;
177    } else if (const Name * n = dyn_cast<Name>(re)) {
178        // Eventually names might be set up for not unit length items.
179        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty) {
180            return true;
181        } else if (n->getType() == Name::Type::ZeroWidth) {
182            return false;
183        }
184        return isUnicodeUnitLength(n->getDefinition());
185    }
186    return false; // otherwise
187}
188
189std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
190    if (const Alt * alt = dyn_cast<Alt>(re)) {
191        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
192        for (const RE * re : *alt) {
193            auto r = getUnicodeUnitLengthRange(re);
194            range.first = std::min<int>(range.first, r.first);
195            range.second = std::max<int>(range.second, r.second);
196        }
197        return range;
198    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
199        std::pair<int, int> range = std::make_pair(0, 0);
200        for (const RE * re : *seq) {
201            auto tmp = getUnicodeUnitLengthRange(re);
202            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
203                range.first += tmp.first;
204            } else {
205                range.first = INT_MAX;
206            }
207            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
208                range.second += tmp.second;
209            } else {
210                range.second = INT_MAX;
211            }
212        }
213        return range;
214    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
215        auto range = getUnicodeUnitLengthRange(rep->getRE());
216        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
217            range.first *= rep->getLB();
218        } else {
219            range.first = INT_MAX;
220        }
221        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
222            range.second *= rep->getUB();
223        } else {
224            range.second = INT_MAX;
225        }
226        return range;
227    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
228        return std::make_pair(0, 0);
229    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
230        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
231        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
232        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
233    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
234        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
235        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
236        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
237    } else if (isa<CC>(re)) {
238        return std::make_pair(1, 1);
239    } else if (const Name * n = dyn_cast<Name>(re)) {
240        // Eventually names might be set up for not unit length items.
241        switch (n->getType()) {
242            case Name::Type::Unicode:
243            case Name::Type::UnicodeProperty:
244                return std::make_pair(1, 1);
245            case Name::Type::Capture:
246            case Name::Type::Reference:
247                return getUnicodeUnitLengthRange(n->getDefinition());
248            case Name::Type::ZeroWidth:
249                return std::make_pair(0, 0);
250            case Name::Type::Unknown:
251                return std::make_pair(0, INT_MAX);
252        }
253    } 
254    return std::make_pair(1, 1);
255}
256   
257int minMatchLength(RE * re) {
258    if (Alt * alt = dyn_cast<Alt>(re)) {
259        int minAltLength = INT_MAX;
260        for (RE * re : *alt) {
261            minAltLength = std::min(minAltLength, minMatchLength(re));
262        }
263        return minAltLength;
264    } else if (Seq * seq = dyn_cast<Seq>(re)) {
265        int minSeqLength = 0;
266        for (RE * re : *seq) {
267            minSeqLength += minMatchLength(re);
268        }
269        return minSeqLength;
270    } else if (Rep * rep = dyn_cast<Rep>(re)) {
271        if (rep->getLB() == 0) return 0;
272        else return (rep->getLB()) * minMatchLength(rep->getRE());
273    } else if (isa<Assertion>(re)) {
274        return 0;
275    } else if (Diff * diff = dyn_cast<Diff>(re)) {
276        return minMatchLength(diff->getLH());
277    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
278        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
279    } else if (isa<Any>(re)) {
280        return 1;
281    } else if (isa<CC>(re)) {
282        return 1;
283    } else if (const Name * n = dyn_cast<Name>(re)) {
284        // Eventually names might be set up for not unit length items.
285        switch (n->getType()) {
286            case Name::Type::Unicode:
287            case Name::Type::UnicodeProperty:
288                return 1;
289            case Name::Type::Capture:
290            case Name::Type::Reference:
291                return minMatchLength(n->getDefinition());
292            default:
293                return 0;
294        }
295    }
296    return 0; // otherwise
297}
298   
299//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
300bool unitBoundedRep(const RE * re) {
301    if (const Alt * alt = dyn_cast<Alt>(re)) {
302        for (const RE * re : *alt) {
303            if (unitBoundedRep(re)) {
304                return true;
305            }
306        }
307        return false;
308    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
309        for (const RE * re : *seq) {
310            if (unitBoundedRep(re)) {
311                return true;
312            }
313        }
314        return false;
315    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
316        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
317            return false;
318        } else {
319            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
320        }
321    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
322        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
323    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
324        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
325    } else if (const Name * n = dyn_cast<Name>(re)) {
326        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
327            return unitBoundedRep(n->getDefinition());
328        }
329        return false;
330    }
331    return false; // otherwise
332 
333}
334
335//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
336bool isTypeForLocal(const RE * re) {
337    if (const Name * n = dyn_cast<Name>(re)) {
338        return isTypeForLocal(n->getDefinition());
339    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
340        for (const RE * re : *alt) {
341            if (!isTypeForLocal(re)) {
342                return false;
343            }
344        }
345        return true;
346    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
347        if (seq->empty()) return false;
348        for (const RE * re : *seq) {
349            if (!isTypeForLocal(re)) {
350                return false;
351            }
352        }
353        return true;
354    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
355        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
356            return false;
357        }
358        return true;
359    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
360        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
361    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
362        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
363    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
364        return false;
365    }
366    return true; // otherwise
367}
368
369bool hasAssertion(const RE * re) {
370    if (isa<CC>(re)) {
371        return false;
372    } else if (const Name * n = dyn_cast<Name>(re)) {
373        return hasAssertion(n->getDefinition());
374    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
375        for (const RE * re : *alt) {
376            if (hasAssertion(re)) return true;
377        }
378        return false;
379    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
380        for (const RE * re : *seq) {
381            if (hasAssertion(re)) return true;
382        }
383        return false;
384    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
385        return hasAssertion(rep->getRE());
386    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
387        return hasAssertion(diff->getLH()) || hasAssertion(diff->getRH());
388    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
389        return hasAssertion(e->getLH()) || hasAssertion(e->getRH());
390    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
391        return true;
392    } else if (const Group * g = dyn_cast<Group>(re)) {
393        if ((g->getMode() == Group::Mode::GraphemeMode) && (g->getSense() == Group::Sense::On)) {
394            return true;
395        }
396        else {
397            return hasAssertion(g->getRE());
398        }
399    }
400    else llvm_unreachable("Unknown RE type");
401}
402
403struct ByteTestComplexity {
404   
405    void gatherTests(RE * re);
406   
407    UCD::UnicodeSet equalityTests;
408    UCD::UnicodeSet lessThanTests;
409};
410
411void ByteTestComplexity::gatherTests(RE * re) {
412    if (CC * cc = dyn_cast<CC>(re)) {
413        if (cc->getAlphabet() != &cc::Byte) report_fatal_error("ByteTestComplexity: non Byte alphabet");
414        for (const auto range : *cc) {
415            const auto lo = re::lo_codepoint(range);
416            const auto hi = re::hi_codepoint(range);
417            if (lo == hi) {
418                equalityTests.insert(lo);
419            } else {
420                if (lo > 0) lessThanTests.insert(lo);
421                if (hi < 0xFF) lessThanTests.insert(hi+1);
422            }
423        }
424    } else if (const Name * n = dyn_cast<Name>(re)) {
425        gatherTests(n->getDefinition());
426    } else if (Alt * alt = dyn_cast<Alt>(re)) {
427        for (RE * item : *alt) {
428            gatherTests(item);
429        }
430    } else if (Seq * seq = dyn_cast<Seq>(re)) {
431        for (RE * item : *seq) {
432            gatherTests(item);
433        }
434    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
435        gatherTests(a->getAsserted());
436    } else if (Rep * rep = dyn_cast<Rep>(re)) {
437        gatherTests(rep->getRE());
438    } else if (Diff * diff = dyn_cast<Diff>(re)) {
439        gatherTests(diff->getLH());
440        gatherTests(diff->getRH());
441    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
442        gatherTests(e->getLH());
443        gatherTests(e->getRH());
444    } else if (Group * g = dyn_cast<Group>(re)) {
445        gatherTests(g->getRE());
446    }
447}
448
449unsigned byteTestComplexity(RE * re) {
450    ByteTestComplexity btc_object;
451    btc_object.gatherTests(re);
452    return btc_object.equalityTests.count() + btc_object.lessThanTests.count();
453}
454
455
456void UndefinedNameError(const Name * n) {
457    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
458}
459}
Note: See TracBrowser for help on using the repository browser.