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

Last change on this file since 6184 was 6171, checked in by cameron, 10 months ago

NullablePrefix/Suffix? removal using RE_Transformer; clean out some setters

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