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

Last change on this file since 5891 was 5891, checked in by cameron, 14 months ago

Byte test complexity analysis

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