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

Last change on this file since 5569 was 5569, checked in by xuedongx, 22 months ago

delete comments

File size: 10.8 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 <map>
15
16using namespace boost::container;
17using namespace llvm;
18
19namespace re {
20 
21UCD::UnicodeSet* RE_Local::first(RE * re) {
22    if (Name * name = dyn_cast<Name>(re)) {
23        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
24            if (CC * cc = dyn_cast<CC>(name->getDefinition())) {
25                UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
26                return sets;
27            } else {
28                return first(name->getDefinition());
29            }
30        } else {
31            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
32        }
33    } else if (CC * cc = dyn_cast<CC>(re)) {
34        UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
35        return sets;
36    } else if (Seq * seq = dyn_cast<Seq>(re)) {
37        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
38        UCD::UnicodeSet UnicodeSets_seq = UCD::UnicodeSet();
39        for (auto si = seq->begin(); si != seq->end(); ++si) {
40            if (isNullable(*si) && first(*si) != nullptr) {
41                UnicodeSets_seq = UnicodeSets_seq + *(first(*si));
42            } else if (isNullable(*si) && first(*si) == nullptr) {
43                continue;
44            } else if (!isNullable(*si) && first(*si) != nullptr){
45                UnicodeSets_seq = UnicodeSets_seq + *(first(*si));
46                break;
47            } else {
48                break;
49            }
50        }
51        *UnicodeSets = UnicodeSets_seq;
52        return UnicodeSets_seq.empty() ? nullptr : UnicodeSets;
53    } else if (Alt * alt = dyn_cast<Alt>(re)) {
54        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
55        UCD::UnicodeSet UnicodeSets_alt = UCD::UnicodeSet();
56        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
57            if (first(*ai) != nullptr) {
58                UnicodeSets_alt = UnicodeSets_alt + *(first(*ai));
59            }
60        }
61        *UnicodeSets = UnicodeSets_alt;
62        return UnicodeSets_alt.empty() ? nullptr : UnicodeSets;
63    } else if (Rep * rep = dyn_cast<Rep>(re)) {
64        return first(rep->getRE());
65    } else if (Diff * diff = dyn_cast<Diff>(re)) {
66        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
67        UCD::UnicodeSet UnicodeSets_diff = UCD::UnicodeSet();
68        if (first(diff->getLH()) && first(diff->getRH())) {
69            UnicodeSets_diff = *(first(diff->getLH())) - *(first(diff->getRH()));
70        }
71        *UnicodeSets = UnicodeSets_diff;
72        return UnicodeSets;
73    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
74        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
75        UCD::UnicodeSet UnicodeSets_inter = UCD::UnicodeSet();
76        if (first(ix->getLH()) && first(ix->getRH())) {
77            UnicodeSets_inter = *(first(ix->getLH())) & *(first(ix->getRH()));
78        }
79        *UnicodeSets = UnicodeSets_inter;
80        return UnicodeSets;
81    }
82    return nullptr;
83
84}
85
86UCD::UnicodeSet* RE_Local::final(RE * re) {
87    if (Name * name = dyn_cast<Name>(re)) {
88        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
89            if (CC * cc = dyn_cast<CC>(name->getDefinition())) {
90                UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
91                return sets;
92            } else {
93                return final(name->getDefinition());
94            }
95        } else {
96            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
97        }
98    } else if (CC * cc = dyn_cast<CC>(re)) {
99        UCD::UnicodeSet * sets = cast<UCD::UnicodeSet>(cc);
100        return sets;
101    } else if (Seq * seq = dyn_cast<Seq>(re)) {
102        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
103        UCD::UnicodeSet UnicodeSets_seq = UCD::UnicodeSet();
104        for (auto si = seq->rbegin(); si != seq->rend(); ++si) {
105            if (isNullable(*si) && final(*si) != nullptr) {
106                UnicodeSets_seq = UnicodeSets_seq + *(final(*si));
107            } else if (isNullable(*si) && final(*si) == nullptr) {
108                continue;
109            } else if (!isNullable(*si) && final(*si) != nullptr){
110                UnicodeSets_seq = UnicodeSets_seq + *(final(*si));
111                break;
112            } else {
113                break;
114            }
115        }
116        *UnicodeSets = UnicodeSets_seq;
117        return UnicodeSets_seq.empty() ? nullptr : UnicodeSets;
118    } else if (Alt * alt = dyn_cast<Alt>(re)) {
119        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
120        UCD::UnicodeSet UnicodeSets_alt = UCD::UnicodeSet();
121        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
122            if (final(*ai) != nullptr) {
123                UnicodeSets_alt = UnicodeSets_alt + *(final(*ai));
124            }
125        }
126        *UnicodeSets = UnicodeSets_alt;
127        return UnicodeSets_alt.empty() ? nullptr : UnicodeSets;
128    } else if (Rep * rep = dyn_cast<Rep>(re)) {
129        return final(rep->getRE());
130    } else if (Diff * diff = dyn_cast<Diff>(re)) {
131        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
132        UCD::UnicodeSet UnicodeSets_diff = UCD::UnicodeSet();
133        if (final(diff->getLH()) && final(diff->getRH())) {
134            UnicodeSets_diff = *(final(diff->getLH())) - *(final(diff->getRH()));
135        }
136        *UnicodeSets = UnicodeSets_diff;
137        return UnicodeSets;
138    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
139        UCD::UnicodeSet * UnicodeSets = new UCD::UnicodeSet();
140        UCD::UnicodeSet UnicodeSets_inter = UCD::UnicodeSet();
141        if (final(ix->getLH()) && final(ix->getRH())) {
142            UnicodeSets_inter = *(final(ix->getLH())) & *(final(ix->getRH()));
143        }
144        *UnicodeSets = UnicodeSets_inter;
145        return UnicodeSets;
146    }
147    return nullptr;
148
149}
150
151void RE_Local::follow(RE * re, std::map<UCD::UnicodeSet*, UCD::UnicodeSet*> &follow_map) {
152    if (Name * name = dyn_cast<Name>(re)) {
153        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
154            return follow(name->getDefinition(), follow_map);
155        } else {
156            throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
157        }
158    } else if (Seq * seq = dyn_cast<Seq>(re)) {
159        RE * re_first = *(seq->begin());
160        std::vector<RE *> list;
161        list.reserve(seq->size());
162        for (auto i = seq->begin() + 1; i != seq->end(); i++) {
163            list.push_back(*i);
164        }
165        RE * re_follow = makeSeq(list.begin(), list.end());
166        follow(re_first, follow_map);
167        follow(re_follow, follow_map);
168        auto e1 = final(re_first);
169        auto e2 = first(re_follow);
170        if (e1 && e2) {
171            auto e = follow_map.find(e1);
172            if (e != follow_map.end()) {
173                *(e->second) = *(e->second) + *e2;
174            } else {
175                follow_map.insert(std::pair<UCD::UnicodeSet*, UCD::UnicodeSet*>(e1, e2));
176            }
177        }
178        return;
179    } else if (Alt * alt = dyn_cast<Alt>(re)) {
180        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
181            follow(*ai, follow_map);
182        }
183        return;
184    } else if (Rep * rep = dyn_cast<Rep>(re)) {
185        follow(rep->getRE(), follow_map);
186        auto e1 = final(rep->getRE());
187        auto e2 = first(rep->getRE());
188        if (e1 && e2) {
189            auto e = follow_map.find(e1);
190            if (e != follow_map.end()) {
191                *(e->second) = *(e->second) + *e2;
192            } else {
193                follow_map.insert(std::pair<UCD::UnicodeSet*, UCD::UnicodeSet*>(e1, e2));
194            }
195        }
196        return;
197    }
198    return;
199}
200
201bool RE_Local::isLocalLanguage(RE * re) {
202    std::vector<UCD::UnicodeSet> UnicodeSets;
203    collect_UnicodeSets_helper(re, UnicodeSets);
204    if (UnicodeSets.size() == 0) return false;
205    for (unsigned i = 0; i < UnicodeSets.size(); i++) {
206        for (unsigned j = i + 1; j < UnicodeSets.size(); j++) {
207            for (const UCD::UnicodeSet::interval_t & range : UnicodeSets[i]) {
208                auto lo = re::lo_codepoint(range);
209                auto hi = re::hi_codepoint(range);
210                if (UnicodeSets[j].intersects(lo, hi)) {
211                    return false;
212                }
213            }
214        }
215    }
216    return true;
217}
218
219
220RE * RE_Local::collect_UnicodeSets_helper(RE * re, std::vector<UCD::UnicodeSet> & UnicodeSets) {
221    assert ("RE object cannot be null!" && re);
222    if (isa<Name>(re)) {
223        if (CC * cc = dyn_cast<CC>(cast<Name>(re)->getDefinition())) {
224            UnicodeSets.push_back(* cast<UCD::UnicodeSet>(cc));
225        } else {
226            collect_UnicodeSets_helper(cast<Name>(re)->getDefinition(), UnicodeSets);
227        }
228    } else if (isa<Seq>(re)) {
229        for (RE * item : *cast<Seq>(re)) {
230            collect_UnicodeSets_helper(item, UnicodeSets);
231        }
232    } else if (isa<Alt>(re)) {
233        for (RE * item : *cast<Alt>(re)) {
234            collect_UnicodeSets_helper(item, UnicodeSets);
235        }
236    } else if (isa<Rep>(re)) {
237        collect_UnicodeSets_helper(cast<Rep>(re)->getRE(), UnicodeSets);
238    } else if (isa<Assertion>(re)) {
239        collect_UnicodeSets_helper(cast<Assertion>(re)->getAsserted(), UnicodeSets);
240    } else if (isa<Diff>(re)) {
241        collect_UnicodeSets_helper(cast<Diff>(re)->getLH(), UnicodeSets);
242        collect_UnicodeSets_helper(cast<Diff>(re)->getRH(), UnicodeSets);
243    } else if (isa<Intersect>(re)) {
244        collect_UnicodeSets_helper(cast<Intersect>(re)->getLH(), UnicodeSets);
245        collect_UnicodeSets_helper(cast<Intersect>(re)->getRH(), UnicodeSets);
246    } else if (isa<Any>(re)) {
247        UnicodeSets.push_back(UCD::UnicodeSet(0x00, 0x10FFFF));
248    } else if (isa<Any>(re)) {
249        UnicodeSets.push_back(UCD::UnicodeSet(0x00, 0x10FFFF));
250    }
251    return re;
252}
253
254bool RE_Local::isNullable(const RE * re) {
255    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
256        for (const RE * re : *re_seq) {
257            if (!isNullable(re)) {
258                return false;
259            }
260        }
261        return true;
262    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
263        for (const RE * re : *re_alt) {
264            if (isNullable(re)) {
265                return true;
266            }
267        }
268    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
269        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
270    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
271        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
272    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
273        return isNullable(e->getLH()) && isNullable(e->getRH());
274    } 
275    return false;
276}
277
278}
Note: See TracBrowser for help on using the repository browser.