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

Last change on this file since 3994 was 3955, checked in by daled, 5 years ago

icGREP now uses scanthru for multibyte unicode character classes.

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