# source:icGREP/icgrep-devel/icgrep/re/re_nullable.cpp@5997

Last change on this file since 5997 was 5891, checked in by cameron, 20 months ago

Byte test complexity analysis

File size: 7.5 KB
Line
1#include "re_nullable.h"
2#include <re/re_alt.h>             // for Alt, makeAlt
3#include <re/re_any.h>             // for makeAny, Any
4#include <re/re_assertion.h>       // for Assertion, Assertion::Sense, Asser...
5#include <re/re_diff.h>            // for Diff, makeDiff
6#include <re/re_intersect.h>       // for Intersect
7#include <re/re_name.h>            // for Name
8#include <re/re_rep.h>             // for Rep, makeRep
9#include <re/re_seq.h>             // for Seq, makeSeq
10#include <re/re_group.h>             // for Seq, makeSeq
11#include <vector>                  // for vector, allocator
12#include <llvm/Support/Casting.h>  // for dyn_cast, isa
13
14/*
15
16 A regular expression is nullable if it (a) matches the empty
17 string, and (b) applies everywhere.  Note that Start (^) and
18 End (\$) match the empty string, but not everywhere).
19
20*/
21
22using namespace llvm;
23
24namespace re {
25
26
27RE * RE_Nullable::excludeNullable(RE * re) {
28    if (!isNullable(re)) return re;
29    if (Seq * seq = dyn_cast<Seq>(re)) {
30        // All items in the seq must be nullable.  We must allow
31        // all possibilities that all but one continue to match empty.
32        std::vector<RE*> alts;
33        for (auto i = 0; i < seq->size(); i++) {
34            std::vector<RE*> list;
35            for (auto j = 0; j < seq->size(); j++) {
36                if (i == j) {
37                    list.push_back(excludeNullable(&seq[j]));
38                } else {
39                    list.push_back(&seq[j]);
40                }
41            }
42            alts.push_back(makeSeq(list.begin(), list.end()));
43        }
44        return makeAlt(alts.begin(), alts.end());
45    } else if (Alt * alt = dyn_cast<Alt>(re)) {
46        std::vector<RE*> list;
47        for (auto i = alt->begin(); i != alt->end(); ++i) {
48            list.push_back(excludeNullable(*i));
49        }
50        return makeAlt(list.begin(), list.end());
51    } else if (Rep * rep = dyn_cast<Rep>(re)) {
52        auto lb = rep->getLB();
53        auto ub = rep->getUB();
54        auto e = rep->getRE();
55        if (!isNullable(e)) {
56            assert (lb == 0);  // because isNullable(re) is true
57            return makeRep(e, 1, ub);
58        }
59        auto e1 = excludeNullable(e);
60        if (ub == 1) {
61            return e1;
62        } else {
63            return makeSeq({e1, makeRep(e, lb == 0 ? 0 : lb - 1, ub == Rep::UNBOUNDED_REP ? ub : ub - 1)});
64        }
65    } else if (Group * g = dyn_cast<Group>(re)) {
66        return makeGroup(g->getMode(), excludeNullable(g->getRE()), g->getSense());
67    } else if (Name * name = dyn_cast<Name>(re)) {
68        return excludeNullable(name->getDefinition());
69    }
70    return re;
71}
72
73
74RE * RE_Nullable::removeNullablePrefix(RE * re) {
75    if (!hasNullablePrefix(re)) return re;
76    if (Seq * seq = dyn_cast<Seq>(re)) {
77        std::vector<RE*> list;
78        for (auto i = seq->begin(); i != seq->end(); ++i) {
79            if (!isNullable(*i)) {
80                list.push_back(removeNullablePrefix(*i));
81                std::copy(++i, seq->end(), std::back_inserter(list));
82                break;
83            }
84        }
85        return makeSeq(list.begin(), list.end());
86    } else if (Alt * alt = dyn_cast<Alt>(re)) {
87        std::vector<RE*> list;
88        for (auto i = alt->begin(); i != alt->end(); ++i) {
89            list.push_back(removeNullablePrefix(*i));
90        }
91        return makeAlt(list.begin(), list.end());
92    } else if (Rep * rep = dyn_cast<Rep>(re)) {
93        auto lb = rep->getLB();
94        auto e = rep->getRE();
95        if ((lb == 0) || isNullable(e)) {
96            return makeSeq();
97        }
98        else if (hasNullablePrefix(e)) {
99            return makeSeq({removeNullablePrefix(e), makeRep(e, lb - 1, lb - 1)});
100        }
101        else {
102            return makeRep(e, lb, lb);
103        }
104    } else if (Name * name = dyn_cast<Name>(re)) {
105        auto def = name->getDefinition();
106        if (hasNullablePrefix(def)) {
107            return removeNullablePrefix(def);
108        }
109    }
110    return re;
111}
112
113RE * RE_Nullable::removeNullableSuffix(RE * re) {
114    if (Seq * seq = dyn_cast<Seq>(re)) {
115        std::vector<RE*> list;
116        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
117            if (!isNullable(*i)) {
118                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
119                list.push_back(removeNullableSuffix(*i));
120                break;
121            }
122        }
123        return makeSeq(list.begin(), list.end());
124    } else if (Alt* alt = dyn_cast<Alt>(re)) {
125        std::vector<RE*> list;
126        for (auto i = alt->begin(); i != alt->end(); ++i) {
127            list.push_back(removeNullableSuffix(*i));
128        }
129        return makeAlt(list.begin(), list.end());
130    } else if (Rep * rep = dyn_cast<Rep>(re)) {
131        auto lb = rep->getLB();
132        auto e = rep->getRE();
133        if ((lb == 0) || isNullable(e)) {
134            return makeSeq();
135        }
136        else if (hasNullableSuffix(e)) {
137            return makeSeq({makeRep(e, lb - 1, lb - 1), removeNullableSuffix(e)});
138        }
139        else {
140            return makeRep(e, lb, lb);
141        }
142    } else if (Name * name = dyn_cast<Name>(re)) {
143        auto def = name->getDefinition();
144        if (hasNullableSuffix(def)) {
145            return removeNullableSuffix(def);
146        }
147    }
148    return re;
149}
150
151bool RE_Nullable::isNullable(const RE * re) {
152    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
153        for (const RE * re : *re_seq) {
154            if (!isNullable(re)) {
155                return false;
156            }
157        }
158        return true;
159    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
160        for (const RE * re : *re_alt) {
161            if (isNullable(re)) {
162                return true;
163            }
164        }
165    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
166        return (re_rep->getLB() == 0) || isNullable(re_rep->getRE());
167    } else if (isa<Diff>(re)) {
168        // a Diff of Seq({}) and an Assertion represents a complemented assertion.
169        return false;
170    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
171        return isNullable(e->getLH()) && isNullable(e->getRH());
172    } else if (const Group * g = dyn_cast<const Group>(re)) {
173        return isNullable(g->getRE());
174    }
175    return false;
176}
177
178bool RE_Nullable::hasNullablePrefix(const RE * re) {
179    if (const Seq * seq = dyn_cast<const Seq>(re)) {
180        if (seq->empty()) return false;
181        return isNullable(seq->front()) || hasNullablePrefix(seq->front());
182    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
183        for (const RE * a : *alt) {
184            if (hasNullablePrefix(a)) {
185                return true;
186            }
187        }
188        return false;
189    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
190        return (rep->getLB() != rep->getUB()) || hasNullablePrefix(rep->getRE());
191    } else if (const Group * g = dyn_cast<const Group>(re)) {
192        return hasNullablePrefix(g->getRE());
193    }
194    return false;
195}
196
197bool RE_Nullable::hasNullableSuffix(const RE * re) {
198    if (const Seq * seq = dyn_cast<const Seq>(re)) {
199        if (seq->empty()) return false;
200        return isNullable(seq->back()) || hasNullableSuffix(seq->back());
201    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
202        for (const RE * a : *alt) {
203            if (hasNullableSuffix(a)) {
204                return true;
205            }
206        }
207        return false;
208    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
209        return (rep->getLB() != rep->getUB()) || hasNullableSuffix(rep->getRE());
210    } else if (const Group * g = dyn_cast<const Group>(re)) {
211        return hasNullableSuffix(g->getRE());
212    }
213    return false;
214}
215
216}
Note: See TracBrowser for help on using the repository browser.