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

Last change on this file since 5899 was 5899, checked in by cameron, 13 months ago

Fixes for Unix line break mode

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