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

Last change on this file was 6261, checked in by nmedfort, 6 months ago

Work on OptimizationBranch?; revisited pipeline termination

File size: 5.6 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 <re/re_toolchain.h>
12#include <re/validation.h>
13#include <vector>                  // for vector, allocator
14#include <llvm/Support/Casting.h>  // for dyn_cast, isa
15
16/*
17
18 A regular expression is nullable if it (a) matches the empty
19 string, and (b) applies everywhere.  Note that Start (^) and
20 End ($) match the empty string, but not everywhere).
21
22*/
23
24using namespace llvm;
25
26namespace re {
27
28bool isNullable(const RE * re) {
29    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
30        for (const RE * re : *re_seq) {
31            if (!isNullable(re)) {
32                return false;
33            }
34        }
35        return true;
36    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
37        for (const RE * re : *re_alt) {
38            if (isNullable(re)) {
39                return true;
40            }
41        }
42    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
43        return (re_rep->getLB() == 0) || isNullable(re_rep->getRE());
44    } else if (isa<Diff>(re)) {
45        // a Diff of Seq({}) and an Assertion represents a complemented assertion.
46        //return isNullable(d->getLH()) && (!isNullable(d->getRH())) && (!isZeroWidth(d->getRH()));
47        return false;
48    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
49        return isNullable(e->getLH()) && isNullable(e->getRH());
50    } else if (const Group * g = dyn_cast<const Group>(re)) {
51        return isNullable(g->getRE());
52    }
53    return false;
54}
55
56struct ZeroWidthValidator : public RE_Validator {
57    ZeroWidthValidator() : RE_Validator() {}
58    bool validateName(const Name * n) override {
59        RE * defn = n->getDefinition();
60        return defn && validate(defn);
61    }
62    bool validateAssertion(const Assertion * a) override {return true;}
63    bool validateCC(const CC *) override {return false;}
64    bool validateRange(const Range *) override {return false;}
65    bool validateDiff(const Diff * d) override {return validate(d->getLH());}
66    bool validateIntersect(const Intersect * x) override {return validate(x->getLH()) || validate(x->getRH());}
67};
68
69bool isZeroWidth(const RE * re) {
70    return ZeroWidthValidator().validateRE(re);
71}
72
73class NullablePrefixRemover: public RE_Transformer {
74protected:
75    RE * transformSeq(Seq * seq) override;
76    RE * transformRep(Rep * rep) override;
77    RE * transformAssertion(Assertion * a) override;
78public:
79    NullablePrefixRemover() : RE_Transformer("NullablePrefixRemoval") {}
80};
81
82RE * NullablePrefixRemover::transformSeq(Seq * seq) {
83    std::vector<RE*> list;
84    // if the sequence is empty, return it unmodified.
85    if (isNullable(seq)) return seq;
86    // Process the first element.
87    auto i = seq->begin();
88    auto e = transform(*i);
89    while (isNullable(e)) {
90        // Skip empty elements.
91        i++;
92        e = transform(*i);
93    }
94    // Special case: nothing skipped and first element unchanged.
95    if ((i == seq->begin()) && (e == *i)) return seq;
96    list.push_back(e);
97    i++;
98    while (i != seq->end()) {
99        list.push_back(*i);
100        i++;
101    }
102    return makeSeq(list.begin(), list.end());
103}
104
105RE * NullablePrefixRemover::transformRep(Rep * rep) {
106    auto lb = rep->getLB();
107    auto r = rep->getRE();
108    if ((lb == 0) || isNullable(r)) {
109        return makeSeq();
110    }
111    auto s = transform(r);
112    if ((s == r) && (lb == rep->getUB())) return rep; // special case.  No transformation required.
113    if (lb == 1) return s;
114    if (lb == 2) return makeSeq({s, r});
115    return makeSeq({s, makeRep(r, lb - 1, lb - 1)});
116}
117
118RE * NullablePrefixRemover::transformAssertion(Assertion * a) {
119    return a;
120}
121
122RE * removeNullablePrefix(RE * r) {
123    return NullablePrefixRemover().transformRE(r);
124}
125
126class NullableSuffixRemover: public RE_Transformer {
127protected:
128    RE * transformSeq(Seq * seq) override;
129    RE * transformRep(Rep * rep) override;
130    RE * transformAssertion(Assertion * a) override;
131public:
132    NullableSuffixRemover() : RE_Transformer("NullableSuffixRemoval") {}
133};
134
135RE * NullableSuffixRemover::transformSeq(Seq * seq) {
136    std::vector<RE*> list;
137    // if the sequence is empty, return it unmodified.
138    if (isNullable(seq)) return seq;
139    // Process the last element.
140    auto ri = seq->rbegin();
141    auto r = transform(*ri);
142    while (isNullable(r)) {
143        // Skip empty elements.
144        ri++;
145        r = transform(*ri);
146    }
147    // Special case: nothing skipped and first element unchanged.
148    if ((ri == seq->rbegin()) && (r == *ri)) return seq;
149    std::copy(seq->begin(), (ri + 1).base(), std::back_inserter(list));
150    list.push_back(r);
151    return makeSeq(list.begin(), list.end());
152}
153
154RE * NullableSuffixRemover::transformRep(Rep * rep) {
155    auto lb = rep->getLB();
156    auto r = rep->getRE();
157    if ((lb == 0) || isNullable(r)) {
158        return makeSeq();
159    }
160    auto s = transform(r);
161    if ((s == r) && (lb == rep->getUB())) return rep; // special case.  No transformation required.
162    if (lb == 1) return s;
163    if (lb == 2) return makeSeq({r, s});
164    return makeSeq({makeRep(r, lb - 1, lb - 1), s});
165}
166
167RE * NullableSuffixRemover::transformAssertion(Assertion * a) {
168    return a;
169}
170RE * removeNullableSuffix(RE * r) {
171    return NullableSuffixRemover().transformRE(r);
172}
173
174}
Note: See TracBrowser for help on using the repository browser.