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

Last change on this file since 4194 was 4194, checked in by nmedfort, 5 years ago

Modified RE module to use a LLVM-like dyn_cast system; added 'make' functions to hide RE constructors.

File size: 5.1 KB
Line 
1#include "re_nullable.h"
2#include "re_cc.h"
3#include "re_start.h"
4#include "re_end.h"
5#include "re_alt.h"
6#include "re_rep.h"
7#include "re_simplifier.h"
8
9/*
10
11 A regular expression is nullable if it (a) matches the empty
12 string, and (b) applies everywhere.  Note that Start (^) and
13 End ($) match the empty string, but not everywhere).
14
15*/
16
17namespace re {
18
19RE * RE_Nullable::removeNullablePrefix(RE * re) {
20    if (Seq * seq = dyn_cast<Seq>(re)) {
21        re = removeNullableSeqPrefix(seq);
22    }
23    else if (Alt * alt = dyn_cast<Alt>(re)) {
24        for (auto i = alt->begin(); i != alt->end(); ++i) {
25            *i = removeNullablePrefix(*i);
26        }
27        re = alt;
28    }
29    else if (Rep * rep = dyn_cast<Rep>(re)) {
30        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
31            re = makeSeq();
32        }
33        else if (hasNullablePrefix(rep->getRE())) {
34            Seq * seq = makeSeq();
35            seq->push_back(removeNullablePrefix(rep->getRE()));
36            seq->push_back(makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1));
37            re = RE_Simplifier::simplify(seq);
38        }
39        else {
40            re = RE_Simplifier::simplify(rep);
41        }
42    }
43    return re;
44}
45
46inline Seq * RE_Nullable::removeNullableSeqPrefix(const Seq * seq) {
47    Seq * new_seq = makeSeq(seq->getType());
48    if (!seq->empty()) {
49        auto i = seq->begin();
50        // find the first non-nullable prefix
51        while (i != seq->end() && isNullable(*i)) {
52            ++i;
53        }
54        if (i == seq->end()) {
55            return new_seq;
56        }
57        // push the first non-nullable seq item to the front of the new_seq
58        new_seq->push_back(removeNullablePrefix(*i));
59        std::copy(++i, seq->end(), std::back_inserter(*new_seq));
60    }
61    return new_seq;
62}
63
64RE * RE_Nullable::removeNullableSuffix(RE * re) {
65    if (Seq * seq = dyn_cast<Seq>(re)) {
66        re = removeNullableSeqSuffix(seq);
67    }
68    else if (Alt* alt = dyn_cast<Alt>(re)) {
69        for (auto i = alt->begin(); i != alt->end(); ++i) {
70            *i = removeNullableSuffix(*i);
71        }
72    }
73    else if (Rep * rep = dyn_cast<Rep>(re)) {
74        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
75            delete rep;
76            re = makeSeq();
77        }
78        else if (hasNullableSuffix(rep->getRE())) {
79            Seq * seq = makeSeq();
80            seq->push_back(RE_Simplifier::simplify(makeRep(rep->getRE()->clone(), rep->getLB() - 1, rep->getLB() - 1)));
81            seq->push_back(removeNullableSuffix(rep->getRE()));
82            delete rep;
83            re = RE_Simplifier::simplify(seq);
84        }
85        else {
86            re = RE_Simplifier::simplify(rep);
87        }
88    }
89    return re;
90}
91
92inline Seq * RE_Nullable::removeNullableSeqSuffix(const Seq * seq) {
93    Seq * new_seq = makeSeq(seq->getType());
94    if (!seq->empty()) {
95        auto i = seq->end();
96        // find the last non-nullable suffix
97        while (i != seq->begin() && isNullable(*--i));
98
99        if (i != seq->begin()) {
100            std::copy(seq->begin(), i, std::back_inserter(*new_seq));
101            new_seq->push_back(removeNullableSuffix(*i));
102        }
103    }
104    return new_seq;
105}
106
107bool RE_Nullable::isNullable(const RE * re) {
108    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
109        return isNullableVector(re_seq);
110    }
111    else if (const Alt* re_alt = dyn_cast<const Alt>(re)) {
112        return isNullableVector(re_alt);
113    }
114    else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
115        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
116    }
117    return false;
118}
119
120inline bool RE_Nullable::isNullableVector(const Vector * vec) {
121    for (const RE * re : *vec) {
122        if (!isNullable(re)) {
123            return false;
124        }
125    }
126    return true;
127}
128
129bool RE_Nullable::hasNullablePrefix(const RE * re) {
130    bool nullable = false;
131    if (const Seq * seq = dyn_cast<const Seq>(re)) {
132        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
133    }
134    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
135        if (!alt->empty()) {
136            nullable = true;
137            for (const RE * re : *alt) {
138                if (!hasNullablePrefix(re)) {
139                    nullable = false;
140                    break;
141                }
142            }
143        }
144    }
145    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
146        nullable = hasNullablePrefix(rep->getRE());
147    }
148    return nullable;
149}
150
151bool RE_Nullable::hasNullableSuffix(const RE * re) {
152    bool nullable = false;
153    if (const Seq * seq = dyn_cast<const Seq>(re)) {
154        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
155    }
156    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
157        if (!alt->empty()) {
158            nullable = true;
159            for (const RE * re : *alt) {
160                if (!hasNullableSuffix(re)) {
161                    nullable = false;
162                    break;
163                }
164            }
165        }
166    }
167    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
168        nullable = hasNullableSuffix(rep->getRE());
169    }
170    return nullable;
171}
172
173}
Note: See TracBrowser for help on using the repository browser.