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

Last change on this file since 5080 was 5080, checked in by cameron, 3 years ago

Initial support for capture groups/back references; back reference simply repeats regexp

File size: 7.6 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_grapheme_boundary.hpp>
14#include <iostream>
15#include <re/printer_re.h>
16#include <limits.h>
17
18namespace re {
19
20bool isByteLength(const RE * re) {
21    if (const Alt * alt = dyn_cast<Alt>(re)) {
22        for (const RE * re : *alt) {
23            if (!isByteLength(re)) {
24                return false;
25            }
26        }
27        return true;
28    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
29        return (seq->size() == 1) && isByteLength(&seq[0]);
30    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
31        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
32    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
33        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
34    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
35        return isByteLength(e->getLH()) && isByteLength(e->getRH());
36    } else if (const Name * n = dyn_cast<Name>(re)) {
37        if (n->getType() == Name::Type::Byte) {
38            return true;
39        }
40        else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
41            return isByteLength(n->getDefinition());
42        }
43        return false;
44    }
45    return false; // otherwise
46}
47
48bool isUnicodeUnitLength(const RE * re) {
49    if (const Alt * alt = dyn_cast<Alt>(re)) {
50        for (const RE * re : *alt) {
51            if (!isUnicodeUnitLength(re)) {
52                return false;
53            }
54        }
55        return true;
56    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
57        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
58    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
59        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
60    } else if (isa<Assertion>(re)) {
61        return false;
62    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
63        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
64    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
65        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
66    } else if (isa<Any>(re)) {
67        return true;
68    } else if (const Name * n = dyn_cast<Name>(re)) {
69        // Eventually names might be set up for not unit length items.
70        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
71            return true;
72        }
73        else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
74            return isUnicodeUnitLength(n->getDefinition());
75        }
76        return false;
77    }
78    return false; // otherwise
79}
80
81std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
82    if (const Alt * alt = dyn_cast<Alt>(re)) {
83        std::pair<int, int> range = std::make_pair(std::numeric_limits<int>::max(), 0);
84        for (const RE * re : *alt) {
85            auto r = getUnicodeUnitLengthRange(re);
86            range.first = std::min<int>(range.first, r.first);
87            range.second = std::max<int>(range.second, r.second);
88        }
89        return range;
90    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
91        std::pair<int, int> range = std::make_pair(0, 0);
92        for (const RE * re : *seq) {
93            auto tmp = getUnicodeUnitLengthRange(re);
94            if (LLVM_LIKELY(tmp.first < std::numeric_limits<int>::max() - range.first)) {
95                range.first += tmp.first;
96            } else {
97                range.first = std::numeric_limits<int>::max();
98            }
99            if (LLVM_LIKELY(tmp.second < std::numeric_limits<int>::max() - range.second)) {
100                range.second += tmp.second;
101            } else {
102                range.second = std::numeric_limits<int>::max();
103            }
104        }
105        return range;
106    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
107        auto range = getUnicodeUnitLengthRange(rep->getRE());
108        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < std::numeric_limits<int>::max())) {
109            range.first *= rep->getLB();
110        } else {
111            range.first = std::numeric_limits<int>::max();
112        }
113        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < std::numeric_limits<int>::max())) {
114            range.second *= rep->getUB();
115        } else {
116            range.second = std::numeric_limits<int>::max();
117        }
118        return range;
119    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
120        return std::make_pair(0, 0);
121    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
122        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
123        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
124        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
125    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
126        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
127        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
128        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
129    } else if (const Name * n = dyn_cast<Name>(re)) {
130        // Eventually names might be set up for not unit length items.
131        switch (n->getType()) {
132            case Name::Type::Byte:
133            case Name::Type::Unicode:
134            case Name::Type::UnicodeProperty:
135                return std::make_pair(1, 1);
136            case Name::Type::Capture:
137            case Name::Type::Reference:
138                return getUnicodeUnitLengthRange(n->getDefinition());
139            case Name::Type::Unknown:
140                return std::make_pair(0, std::numeric_limits<int>::max());
141        }
142    } else if (const GraphemeBoundary * gp = dyn_cast<GraphemeBoundary>(re)) {
143        if (gp->getExpression()) {
144            return getUnicodeUnitLengthRange(gp->getExpression());
145        }
146        return std::make_pair(0, 0);
147    }
148    return std::make_pair(1, 1);
149}
150   
151int minMatchLength(RE * re) {
152    if (Alt * alt = dyn_cast<Alt>(re)) {
153        int minAltLength = INT_MAX;
154        for (RE * re : *alt) {
155            minAltLength = std::min(minAltLength, minMatchLength(re));
156        }
157        return minAltLength;
158    }
159    else if (Seq * seq = dyn_cast<Seq>(re)) {
160        int minSeqLength = 0;
161        for (RE * re : *seq) {
162            minSeqLength += minMatchLength(re);
163        }
164        return minSeqLength;
165    }
166    else if (Rep * rep = dyn_cast<Rep>(re)) {
167        if (rep->getLB() == 0) return 0;
168        else return (rep->getLB()) * minMatchLength(rep->getRE());
169    }
170    else if (isa<Assertion>(re)) {
171        return 0;
172    }
173    else if (Diff * diff = dyn_cast<Diff>(re)) {
174        return minMatchLength(diff->getLH());
175    }
176    else if (Intersect * e = dyn_cast<Intersect>(re)) {
177        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
178    }
179    else if (isa<Any>(re)) {
180        return 1;
181    }
182    else if (const Name * n = dyn_cast<Name>(re)) {
183    // Eventually names might be set up for not unit length items.
184        switch (n->getType()) {
185            case Name::Type::Byte:
186            case Name::Type::Unicode:
187            case Name::Type::UnicodeProperty:
188                return 1;
189            case Name::Type::Capture:
190            case Name::Type::Reference:
191                return minMatchLength(n->getDefinition());
192            case Name::Type::Unknown:
193                return 0;
194        }
195    }
196    return 0; // otherwise
197}
198
199
200}
Note: See TracBrowser for help on using the repository browser.