source: icGREP/icgrep-devel/icgrep/re/re_local.cpp

Last change on this file was 5632, checked in by cameron, 2 weeks ago

Optimizations for re_local

File size: 7.2 KB
Line 
1#include "re_local.h"
2#include <re/re_name.h>
3#include <re/re_alt.h>
4#include <re/re_cc.h>
5#include <re/re_seq.h>
6#include <re/re_rep.h>
7#include <re/re_diff.h>
8#include <re/re_intersect.h>
9#include <re/re_assertion.h>
10#include <re/re_any.h>
11#include <re/re_analysis.h>
12#include <UCD/resolve_properties.h>
13#include <boost/container/flat_set.hpp>
14#include <boost/range/adaptor/reversed.hpp>
15#include <map>
16
17using namespace boost::container;
18using namespace llvm;
19
20namespace re {
21 
22inline void combine(CC *& a, CC * b) {
23    if (a && b) {
24        a = makeCC(a, b);
25    } else if (b) {
26        a = b;
27    }
28}
29
30CC * RE_Local::first(RE * re) {
31    if (Name * name = dyn_cast<Name>(re)) {
32        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
33            return first(name->getDefinition());
34        } else {
35            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
36        }
37    } else if (CC * cc = dyn_cast<CC>(re)) {
38        return cc;
39    } else if (Seq * seq = dyn_cast<Seq>(re)) {
40        CC * cc = nullptr;
41        for (auto & si : *seq) {
42            combine(cc, first(si));
43            if (!isNullable(si)) {
44                break;
45            }
46        }
47        return cc;
48    } else if (Alt * alt = dyn_cast<Alt>(re)) {
49        CC * cc = nullptr;
50        for (auto & ai : *alt) {
51            combine(cc, first(ai));
52        }
53        return cc;
54    } else if (Rep * rep = dyn_cast<Rep>(re)) {
55        return first(rep->getRE());
56    } else if (Diff * diff = dyn_cast<Diff>(re)) {
57        if (CC * lh = first(diff->getLH())) {
58            if (CC * rh = first(diff->getRH())) {
59                return subtractCC(lh, rh);
60            }
61        }
62    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
63        if (CC * lh = first(ix->getLH())) {
64            if (CC * rh = first(ix->getRH())) {
65                return intersectCC(lh, rh);
66            }
67        }
68    }
69    return nullptr;
70}
71
72CC * RE_Local::final(RE * re) {
73    if (Name * name = dyn_cast<Name>(re)) {
74        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
75            return final(name->getDefinition());
76        } else {
77            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
78        }
79    } else if (CC * cc = dyn_cast<CC>(re)) {
80        return cc;
81    } else if (Seq * seq = dyn_cast<Seq>(re)) {
82        CC * cc = nullptr;
83        for (auto & si : boost::adaptors::reverse(*seq)) {
84            combine(cc, first(si));
85            if (!isNullable(si)) {
86                break;
87            }
88        }
89        return cc;
90    } else if (Alt * alt = dyn_cast<Alt>(re)) {
91        CC * cc = nullptr;
92        for (auto & ai : *alt) {
93            combine(cc, final(ai));
94        }
95        return cc;
96    } else if (Rep * rep = dyn_cast<Rep>(re)) {
97        return final(rep->getRE());
98    } else if (Diff * diff = dyn_cast<Diff>(re)) {
99        if (CC * lh = final(diff->getLH())) {
100            if (CC * rh = final(diff->getRH())) {
101                return subtractCC(lh, rh);
102            }
103        }
104    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
105        if (CC * lh = final(ix->getLH())) {
106            if (CC * rh = final(ix->getRH())) {
107                return intersectCC(lh, rh);
108            }
109        }
110    }
111    return nullptr;
112
113}
114
115void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
116    if (Name * name = dyn_cast<Name>(re)) {
117        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
118            return follow(name->getDefinition(), follow_map);
119        } else {
120            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
121        }
122    } else if (Seq * seq = dyn_cast<Seq>(re)) {
123        RE * re_first = *(seq->begin());
124        RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
125        auto e1 = final(re_first);
126        auto e2 = first(re_follow);
127        if (e1 && e2) {
128            auto e = follow_map.find(e1);
129            if (e != follow_map.end()) {
130                e->second = makeCC(e->second, e2);
131            } else {
132                follow_map.emplace(e1, e2);
133            }
134        }
135        follow(re_first, follow_map);
136        follow(re_follow, follow_map);
137    } else if (Alt * alt = dyn_cast<Alt>(re)) {
138        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
139            follow(*ai, follow_map);
140        }
141    } else if (Rep * rep = dyn_cast<Rep>(re)) {
142        auto e1 = final(rep->getRE());
143        auto e2 = first(rep->getRE());
144        if (e1 && e2) {
145            auto e = follow_map.find(e1);
146            if (e != follow_map.end()) {
147                e->second = makeCC(e->second, e2);
148            } else {
149                follow_map.emplace(e1, e2);
150            }
151        }
152        follow(rep->getRE(), follow_map);
153    }
154}
155
156bool RE_Local::isLocalLanguage(RE * re) {
157    UCD::UnicodeSet seen = UCD::UnicodeSet();
158    return isLocalLanguage_helper(re, seen);
159}
160
161bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & codepoints_seen) {
162    assert ("RE object cannot be null!" && re);
163    if (isa<Any>(re)) {
164        bool no_intersect = codepoints_seen.empty();
165        codepoints_seen = UCD::UnicodeSet(0x00, 0x10FFFF);
166        return no_intersect;
167    } else if (const CC * cc = dyn_cast<CC>(re)) {
168        bool has_intersect = cast<UCD::UnicodeSet>(cc)->intersects(codepoints_seen);
169        codepoints_seen = codepoints_seen + *cast<UCD::UnicodeSet>(cc);
170        return !has_intersect;
171    } else if (const Name * n = dyn_cast<Name>(re)) {
172        return isLocalLanguage_helper(n->getDefinition(), codepoints_seen);
173    } else if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
174        for (const RE * item : *re_seq) {
175            if (!isLocalLanguage_helper(item, codepoints_seen)) return false;
176        }
177        return true;
178    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
179        for (RE * item : *re_alt) {
180            if (!isLocalLanguage_helper(item, codepoints_seen)) return false;
181        }
182        return true;
183    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
184        if (re_rep->getUB() > 1) return false;
185        return isLocalLanguage_helper(re_rep->getRE(), codepoints_seen);
186    } else {
187        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
188        return false;
189    }
190}
191
192bool RE_Local::isNullable(const RE * re) {
193    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
194        for (const RE * re : *re_seq) {
195            if (!isNullable(re)) {
196                return false;
197            }
198        }
199        return true;
200    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
201        for (const RE * re : *re_alt) {
202            if (isNullable(re)) {
203                return true;
204            }
205        }
206    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
207        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
208    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
209        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
210    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
211        return isNullable(e->getLH()) && isNullable(e->getRH());
212    } 
213    return false;
214}
215
216}
Note: See TracBrowser for help on using the repository browser.