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

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

Minor changes; moved printers to re and pablo folders.

File size: 11.7 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(std::map<std::string, std::string> name_map)
45: m_name_map(name_map)
46, symgen()
47{
48
49}
50
51CodeGenState RE_Compiler::compile_subexpressions(const std::map<std::string, RE*>& re_map)
52{
53    CodeGenState cg_state;
54    for (auto i =  re_map.rbegin(); i != re_map.rend(); ++i) {
55        //This is specifically for the utf8 multibyte character classes.
56        if (Seq * seq = dyn_cast<Seq>(i->second)) {
57            if (seq->getType() == Seq::Type::Byte) {
58                std::string gs_retVal = symgen.get("start_marker");
59                cg_state.stmtsl.push_back(make_assign(gs_retVal, make_all(1)));
60                for (auto j = seq->begin();; ) {
61                    Name * name = dyn_cast<Name>(*j);
62                    assert (name);
63                    auto * cc_mask = make_and(make_var(gs_retVal), make_charclass(name->getName()));
64                    if (++j != seq->end()) {
65                        gs_retVal = symgen.get("marker");
66                        cg_state.stmtsl.push_back(make_assign(gs_retVal, make_advance(cc_mask)));
67                    }
68                    else {
69                        cg_state.stmtsl.push_back(make_assign(seq->getName(), cc_mask));
70                        break;
71                    }
72                }
73                cg_state.newsym = gs_retVal;
74            }
75        }
76    }
77    return cg_state;
78}
79
80CodeGenState RE_Compiler::compile(RE * re)
81{
82    CodeGenState cg_state;
83
84    std::string gs_m0 = symgen.get("start_marker");
85    cg_state.stmtsl.push_back(make_assign(gs_m0, make_all(1)));
86
87    if (hasUnicode(re)) {
88        cg_state.newsym = gs_m0;
89        //Set the 'internal.initial' bit stream for the utf-8 multi-byte encoding.
90        std::string gs_initial = symgen.get("internal.initial");
91        m_name_map.insert(make_pair("internal.initial", gs_initial));
92        PabloE * u8single = make_var(m_name_map.find("UTF8-SingleByte")->second);
93        PabloE * u8pfx2 = make_var(m_name_map.find("UTF8-Prefix2")->second);
94        PabloE * u8pfx3 = make_var(m_name_map.find("UTF8-Prefix3")->second);
95        PabloE * u8pfx4 = make_var(m_name_map.find("UTF8-Prefix4")->second);
96        PabloE * u8pfx = make_or(make_or(u8pfx2, u8pfx3), u8pfx4);
97        cg_state.stmtsl.push_back(make_assign(gs_initial, make_or(u8pfx, u8single)));
98        cg_state.newsym = gs_initial;
99
100        //Set the 'internal.nonfinal' bit stream for the utf-8 multi-byte encoding.
101        cg_state.newsym = gs_m0;
102        std::string gs_nonfinal = symgen.get("internal.nonfinal");
103        m_name_map.insert(make_pair("internal.nonfinal", gs_nonfinal));
104        //#define USE_IF_FOR_NONFINAL
105        #ifdef USE_IF_FOR_NONFINAL
106        cg_state.stmtsl.push_back(make_assign(gs_nonfinal, make_all(0)));
107        #endif
108        PabloE * u8scope32 = make_advance(u8pfx3);
109        PabloE * u8scope42 = make_advance(u8pfx4);
110        PabloE * u8scope43 = make_advance(u8scope42);
111        PabloE * assign_non_final = make_assign(gs_nonfinal, make_or(make_or(u8pfx, u8scope32), make_or(u8scope42, u8scope43)));
112        #ifdef USE_IF_FOR_NONFINAL
113        std::list<PabloE *> * if_body = new std::list<PabloE *> ();
114        if_body->push_back(assign_non_final);
115        cg_state.stmtsl.push_back(new If(u8pfx, *if_body));
116        #else
117        cg_state.stmtsl.push_back(assign_non_final);
118        #endif
119        cg_state.newsym = gs_nonfinal;
120    }
121
122    cg_state.newsym = gs_m0;
123    compile(re, cg_state);
124
125    //These three lines are specifically for grep.
126    std::string gs_retVal = symgen.get("marker");
127    cg_state.stmtsl.push_back(make_assign(gs_retVal, make_and(new MatchStar(make_var(cg_state.newsym),
128        make_not(make_var(m_name_map.find("LineFeed")->second))), make_var(m_name_map.find("LineFeed")->second))));
129    cg_state.newsym = gs_retVal;
130
131    return cg_state;
132}
133
134void RE_Compiler::compile(RE * re, CodeGenState & cg_state) {
135    if (Name * name = dyn_cast<Name>(re)) {
136        compile(name, cg_state);
137    }
138    else if (Seq* seq = dyn_cast<Seq>(re)) {
139        compile(seq, cg_state);
140    }
141    else if (Alt * alt = dyn_cast<Alt>(re)) {
142        compile(alt, cg_state);
143    }
144    else if (Rep * rep = dyn_cast<Rep>(re)) {
145        compile(rep, cg_state);
146    }
147    else if (isa<Start>(re)) {
148        std::string gs_retVal = symgen.get("sol");
149        cg_state.stmtsl.push_back(make_assign(gs_retVal, make_and(make_var(cg_state.newsym), make_not(make_advance(make_not(make_charclass(m_name_map.find("LineFeed")->second)))))));
150        cg_state.newsym = gs_retVal;
151    }
152    else if (isa<End>(re)) {
153        std::string gs_retVal = symgen.get("eol");
154        cg_state.stmtsl.push_back(make_assign(gs_retVal, make_and(make_var(cg_state.newsym), make_charclass(m_name_map.find("LineFeed")->second))));
155        cg_state.newsym = gs_retVal;
156    }
157}
158
159inline void RE_Compiler::compile(Name * name, CodeGenState & cg_state) {
160    std::string gs_retVal = symgen.get("marker");
161    PabloE * markerExpr = make_var(cg_state.newsym);
162    if (name->getType() != Name::Type::FixedLength) {
163        // Move the markers forward through any nonfinal UTF-8 bytes to the final position of each character.
164        markerExpr = make_and(markerExpr, make_charclass(m_name_map.find("internal.initial")->second));
165        markerExpr = new ScanThru(markerExpr, make_charclass(m_name_map.find("internal.nonfinal")->second));
166    }
167    PabloE * ccExpr;
168    if (name->getType() == Name::Type::UnicodeCategory) {
169        ccExpr = make_call(name->getName());
170    }
171    else {
172        ccExpr = make_charclass(name->getName());
173    }
174    if (name->isNegated()) {
175        ccExpr = make_not(make_or(make_or(ccExpr, make_charclass(m_name_map.find("LineFeed")->second)),
176                                make_charclass(m_name_map.find("internal.nonfinal")->second)));
177    }
178    cg_state.stmtsl.push_back(make_assign(gs_retVal, make_advance(make_and(ccExpr, markerExpr))));
179    cg_state.newsym = gs_retVal;
180}
181
182inline void RE_Compiler::compile(Seq * seq, CodeGenState & cg_state) {
183    for (RE * re : *seq) {
184        compile(re, cg_state);
185    }
186}
187
188inline void RE_Compiler::compile(Alt * alt, CodeGenState & cg_state) {
189    if (alt->empty()) {
190        std::string gs_retVal = symgen.get("always_fail_marker");
191        cg_state.stmtsl.push_back(make_assign(gs_retVal, make_all(0)));
192        cg_state.newsym = gs_retVal;
193    }
194    else {
195        auto i = alt->begin();
196        const std::string startsym = cg_state.newsym;
197        compile(*i, cg_state);
198        while (++i != alt->end()) {
199            std::string alt1 = cg_state.newsym;
200            cg_state.newsym = startsym;
201            compile(*i, cg_state);
202            std::string newsym = symgen.get("alt");
203            cg_state.stmtsl.push_back(make_assign(newsym, make_or(make_var(alt1), make_var(cg_state.newsym))));
204            cg_state.newsym = newsym;
205        }
206    }
207}
208
209inline void RE_Compiler::compile(Rep * rep, CodeGenState & cg_state) {
210    if (isa<Name>(rep->getRE()) && (rep->getLB() == 0) && (rep->getUB()== Rep::UNBOUNDED_REP)) {
211        Name * rep_name = dyn_cast<Name>(rep->getRE());
212        std::string gs_retVal = symgen.get("marker");
213
214        PabloE* ccExpr;
215        if (rep_name->getType() == Name::Type::UnicodeCategory) {
216            ccExpr = make_call(rep_name->getName());
217        }
218        else {
219            ccExpr = make_charclass(rep_name->getName());
220        }
221
222        if (rep_name->isNegated()) {
223            ccExpr = make_not(make_or(make_or(ccExpr, make_charclass(m_name_map.find("LineFeed")->second)), make_charclass(m_name_map.find("internal.nonfinal")->second)));
224        }
225        if (rep_name->getType() == Name::Type::FixedLength) {
226            cg_state.stmtsl.push_back(make_assign(gs_retVal, new MatchStar(make_var(cg_state.newsym), ccExpr)));
227        }
228        else { // Name::Unicode and Name::UnicodeCategory
229            cg_state.stmtsl.push_back(make_assign(gs_retVal,
230                make_and(new MatchStar(make_var(cg_state.newsym),
231                        make_or(make_charclass(m_name_map.find("internal.nonfinal")->second), ccExpr)),
232                               make_charclass(m_name_map.find("internal.initial")->second))));
233        }
234        cg_state.newsym = gs_retVal;
235    }
236    else if (rep->getUB() == Rep::UNBOUNDED_REP) {
237        compileUnboundedRep(rep->getRE(), rep->getLB(), cg_state);
238    }
239    else { // if (rep->getUB() != Rep::UNBOUNDED_REP)
240        compileBoundedRep(rep->getRE(), rep->getLB(), rep->getUB(), cg_state);
241    }
242}
243
244inline void RE_Compiler::compileUnboundedRep(RE * repeated, int lb, CodeGenState & cg_state) {
245    for (; lb; --lb) {
246        compile(repeated, cg_state);
247    }
248    std::string while_test = symgen.get("while_test");
249    std::string while_accum = symgen.get("while_accum");
250    CodeGenState while_test_state;
251    while_test_state.newsym = while_test;
252    compile(repeated, while_test_state);
253    cg_state.stmtsl.push_back(make_assign(while_test, make_var(cg_state.newsym)));
254    cg_state.stmtsl.push_back(make_assign(while_accum, make_var(cg_state.newsym)));
255    while_test_state.stmtsl.push_back(make_assign(while_test, make_and(make_var(while_test_state.newsym), make_not(make_var(while_accum)))));
256    while_test_state.stmtsl.push_back(make_assign(while_accum, make_or(make_var(while_accum), make_var(while_test_state.newsym))));
257    cg_state.stmtsl.push_back(new While(make_var(while_test), while_test_state.stmtsl));
258    cg_state.newsym = while_accum;
259}
260
261inline void RE_Compiler::compileBoundedRep(RE * repeated, int lb, int ub, CodeGenState & cg_state) {
262    ub -= lb;
263    for (; lb; --lb) {
264        compile(repeated, cg_state);
265    }
266    if (ub > 0) {
267         std::string oldsym = cg_state.newsym;
268         compile(repeated, cg_state);
269         compileBoundedRep(repeated, 0, ub - 1, cg_state);
270         std::string altsym = symgen.get("alt");
271         cg_state.stmtsl.push_back(make_assign(altsym, make_or(make_var(oldsym), make_var(cg_state.newsym))));
272         cg_state.newsym = altsym;
273    }
274}
275
276
277bool RE_Compiler::hasUnicode(const RE * re) {
278    bool found = false;
279    if (re == nullptr) {
280        throw std::runtime_error("Unexpected Null Value passed to RE Compiler!");
281    }
282    else if (const Name * name = dyn_cast<const Name>(re)) {
283        if ((name->getType() == Name::Type::UnicodeCategory) || (name->getType() == Name::Type::Unicode)) {
284            found = true;
285        }
286    }
287    else if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
288        for (auto i = re_seq->cbegin(); i != re_seq->cend(); ++i) {
289            if (hasUnicode(*i)) {
290                found = true;
291                break;
292            }
293        }
294    }
295    else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
296        for (auto i = re_alt->cbegin(); i != re_alt->cend(); ++i) {
297            if (hasUnicode(*i)) {
298                found = true;
299                break;
300            }
301        }
302    }
303    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
304        found = hasUnicode(rep->getRE());
305    }
306    return found;
307}
308
309} // end of namespace re
Note: See TracBrowser for help on using the repository browser.