source: icGREP/icgrep-devel/icgrep/re/re_compiler.cpp @ 4210

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

First stage of code generator revamp

File size: 9.8 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "re_compiler.h"
8//Regular Expressions
9#include <re/re_name.h>
10#include <re/re_start.h>
11#include <re/re_end.h>
12#include <re/re_alt.h>
13#include <re/re_cc.h>
14#include <re/re_seq.h>
15#include <re/re_rep.h>
16
17
18//Pablo Expressions
19#include <pablo/codegenstate.h>
20#include <pablo/pe_advance.h>
21#include <pablo/pe_all.h>
22#include <pablo/pe_and.h>
23#include <pablo/pe_call.h>
24#include <pablo/pe_charclass.h>
25#include <pablo/pe_matchstar.h>
26#include <pablo/pe_not.h>
27#include <pablo/pe_or.h>
28#include <pablo/pe_pabloe.h>
29#include <pablo/pe_scanthru.h>
30#include <pablo/pe_sel.h>
31#include <pablo/pe_var.h>
32#include <pablo/pe_xor.h>
33#include <pablo/ps_assign.h>
34#include <pablo/ps_if.h>
35#include <pablo/ps_while.h>
36
37#include <assert.h>
38#include <stdexcept>
39
40using namespace pablo;
41
42namespace re {
43
44RE_Compiler::RE_Compiler(CodeGenState & baseCG, std::map<std::string, std::string> name_map)
45: mBaseCG(baseCG)
46, m_name_map(name_map)
47{
48
49}
50
51void RE_Compiler::compile(RE * re) {
52
53    std::string gs_m0 = mBaseCG.symgen("start_marker");
54    mBaseCG.push_back(makeAssign(gs_m0, makeAll(1)));
55
56    if (hasUnicode(re)) {
57        mBaseCG.newsym = gs_m0;
58        //Set the 'internal.initial' bit stream for the utf-8 multi-byte encoding.
59        std::string gs_initial = mBaseCG.symgen("internal.initial");
60        m_name_map.insert(make_pair("internal.initial", gs_initial));
61        PabloE * u8single = makeVar(m_name_map.find("UTF8-SingleByte")->second);
62        PabloE * u8pfx2 = makeVar(m_name_map.find("UTF8-Prefix2")->second);
63        PabloE * u8pfx3 = makeVar(m_name_map.find("UTF8-Prefix3")->second);
64        PabloE * u8pfx4 = makeVar(m_name_map.find("UTF8-Prefix4")->second);
65        PabloE * u8pfx = makeOr(makeOr(u8pfx2, u8pfx3), u8pfx4);
66        mBaseCG.push_back(makeAssign(gs_initial, makeOr(u8pfx, u8single)));
67        mBaseCG.newsym = gs_initial;
68
69        //Set the 'internal.nonfinal' bit stream for the utf-8 multi-byte encoding.
70        mBaseCG.newsym = gs_m0;
71        std::string gs_nonfinal = mBaseCG.symgen("internal.nonfinal");
72        m_name_map.insert(make_pair("internal.nonfinal", gs_nonfinal));
73        //#define USE_IF_FOR_NONFINAL
74        #ifdef USE_IF_FOR_NONFINAL
75        cg.push_back(make_assign(gs_nonfinal, make_all(0)));
76        #endif
77        PabloE * u8scope32 = makeAdvance(u8pfx3);
78        PabloE * u8scope42 = makeAdvance(u8pfx4);
79        PabloE * u8scope43 = makeAdvance(u8scope42);
80        PabloE * assign_non_final = makeAssign(gs_nonfinal, makeOr(makeOr(u8pfx, u8scope32), makeOr(u8scope42, u8scope43)));
81        #ifdef USE_IF_FOR_NONFINAL
82        std::list<PabloE *> * if_body = new std::list<PabloE *> ();
83        if_body->push_back(assign_non_final);
84        cg.push_back(new If(u8pfx, *if_body));
85        #else
86        mBaseCG.push_back(assign_non_final);
87        #endif
88        mBaseCG.newsym = gs_nonfinal;
89    }
90
91    mBaseCG.newsym = gs_m0;
92    process(re, mBaseCG);
93
94    //These three lines are specifically for grep.
95    std::string gs_retVal = mBaseCG.symgen("marker");
96    mBaseCG.push_back(makeAssign(gs_retVal, makeAnd(makeMatchStar(makeVar(mBaseCG.newsym),
97        makeNot(makeVar(m_name_map.find("LineFeed")->second))), makeVar(m_name_map.find("LineFeed")->second))));
98    mBaseCG.newsym = gs_retVal;
99}
100
101void RE_Compiler::process(RE * re, CodeGenState & cg) {
102    if (Name * name = dyn_cast<Name>(re)) {
103        process(name, cg);
104    }
105    else if (Seq* seq = dyn_cast<Seq>(re)) {
106        process(seq, cg);
107    }
108    else if (Alt * alt = dyn_cast<Alt>(re)) {
109        process(alt, cg);
110    }
111    else if (Rep * rep = dyn_cast<Rep>(re)) {
112        process(rep, cg);
113    }
114    else if (isa<Start>(re)) {
115        std::string gs_retVal = cg.symgen("sol");
116        cg.push_back(makeAssign(gs_retVal, makeAnd(makeVar(cg.newsym), makeNot(makeAdvance(makeNot(makeCharClass(m_name_map.find("LineFeed")->second)))))));
117        cg.newsym = gs_retVal;
118    }
119    else if (isa<End>(re)) {
120        std::string gs_retVal = cg.symgen("eol");
121        cg.push_back(makeAssign(gs_retVal, makeAnd(makeVar(cg.newsym), makeCharClass(m_name_map.find("LineFeed")->second))));
122        cg.newsym = gs_retVal;
123    }
124}
125
126inline void RE_Compiler::process(Name * name, CodeGenState & cg) {
127    std::string gs_retVal = cg.symgen("marker");
128    PabloE * markerExpr = makeVar(cg.newsym);
129    if (name->getType() != Name::Type::FixedLength) {
130        // Move the markers forward through any nonfinal UTF-8 bytes to the final position of each character.
131        markerExpr = makeAnd(markerExpr, makeCharClass(m_name_map.find("internal.initial")->second));
132        markerExpr = new ScanThru(markerExpr, makeCharClass(m_name_map.find("internal.nonfinal")->second));
133    }
134    PabloE * ccExpr;
135    if (name->getType() == Name::Type::UnicodeCategory) {
136        ccExpr = makeCall(name->getName());
137    }
138    else {
139        ccExpr = makeCharClass(name->getName());
140    }
141    if (name->isNegated()) {
142        ccExpr = makeNot(makeOr(makeOr(ccExpr, makeCharClass(m_name_map.find("LineFeed")->second)),
143                                makeCharClass(m_name_map.find("internal.nonfinal")->second)));
144    }
145    cg.push_back(makeAssign(gs_retVal, makeAdvance(makeAnd(ccExpr, markerExpr))));
146    cg.newsym = gs_retVal;
147}
148
149inline void RE_Compiler::process(Seq * seq, CodeGenState & cg) {
150    for (RE * re : *seq) {
151        process(re, cg);
152    }
153}
154
155inline void RE_Compiler::process(Alt * alt, CodeGenState & cg) {
156    if (alt->empty()) {
157        std::string gs_retVal = cg.symgen("always_fail_marker");
158        cg.push_back(makeAssign(gs_retVal, makeAll(0)));
159        cg.newsym = gs_retVal;
160    }
161    else {
162        auto i = alt->begin();
163        const std::string startsym = cg.newsym;
164        process(*i, cg);
165        while (++i != alt->end()) {
166            std::string alt1 = cg.newsym;
167            cg.newsym = startsym;
168            process(*i, cg);
169            std::string newsym = cg.symgen("alt");
170            cg.push_back(makeAssign(newsym, makeOr(makeVar(alt1), makeVar(cg.newsym))));
171            cg.newsym = newsym;
172        }
173    }
174}
175
176inline void RE_Compiler::process(Rep * rep, CodeGenState & cg) {
177    if (rep->getUB() == Rep::UNBOUNDED_REP) {
178        processUnboundedRep(rep->getRE(), rep->getLB(), cg);
179    }
180    else { // if (rep->getUB() != Rep::UNBOUNDED_REP)
181        processBoundedRep(rep->getRE(), rep->getLB(), rep->getUB(), cg);
182    }
183}
184
185inline void RE_Compiler::processUnboundedRep(RE * repeated, int lb, CodeGenState & cg) {
186    while (lb-- != 0) {
187        process(repeated, cg);
188    }
189    if (isa<Name>(repeated)) {
190        Name * rep_name = dyn_cast<Name>(repeated);
191        std::string gs_retVal = cg.symgen("marker");
192
193        PabloE* ccExpr;
194        if (rep_name->getType() == Name::Type::UnicodeCategory) {
195            ccExpr = makeCall(rep_name->getName());
196        }
197        else {
198            ccExpr = makeCharClass(rep_name->getName());
199        }
200
201        if (rep_name->isNegated()) {
202            ccExpr = makeNot(makeOr(makeOr(ccExpr, makeCharClass(m_name_map.find("LineFeed")->second)), makeCharClass(m_name_map.find("internal.nonfinal")->second)));
203        }
204        if (rep_name->getType() == Name::Type::FixedLength) {
205            cg.push_back(makeAssign(gs_retVal, makeMatchStar(makeVar(cg.newsym), ccExpr)));
206        }
207        else { // Name::Unicode and Name::UnicodeCategory
208            cg.push_back(makeAssign(gs_retVal,
209                makeAnd(makeMatchStar(makeVar(cg.newsym),
210                        makeOr(makeCharClass(m_name_map.find("internal.nonfinal")->second), ccExpr)),
211                               makeCharClass(m_name_map.find("internal.initial")->second))));
212        }
213        cg.newsym = gs_retVal;
214    }
215    else {
216      std::string while_test = cg.symgen("while_test");
217      std::string while_accum = cg.symgen("while_accum");
218
219      CodeGenState wt(cg);
220
221      wt.newsym = while_test;
222      process(repeated, wt);
223
224      cg.push_back(makeAssign(while_test, makeVar(cg.newsym)));
225      cg.push_back(makeAssign(while_accum, makeVar(cg.newsym)));
226
227      wt.push_back(makeAssign(while_test, makeAnd(makeVar(wt.newsym), makeNot(makeVar(while_accum)))));
228      wt.push_back(makeAssign(while_accum, makeOr(makeVar(while_accum), makeVar(wt.newsym))));
229
230      cg.push_back(makeWhile(makeVar(while_test), wt.expressions()));
231      cg.newsym = while_accum;
232    }
233}
234
235inline void RE_Compiler::processBoundedRep(RE * repeated, int lb, int ub, CodeGenState & cg) {
236    ub -= lb;
237    while(lb-- != 0) {
238        process(repeated, cg);
239    }
240    if (ub > 0) {
241         std::string oldsym = cg.newsym;
242         process(repeated, cg);
243         processBoundedRep(repeated, 0, ub - 1, cg);
244         std::string altsym = cg.symgen("alt");
245         cg.push_back(makeAssign(altsym, makeOr(makeVar(oldsym), makeVar(cg.newsym))));
246         cg.newsym = altsym;
247    }
248}
249
250
251bool RE_Compiler::hasUnicode(const RE * re) {
252    bool found = false;
253    if (re == nullptr) {
254        throw std::runtime_error("Unexpected Null Value passed to RE Compiler!");
255    }
256    else if (const Name * name = dyn_cast<const Name>(re)) {
257        if ((name->getType() == Name::Type::UnicodeCategory) || (name->getType() == Name::Type::Unicode)) {
258            found = true;
259        }
260    }
261    else if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
262        for (auto i = re_seq->cbegin(); i != re_seq->cend(); ++i) {
263            if (hasUnicode(*i)) {
264                found = true;
265                break;
266            }
267        }
268    }
269    else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
270        for (auto i = re_alt->cbegin(); i != re_alt->cend(); ++i) {
271            if (hasUnicode(*i)) {
272                found = true;
273                break;
274            }
275        }
276    }
277    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
278        found = hasUnicode(rep->getRE());
279    }
280    return found;
281}
282
283} // end of namespace re
Note: See TracBrowser for help on using the repository browser.