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

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

The framework for the unicode categories is in place. The static c++ code for each of the categories just needs to be placed into the stub unicode categories class.

File size: 6.8 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        re_list->pop_back();
107        seq->GetREList()->reverse();
108        re_list->insert(re_list->end(), seq->GetREList()->begin(), seq->GetREList()->end());
109
110        return mkSeqList_helper(ret_list, re_list);
111    }
112    else
113    {
114        ret_list->push_front(re_list->back());
115        re_list->pop_back();
116        return mkSeqList_helper(ret_list, re_list);
117    }
118}
119
120RE* RE_Simplifier::mkAlt(std::list<RE*>* re_list)
121{
122    /*
123      mkAlt - make a list of alternatives, but flatten, and combine character
124      classes.  If there is only one alternative, simply return that.
125    */
126
127    std::list<RE*>* t1_list = new std::list<RE*>();
128    t1_list->assign(re_list->begin(), re_list->end());
129    if (t1_list->size() > 0)
130    {
131        std::list<RE*>* t2_list = mkAltList(t1_list);
132        if (t2_list->size() > 1)
133        {
134            return new Alt(t2_list);
135        }
136        else
137        {
138            return t2_list->back();
139        }
140    }
141    else
142    {
143        return 0;
144    }
145}
146
147std::list<RE*>* RE_Simplifier::mkAltList(std::list<RE*>* re_list)
148{
149    std::list<RE*>* ret_list = new std::list<RE*>();
150    return mkAltList_helper(ret_list, re_list);
151}
152
153std::list<RE*>* RE_Simplifier::mkAltList_helper(std::list<RE*>* ret_list, std::list<RE*>* re_list)
154{
155    /*
156      Build a list for Alt, flattening alternative subgroups, and combining character classes.  We
157      move character classes towards the end of the list to ensure that all combinations are found.
158    */
159
160    if (re_list->size() == 0)
161    {
162        return ret_list;
163    }
164    else if (Alt* alt = dynamic_cast<Alt*>(re_list->back()))
165    {
166        re_list->pop_back();
167        re_list->insert(re_list->end(), alt->GetREList()->begin(), alt->GetREList()->end());
168        return mkAltList_helper(ret_list, re_list);
169    }
170    else if (re_list->size() >= 2)
171    {
172        std::list<RE*>::iterator it;
173        it = re_list->end();
174        it--;
175        if (CC* cc1 = dynamic_cast<CC*>(*it))
176        {
177            it--;
178            if(CC* cc2 = dynamic_cast<CC*>(*it))
179            {
180                CC* cc = new CC(cc1, cc2);
181                re_list->pop_back();
182                re_list->pop_back();
183                re_list->push_back(cc);
184                return mkAltList_helper(ret_list, re_list);
185            }
186            else
187            {
188                std::list<RE*>::iterator item1 = re_list->end();
189                --item1;
190                std::list<RE*>::iterator item2 = item1;
191                --item2;
192                std::swap(*item1, *item2);
193                return mkAltList_helper(ret_list, re_list);
194            }
195        }
196        ret_list->push_front(re_list->back());
197        re_list->pop_back();
198        return mkAltList_helper(ret_list, re_list);
199    }
200    else
201    {
202        ret_list->push_front(re_list->back());
203        re_list->pop_back();
204        return mkAltList_helper(ret_list, re_list);
205    }
206}
207
208int RE_Simplifier::ubCombine(int h1, int h2)
209{
210    if ((h1 == unboundedRep) || (h2 == unboundedRep))
211    {
212        return unboundedRep;
213    }
214    else
215    {
216        return h1 * h2;
217    }
218}
219
220RE* RE_Simplifier::mkRep(RE* re, int lb2, int ub2)
221{
222    if (Rep* rep = dynamic_cast<Rep*>(re))
223    {
224        if (((rep->getUB() == unboundedRep) && (lb2 > 0)) ||
225                ((rep->getUB() == unboundedRep) && (rep->getLB() <= 1)))
226        {
227            return new Rep(rep->getRE(), rep->getLB() * lb2, unboundedRep);
228        }
229        else if ((rep->getUB() == unboundedRep) && (lb2 == 0))
230        {
231            return new Rep(rep, 0, 1);
232        }
233        else if ((rep->getUB() * lb2) >= (rep->getLB() * (lb2 + 1) - 1))
234        {
235            return new Rep(rep->getRE(), rep->getLB() * lb2, ubCombine(rep->getUB(), ub2));
236        }
237        else
238        {
239            return new Rep(rep, lb2, ub2);
240        }
241    }
242    else
243    {
244        if (Seq* seq = dynamic_cast<Seq*>(re))
245        {
246            if(seq->GetREList()->size() == 0)
247            {
248                return seq;
249            }
250        }
251
252        if ((lb2 == 0) && (ub2 == 0))
253        {
254            return new Seq();
255        }
256        else if ((lb2 == 1) && (ub2 == 1))
257        {
258            return re;
259        }
260        else
261        {
262            return new Rep(re, lb2, ub2);
263        }
264    }
265}
Note: See TracBrowser for help on using the repository browser.