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

Last change on this file since 5678 was 5649, checked in by cameron, 2 years ago

Some RE tidy-ups; an empty Alt is permitted and represents the set of no strings

File size: 10.0 KB
Line 
1#include "re_analysis.h"
2#include <re/re_cc.h>
3#include <re/re_name.h>
4#include <re/re_start.h>
5#include <re/re_end.h>
6#include <re/re_any.h>
7#include <re/re_seq.h>
8#include <re/re_alt.h>
9#include <re/re_rep.h>
10#include <re/re_diff.h>
11#include <re/re_intersect.h>
12#include <re/re_assertion.h>
13#include <re/re_nullable.h>
14#include <re/printer_re.h>
15#include <limits.h>
16#include <llvm/Support/ErrorHandling.h>
17
18using namespace llvm;
19
20namespace re {
21
22bool isByteLength(const RE * re) {
23    if (const Alt * alt = dyn_cast<Alt>(re)) {
24        for (const RE * re : *alt) {
25            if (!isByteLength(re)) {
26                return false;
27            }
28        }
29        return true;
30    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
31        return (seq->size() == 1) && isByteLength(&seq[0]);
32    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
33        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
34    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
35        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
36    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
37        return isByteLength(e->getLH()) && isByteLength(e->getRH());
38    } else if (isa<CC>(re)) {
39        return cast<CC>(re)->max_codepoint() <= 0x7F;
40    } else if (const Name * n = dyn_cast<Name>(re)) {
41        if (n->getType() == Name::Type::Byte) {
42            return true;
43        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
44            return isByteLength(n->getDefinition());
45        }
46        return false;
47    }
48    return false; // otherwise
49}
50
51bool isUnicodeUnitLength(const RE * re) {
52    if (const Alt * alt = dyn_cast<Alt>(re)) {
53        for (const RE * re : *alt) {
54            if (!isUnicodeUnitLength(re)) {
55                return false;
56            }
57        }
58        return true;
59    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
60        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
61    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
62        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
63    } else if (isa<Assertion>(re)) {
64        return false;
65    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
66        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
67    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
68        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
69    } else if (isa<Any>(re)) {
70        return true;
71    } else if (isa<CC>(re)) {
72        return true;
73    } else if (const Name * n = dyn_cast<Name>(re)) {
74        // Eventually names might be set up for not unit length items.
75        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
76            return true;
77        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
78            return isUnicodeUnitLength(n->getDefinition());
79        }
80        return false;
81    }
82    return false; // otherwise
83}
84
85std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
86    if (const Alt * alt = dyn_cast<Alt>(re)) {
87        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
88        for (const RE * re : *alt) {
89            auto r = getUnicodeUnitLengthRange(re);
90            range.first = std::min<int>(range.first, r.first);
91            range.second = std::max<int>(range.second, r.second);
92        }
93        return range;
94    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
95        std::pair<int, int> range = std::make_pair(0, 0);
96        for (const RE * re : *seq) {
97            auto tmp = getUnicodeUnitLengthRange(re);
98            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
99                range.first += tmp.first;
100            } else {
101                range.first = INT_MAX;
102            }
103            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
104                range.second += tmp.second;
105            } else {
106                range.second = INT_MAX;
107            }
108        }
109        return range;
110    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
111        auto range = getUnicodeUnitLengthRange(rep->getRE());
112        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
113            range.first *= rep->getLB();
114        } else {
115            range.first = INT_MAX;
116        }
117        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
118            range.second *= rep->getUB();
119        } else {
120            range.second = INT_MAX;
121        }
122        return range;
123    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
124        return std::make_pair(0, 0);
125    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
126        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
127        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
128        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
129    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
130        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
131        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
132        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
133    } else if (isa<CC>(re)) {
134        return std::make_pair(1, 1);
135    } else if (const Name * n = dyn_cast<Name>(re)) {
136        // Eventually names might be set up for not unit length items.
137        switch (n->getType()) {
138            case Name::Type::Byte:
139            case Name::Type::Unicode:
140            case Name::Type::UnicodeProperty:
141                return std::make_pair(1, 1);
142            case Name::Type::Capture:
143            case Name::Type::Reference:
144                return getUnicodeUnitLengthRange(n->getDefinition());
145            case Name::Type::ZeroWidth:
146                return std::make_pair(0, 0);
147            case Name::Type::Unknown:
148                return std::make_pair(0, INT_MAX);
149        }
150    } 
151    return std::make_pair(1, 1);
152}
153   
154int minMatchLength(RE * re) {
155    if (Alt * alt = dyn_cast<Alt>(re)) {
156        int minAltLength = INT_MAX;
157        for (RE * re : *alt) {
158            minAltLength = std::min(minAltLength, minMatchLength(re));
159        }
160        return minAltLength;
161    } else if (Seq * seq = dyn_cast<Seq>(re)) {
162        int minSeqLength = 0;
163        for (RE * re : *seq) {
164            minSeqLength += minMatchLength(re);
165        }
166        return minSeqLength;
167    } else if (Rep * rep = dyn_cast<Rep>(re)) {
168        if (rep->getLB() == 0) return 0;
169        else return (rep->getLB()) * minMatchLength(rep->getRE());
170    } else if (isa<Assertion>(re)) {
171        return 0;
172    } else if (Diff * diff = dyn_cast<Diff>(re)) {
173        return minMatchLength(diff->getLH());
174    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
175        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
176    } else if (isa<Any>(re)) {
177        return 1;
178    } else if (isa<CC>(re)) {
179        return 1;
180    } else if (const Name * n = dyn_cast<Name>(re)) {
181        // Eventually names might be set up for not unit length items.
182        switch (n->getType()) {
183            case Name::Type::Byte:
184            case Name::Type::Unicode:
185            case Name::Type::UnicodeProperty:
186                return 1;
187            case Name::Type::Capture:
188            case Name::Type::Reference:
189                return minMatchLength(n->getDefinition());
190            default:
191                return 0;
192        }
193    }
194    return 0; // otherwise
195}
196   
197//If a regular expression contains unit and not byteLength bounded repetition type, we select a different pipeline to utilize the log2 technique.
198bool unitBoundedRep(const RE * re) {
199    if (const Alt * alt = dyn_cast<Alt>(re)) {
200        for (const RE * re : *alt) {
201            if (unitBoundedRep(re)) {
202                return true;
203            }
204        }
205        return false;
206    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
207        for (const RE * re : *seq) {
208            if (unitBoundedRep(re)) {
209                return true;
210            }
211        }
212        return false;
213    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
214        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
215            return false;
216        } else {
217            return (!isByteLength(rep->getRE()) && isUnicodeUnitLength(rep->getRE()));
218        }
219    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
220        return unitBoundedRep(diff->getLH()) || unitBoundedRep(diff->getRH());
221    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
222        return unitBoundedRep(e->getLH()) || unitBoundedRep(e->getRH());
223    } else if (const Name * n = dyn_cast<Name>(re)) {
224        if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
225            return unitBoundedRep(n->getDefinition());
226        }
227        return false;
228    }
229    return false; // otherwise
230 
231}
232
233//Cases that not include bounded repetition, assertion, start and end type can suit for local language compile pipeline.
234bool isTypeForLocal(const RE * re) {
235    if (const Alt * alt = dyn_cast<Alt>(re)) {
236        for (const RE * re : *alt) {
237            if (!isTypeForLocal(re)) {
238                return false;
239            }
240        }
241        return true;
242    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
243    for (const RE * re : *seq) {
244        if (!isTypeForLocal(re)) {
245            return false;
246        }
247    }
248        return true;
249    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
250        if (rep->getLB() != 0 || rep->getUB() != Rep::UNBOUNDED_REP) {
251            return false;
252        } 
253        return true;
254    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
255        return isTypeForLocal(diff->getLH()) && isTypeForLocal(diff->getRH());
256    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
257        return isTypeForLocal(e->getLH()) && isTypeForLocal(e->getRH());
258    } else if (isa<Start>(re) || isa<End>(re) || isa<Assertion>(re)) {
259        return false;
260    }
261    return true; // otherwise
262}
263
264void UndefinedNameError(const Name * n) {
265    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
266}
267}
Note: See TracBrowser for help on using the repository browser.