source: icGREP/icgrep-devel/icgrep/re_simplifier.cpp @ 4133

Last change on this file since 4133 was 3998, checked in by cameron, 5 years ago

Preserve negated attribute

File size: 7.1 KB
Line 
1#include "re_simplifier.h"
2
3RE* RE_Simplifier::simplify(RE* re)
4{
5    RE* retVal = 0;
6
7    if (Alt* re_alt = dynamic_cast<Alt*>(re))
8    {
9        std::list<RE*> re_list;
10        std::list<RE*>::reverse_iterator rit = re_alt->GetREList()->rbegin();
11
12        for (rit = re_alt->GetREList()->rbegin(); rit != re_alt->GetREList()->rend(); ++rit)
13        {
14            re_list.push_back(simplify(*rit));
15        }
16
17        retVal = mkAlt(&re_list);
18    }
19    else if (Seq* re_seq = dynamic_cast<Seq*>(re))
20    {
21        std::list<RE*> re_list;
22        std::list<RE*>::iterator it;
23
24        for (it = re_seq->GetREList()->begin(); it != re_seq->GetREList()->end(); ++it)
25        {
26            re_list.push_front(simplify(*it));
27        }
28
29        retVal = mkSeq(re_seq->getType(), &re_list);
30    }
31    else if (CC* re_cc = dynamic_cast<CC*>(re))
32    {
33        retVal = re_cc;
34    }
35    else if (Name* re_name = dynamic_cast<Name*>(re))
36    {
37        Name* name = new Name(re_name->getName());
38        name->setType(re_name->getType());
39        name->setNegated(re_name->isNegated());   // TODO:  Hide this in the re_name module.
40        retVal = name;
41    }
42    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
43    {
44        retVal = mkRep(simplify(re_rep->getRE()), re_rep->getLB(), re_rep->getUB());
45    }
46    else if (Start* re_start = dynamic_cast<Start*>(re))
47    {
48        retVal = new Start();
49    }
50    else if (End* re_end = dynamic_cast<End*>(re))
51    {
52        retVal = new End();
53    }
54
55    return retVal;
56}
57
58RE* RE_Simplifier::mkSeq(Seq::Type type, std::list<RE*>* re_list)
59{
60    /*
61      mkSeq - make a sequence, but flatten.  Result might not be a Seq. If
62      there is only one component for a sequence, simply return that.
63    */
64
65    //We don't want to modify the AST that we are walking so we'll make a copy.
66    std::list<RE*>* t1_list = new std::list<RE*>();
67    //Linear in initial and final sizes.
68    t1_list->assign(re_list->begin(), re_list->end());
69    if (t1_list->size() > 0)
70    { 
71        std::list<RE*>* t2_list = mkSeqList(t1_list);
72        if (t2_list->size() > 1)
73        {
74            Seq* new_seq = new Seq(t2_list);
75            new_seq->setType(type);
76            return new_seq;
77        }
78        else
79        {
80            return t2_list->back();
81        }
82    }
83    else
84    {
85        return 0;
86    }
87}
88
89std::list<RE*>* RE_Simplifier::mkSeqList(std::list<RE*>* re_list)
90{
91    std::list<RE*>* ret_list = new std::list<RE*>();
92    return mkSeqList_helper(ret_list, re_list);
93}
94
95std::list<RE*>* RE_Simplifier::mkSeqList_helper(std::list<RE*>* ret_list, std::list<RE*>* re_list)
96{
97    /*
98      Build a list for Seq, flattening subsequences.
99    */
100
101    if (re_list->size() == 0)
102    {
103        return ret_list;
104    }
105    else if (Seq* seq = dynamic_cast<Seq*>(re_list->back()))
106    {
107        if (seq->getType() == Seq::Byte)
108        {
109            ret_list->push_front(re_list->back());
110            re_list->pop_back();
111            return mkSeqList_helper(ret_list, re_list);
112        }
113        else
114        {
115            re_list->pop_back();
116            seq->GetREList()->reverse();
117            re_list->insert(re_list->end(), seq->GetREList()->begin(), seq->GetREList()->end());
118
119            return mkSeqList_helper(ret_list, re_list);
120        }
121    }
122    else
123    {
124        ret_list->push_front(re_list->back());
125        re_list->pop_back();
126        return mkSeqList_helper(ret_list, re_list);
127    }
128}
129
130RE* RE_Simplifier::mkAlt(std::list<RE*>* re_list)
131{
132    /*
133      mkAlt - make a list of alternatives, but flatten, and combine character
134      classes.  If there is only one alternative, simply return that.
135    */
136
137    std::list<RE*>* t1_list = new std::list<RE*>();
138    t1_list->assign(re_list->begin(), re_list->end());
139    if (t1_list->size() > 0)
140    {
141        std::list<RE*>* t2_list = mkAltList(t1_list);
142        if (t2_list->size() > 1)
143        {
144            return new Alt(t2_list);
145        }
146        else
147        {
148            return t2_list->back();
149        }
150    }
151    else
152    {
153        return 0;
154    }
155}
156
157std::list<RE*>* RE_Simplifier::mkAltList(std::list<RE*>* re_list)
158{
159    std::list<RE*>* ret_list = new std::list<RE*>();
160    return mkAltList_helper(ret_list, re_list);
161}
162
163std::list<RE*>* RE_Simplifier::mkAltList_helper(std::list<RE*>* ret_list, std::list<RE*>* re_list)
164{
165    /*
166      Build a list for Alt, flattening alternative subgroups, and combining character classes.  We
167      move character classes towards the end of the list to ensure that all combinations are found.
168    */
169
170    if (re_list->size() == 0)
171    {
172        return ret_list;
173    }
174    else if (Alt* alt = dynamic_cast<Alt*>(re_list->back()))
175    {
176        re_list->pop_back();
177        re_list->insert(re_list->end(), alt->GetREList()->begin(), alt->GetREList()->end());
178        return mkAltList_helper(ret_list, re_list);
179    }
180    else if (re_list->size() >= 2)
181    {
182        std::list<RE*>::iterator it;
183        it = re_list->end();
184        it--;
185        if (CC* cc1 = dynamic_cast<CC*>(*it))
186        {
187            it--;
188            if(CC* cc2 = dynamic_cast<CC*>(*it))
189            {
190                CC* cc = new CC(cc1, cc2);
191                re_list->pop_back();
192                re_list->pop_back();
193                re_list->push_back(cc);
194                return mkAltList_helper(ret_list, re_list);
195            }
196            else
197            {
198                std::list<RE*>::iterator item1 = re_list->end();
199                --item1;
200                std::list<RE*>::iterator item2 = item1;
201                --item2;
202                std::swap(*item1, *item2);
203                return mkAltList_helper(ret_list, re_list);
204            }
205        }
206        ret_list->push_front(re_list->back());
207        re_list->pop_back();
208        return mkAltList_helper(ret_list, re_list);
209    }
210    else
211    {
212        ret_list->push_front(re_list->back());
213        re_list->pop_back();
214        return mkAltList_helper(ret_list, re_list);
215    }
216}
217
218int RE_Simplifier::ubCombine(int h1, int h2)
219{
220    if ((h1 == unboundedRep) || (h2 == unboundedRep))
221    {
222        return unboundedRep;
223    }
224    else
225    {
226        return h1 * h2;
227    }
228}
229
230RE* RE_Simplifier::mkRep(RE* re, int lb2, int ub2)
231{
232    if (Rep* rep = dynamic_cast<Rep*>(re))
233    {
234        if (((rep->getUB() == unboundedRep) && (lb2 > 0)) ||
235                ((rep->getUB() == unboundedRep) && (rep->getLB() <= 1)))
236        {
237            return new Rep(rep->getRE(), rep->getLB() * lb2, unboundedRep);
238        }
239        else if ((rep->getUB() == unboundedRep) && (lb2 == 0))
240        {
241            return new Rep(rep, 0, 1);
242        }
243        else if ((rep->getUB() * lb2) >= (rep->getLB() * (lb2 + 1) - 1))
244        {
245            return new Rep(rep->getRE(), rep->getLB() * lb2, ubCombine(rep->getUB(), ub2));
246        }
247        else
248        {
249            return new Rep(rep, lb2, ub2);
250        }
251    }
252    else
253    {
254        if (Seq* seq = dynamic_cast<Seq*>(re))
255        {
256            if(seq->GetREList()->size() == 0)
257            {
258                return seq;
259            }
260        }
261
262        if ((lb2 == 0) && (ub2 == 0))
263        {
264            return new Seq();
265        }
266        else if ((lb2 == 1) && (ub2 == 1))
267        {
268            return re;
269        }
270        else
271        {
272            return new Rep(re, lb2, ub2);
273        }
274    }
275}
Note: See TracBrowser for help on using the repository browser.