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

Last change on this file was 5736, checked in by cameron, 5 days ago

Bug fixes for empty sequences

File size: 6.9 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            UndefinedNameError(name);
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            UndefinedNameError(name);
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            UndefinedNameError(name);
121        }
122    } else if (Seq * seq = dyn_cast<Seq>(re)) {
123        if (seq->size() > 0) {
124            RE * re_first = *(seq->begin());
125            RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
126            auto e1 = final(re_first);
127            auto e2 = first(re_follow);
128            if (e1 && e2) {
129                auto e = follow_map.find(e1);
130                if (e != follow_map.end()) {
131                    e->second = makeCC(e->second, e2);
132                } else {
133                    follow_map.emplace(e1, e2);
134                }
135            }
136            follow(re_first, follow_map);
137            follow(re_follow, follow_map);
138        }
139    } else if (Alt * alt = dyn_cast<Alt>(re)) {
140        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
141            follow(*ai, follow_map);
142        }
143    } else if (Rep * rep = dyn_cast<Rep>(re)) {
144        auto e1 = final(rep->getRE());
145        auto e2 = first(rep->getRE());
146        if (e1 && e2) {
147            auto e = follow_map.find(e1);
148            if (e != follow_map.end()) {
149                e->second = makeCC(e->second, e2);
150            } else {
151                follow_map.emplace(e1, e2);
152            }
153        }
154        follow(rep->getRE(), follow_map);
155    }
156}
157
158bool RE_Local::isLocalLanguage(RE * re) {
159    UCD::UnicodeSet seen = UCD::UnicodeSet();
160    return isLocalLanguage_helper(re, seen);
161}
162
163bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen) {
164    assert ("RE object cannot be null!" && re);
165    if (isa<Any>(re)) {
166        const bool no_intersect = seen.empty();
167        seen = UCD::UnicodeSet(0x00, 0x10FFFF);
168        return no_intersect;
169    } else if (const CC * cc = dyn_cast<CC>(re)) {
170        const bool has_intersect = cast<CC>(cc)->intersects(seen);
171        seen = seen + *cast<CC>(cc);
172        return !has_intersect;
173    } else if (const Name * n = dyn_cast<Name>(re)) {
174        return isLocalLanguage_helper(n->getDefinition(), seen);
175    } else if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
176        for (const RE * item : *re_seq) {
177            if (!isLocalLanguage_helper(item, seen)) return false;
178        }
179        return true;
180    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
181        for (RE * item : *re_alt) {
182            if (!isLocalLanguage_helper(item, seen)) return false;
183        }
184        return true;
185    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
186        if (re_rep->getUB() > 1) return false;
187        return isLocalLanguage_helper(re_rep->getRE(), seen);
188    } else {
189        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
190        return false;
191    }
192}
193
194bool RE_Local::isNullable(const RE * re) {
195    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
196        for (const RE * re : *re_seq) {
197            if (!isNullable(re)) {
198                return false;
199            }
200        }
201        return true;
202    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
203        for (const RE * re : *re_alt) {
204            if (isNullable(re)) {
205                return true;
206            }
207        }
208    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
209        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
210    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
211        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
212    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
213        return isNullable(e->getLH()) && isNullable(e->getRH());
214    } 
215    return false;
216}
217
218}
Note: See TracBrowser for help on using the repository browser.