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

Last change on this file since 4835 was 4835, checked in by nmedfort, 4 years ago

Minor changes to add grapheme boundary processing to RE analysis.

File size: 6.7 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        return (n->getType() == Name::Type::Byte);
38    }
39    return false; // otherwise
40}
41
42bool isUnicodeUnitLength(const RE * re) {
43    if (const Alt * alt = dyn_cast<Alt>(re)) {
44        for (const RE * re : *alt) {
45            if (!isUnicodeUnitLength(re)) {
46                return false;
47            }
48        }
49        return true;
50    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
51        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
52    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
53        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
54    } else if (isa<Assertion>(re)) {
55        return false;
56    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
57        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
58    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
59        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
60    } else if (isa<Any>(re)) {
61        return true;
62    } else if (const Name * n = dyn_cast<Name>(re)) {
63        // Eventually names might be set up for not unit length items.
64        return (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte);
65    } else if (const GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
66        return isUnicodeUnitLength(gb->getExpression());
67    }
68    return false; // otherwise
69}
70
71std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
72    if (const Alt * alt = dyn_cast<Alt>(re)) {
73        std::pair<int, int> range = std::make_pair(std::numeric_limits<int>::max(), 0);
74        for (const RE * re : *alt) {
75            auto r = getUnicodeUnitLengthRange(re);
76            range.first = std::min<int>(range.first, r.first);
77            range.second = std::max<int>(range.second, r.second);
78        }
79        return range;
80    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
81        std::pair<int, int> range = std::make_pair(0, 0);
82        for (const RE * re : *seq) {
83            auto tmp = getUnicodeUnitLengthRange(re);
84            if (LLVM_LIKELY(tmp.first < std::numeric_limits<int>::max() - range.first)) {
85                range.first += tmp.first;
86            } else {
87                range.first = std::numeric_limits<int>::max();
88            }
89            if (LLVM_LIKELY(tmp.second < std::numeric_limits<int>::max() - range.second)) {
90                range.second += tmp.second;
91            } else {
92                range.second = std::numeric_limits<int>::max();
93            }
94        }
95        return range;
96    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
97        auto range = getUnicodeUnitLengthRange(rep->getRE());
98        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < std::numeric_limits<int>::max())) {
99            range.first *= rep->getLB();
100        } else {
101            range.first = std::numeric_limits<int>::max();
102        }
103        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < std::numeric_limits<int>::max())) {
104            range.second *= rep->getUB();
105        } else {
106            range.second = std::numeric_limits<int>::max();
107        }
108        return range;
109    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
110        return std::make_pair(0, 0);
111    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
112        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
113        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
114        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
115    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
116        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
117        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
118        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
119    } else if (const Name * n = dyn_cast<Name>(re)) {
120        // Eventually names might be set up for not unit length items.
121        switch (n->getType()) {
122            case Name::Type::Byte:
123            case Name::Type::Unicode:
124            case Name::Type::UnicodeProperty:
125                return std::make_pair(1, 1);
126            case Name::Type::Unknown:
127                return std::make_pair(0, std::numeric_limits<int>::max());
128        }
129    } else if (const GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
130        return std::make_pair(getUnicodeUnitLengthRange(gb->getExpression()).first, std::numeric_limits<int>::max());
131    }
132    return std::make_pair(1, 1);
133}
134   
135int minMatchLength(RE * re) {
136    if (Alt * alt = dyn_cast<Alt>(re)) {
137        int minAltLength = INT_MAX;
138        for (RE * re : *alt) {
139            minAltLength = std::min(minAltLength, minMatchLength(re));
140        }
141        return minAltLength;
142    }
143    else if (Seq * seq = dyn_cast<Seq>(re)) {
144        int minSeqLength = 0;
145        for (RE * re : *seq) {
146            minSeqLength += minMatchLength(re);
147        }
148        return minSeqLength;
149    }
150    else if (Rep * rep = dyn_cast<Rep>(re)) {
151        if (rep->getLB() == 0) return 0;
152        else return (rep->getLB()) * minMatchLength(rep->getRE());
153    }
154    else if (isa<Assertion>(re)) {
155        return 0;
156    }
157    else if (Diff * diff = dyn_cast<Diff>(re)) {
158        return minMatchLength(diff->getLH());
159    }
160    else if (Intersect * e = dyn_cast<Intersect>(re)) {
161        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
162    }
163    else if (isa<Any>(re)) {
164        return 1;
165    }
166    else if (isa<Name>(re)) {
167        return 1;
168    }
169    return 0; // otherwise
170}
171
172
173}
Note: See TracBrowser for help on using the repository browser.