source: icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp @ 6173

Last change on this file since 6173 was 6173, checked in by nmedfort, 7 months ago

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

File size: 15.1 KB
Line 
1/*
2 *  Copyright (c) 2017 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 <toolchain/toolchain.h>
8#include <grep_interface.h>
9#include <re/re_toolchain.h>
10#include <re/re_any.h>
11#include <re/re_name.h>
12#include <re/re_cc.h>
13#include <re/re_start.h>
14#include <re/re_end.h>
15#include <re/re_alt.h>
16#include <re/re_seq.h>
17#include <re/re_diff.h>
18#include <re/re_intersect.h>
19#include <re/re_group.h>
20#include <re/re_range.h>
21#include <re/re_assertion.h>
22#include <cc/cc_compiler.h>            // for CC_Compiler
23#include <llvm/Support/CommandLine.h>  // for clEnumVal, clEnumValEnd, Optio...
24#include <re/re_compiler.h>            // for RE_Compiler
25#include <re/re_nullable.h>            // for RE_Nullable
26#include <re/re_star_normal.h>         // for RE_Star_Normal
27#include <re/re_simplifier.h>          // for RE_Simplifier
28#include <re/re_minimizer.h>
29#include <re/re_local.h>
30#include <re/printer_re.h>
31#include <re/re_analysis.h>
32#include <re/re_cc.h>
33#include <re/casing.h>
34#include <re/exclude_CC.h>
35#include <re/re_name_resolve.h>
36#include <re/grapheme_clusters.h>
37#include <llvm/Support/raw_ostream.h>
38#include <llvm/Support/ErrorHandling.h>
39#include <toolchain/toolchain.h>
40
41using namespace pablo;
42using namespace llvm;
43
44namespace re {
45
46static cl::OptionCategory RegexOptions("Regex Toolchain Options",
47                                              "These options control the regular expression transformation and compilation.");
48const cl::OptionCategory * LLVM_READONLY re_toolchain_flags() {
49    return &RegexOptions;
50}
51
52static cl::bits<RE_PrintFlags> 
53    PrintOptions(cl::values(clEnumVal(ShowREs, "Print parsed or generated regular expressions"),
54                            clEnumVal(ShowAllREs, "Print all regular expression passes"),
55                            clEnumVal(ShowStrippedREs, "Print REs with nullable prefixes/suffixes removed"),
56                            clEnumVal(ShowSimplifiedREs, "Print final simplified REs")
57                            CL_ENUM_VAL_SENTINEL), cl::cat(RegexOptions));
58
59static cl::bits<RE_AlgorithmFlags>
60    AlgorithmOptions(cl::values(clEnumVal(DisableLog2BoundedRepetition, "disable log2 optimizations for bounded repetition of bytes"),
61                              clEnumVal(DisableIfHierarchy, "disable nested if hierarchy for generated Unicode classes (not recommended)"), 
62                              clEnumVal(DisableMatchStar, "disable MatchStar optimization"), 
63                              clEnumVal(DisableUnicodeMatchStar, "disable Unicode MatchStar optimization"),
64                              clEnumVal(DisableUnicodeLineBreak, "disable Unicode line breaks - use LF only")
65                              CL_ENUM_VAL_SENTINEL), cl::cat(RegexOptions));
66
67bool LLVM_READONLY AlgorithmOptionIsSet(RE_AlgorithmFlags flag) {
68    return AlgorithmOptions.isSet(flag);
69}
70
71int IfInsertionGap;
72static cl::opt<int, true> 
73    IfInsertionGapOption("if-insertion-gap",  cl::location(IfInsertionGap), cl::init(3),
74                         cl::desc("minimum number of nonempty elements between inserted if short-circuit tests"), 
75                         cl::cat(RegexOptions));
76
77RE * resolveModesAndExternalSymbols(RE * r, bool globallyCaseInsensitive) {
78    if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowREs)) {
79        errs() << "Parser:\n" << Printer_RE::PrintRE(r) << '\n';
80    }
81    r = resolveGraphemeMode(r, false /* not in grapheme mode at top level*/);
82    if (PrintOptions.isSet(ShowAllREs)) {
83        errs() << "resolveGraphemeMode:\n" << Printer_RE::PrintRE(r) << '\n';
84    }
85    r = re::resolveUnicodeNames(r);
86    r = resolveCaseInsensitiveMode(r, globallyCaseInsensitive);
87    return r;
88}
89
90RE * excludeUnicodeLineBreak(RE * r) {
91    r = exclude_CC(r, re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029))));
92    if (PrintOptions.isSet(ShowAllREs)) {
93        errs() << "excludeUnicodeLineBreak:\n" << Printer_RE::PrintRE(r) << '\n';
94    }
95    return r;
96}
97
98RE * regular_expression_passes(RE * r) {
99
100    //Optimization passes to simplify the AST.
101    r = removeNullablePrefix(r);
102    r = removeNullableSuffix(r);
103    r = RE_Star_Normal().transformRE(r);
104    if (codegen::OptLevel > 1) {
105        r = RE_Minimizer::minimize(r);
106    } else {
107        r = RE_Simplifier::simplify(r);
108    }
109    if (!DefiniteLengthBackReferencesOnly(r)) {
110        llvm::report_fatal_error("Future back reference support: references must be within a fixed distance from a fixed-length capture.");
111    }
112    return r;
113}
114
115static bool compare(const RE * const lh, const RE * const rh);
116
117static bool lessThan(const Vector * const lh, const Vector * const rh) {
118    assert (lh->getClassTypeId() == rh->getClassTypeId());
119    assert (lh->getClassTypeId() == RE::ClassTypeId::Alt || lh->getClassTypeId() == RE::ClassTypeId::Seq);
120    if (LLVM_LIKELY(lh->size() != rh->size())) {
121        return lh->size() < rh->size();
122    }
123    for (auto i = lh->begin(), j = rh->begin(); i != lh->end(); ++i, ++j) {
124        assert (*i && *j);
125        if (compare(*i, *j)) {
126            return true;
127        } else if (compare(*j, *i)) {
128            return false;
129        }
130    }
131    return false;
132}
133
134inline bool lessThan(const Name * const lh, const Name * const rh) {
135    if (lh->getType() != rh->getType()) {
136        return lh->getType() < rh->getType();
137    } else if (lh->hasNamespace() != rh->hasNamespace()) {
138        return lh->hasNamespace();
139    } else if (lh->hasNamespace() && (lh->getNamespace() != rh->getNamespace())) {
140        return lh->getNamespace() < rh->getNamespace();
141    } else if (lh->getName() != rh->getName()) {
142        return lh->getName() < rh->getName();
143    } else if (lh->getDefinition() == nullptr) {
144        return rh->getDefinition() != nullptr;
145    } else if (rh->getDefinition() == nullptr) {
146        return false;
147    } else {
148        return compare(lh->getDefinition(), rh->getDefinition());
149    }
150}
151
152inline bool lessThan(const Assertion * const lh, const Assertion * const rh) {
153    if (lh->getKind() != rh->getKind()) {
154        return lh->getKind() < rh->getKind();
155    }
156    if (lh->getSense() != rh->getSense()) {
157        return lh->getSense() < rh->getSense();
158    }
159    return compare(lh->getAsserted(), rh->getAsserted());
160}
161
162inline bool lessThan(const Rep * const lh, const Rep * const rh) {
163    if (lh->getLB() != rh->getLB()) {
164        return lh->getLB() < rh->getLB();
165    }
166    if (lh->getUB() != rh->getUB()) {
167        return lh->getUB() < rh->getUB();
168    }
169    return compare(lh->getRE(), rh->getRE());
170}
171
172inline bool lessThan(const Diff * const lh, const Diff * const rh) {
173    if (compare(lh->getLH(), rh->getLH())) {
174        return true;
175    } else if (compare(rh->getLH(), lh->getLH())) {
176        return false;
177    } else if (compare(lh->getRH(), rh->getRH())) {
178        return true;
179    } else {
180        return !compare(rh->getRH(), lh->getRH());
181    }
182}
183
184inline bool lessThan(const Range * const lh, const Range * const rh) {
185    if (compare(lh->getLo(), rh->getLo())) {
186        return true;
187    } else if (compare(rh->getLo(), lh->getLo())) {
188        return false;
189    } else if (compare(lh->getHi(), rh->getHi())) {
190        return true;
191    } else {
192        return !compare(rh->getHi(), lh->getHi());
193    }
194}
195
196static bool lessThan(const Intersect * const lh, const Intersect * const rh) {
197    if (compare(lh->getLH(), rh->getLH())) {
198        return true;
199    } else if (compare(rh->getLH(), lh->getLH())) {
200        return false;
201    } else if (compare(lh->getRH(), rh->getRH())) {
202        return true;
203    } else {
204        return !compare(rh->getRH(), lh->getRH());
205    }
206}
207
208inline bool lessThan(const Group * const lh, const Group * const rh) {
209    if (lh->getMode() != rh->getMode()) {
210        return lh->getMode() < rh->getMode();
211    }
212    if (lh->getSense() != rh->getSense()) {
213        return lh->getSense() < rh->getSense();
214    }
215    return compare(lh->getRE(), rh->getRE());
216}
217
218inline bool compare(const RE * const lh, const RE * const rh) {
219    using Type = RE::ClassTypeId;
220    assert (lh && rh);
221    const auto typeL = lh->getClassTypeId();
222    const auto typeR = rh->getClassTypeId();
223    if (LLVM_LIKELY(typeL != typeR)) {
224        return typeL < typeR;
225    }
226    switch (typeL) {
227        case Type::Alt:
228        case Type::Seq:
229            return lessThan(cast<Vector>(lh), cast<Vector>(rh));
230        case Type::End: case Type::Start:
231            return false;
232        case Type::Assertion:
233            return lessThan(cast<Assertion>(lh), cast<Assertion>(rh));
234        case Type::CC:
235            return *cast<CC>(lh) < *cast<CC>(rh);
236        case Type::Name:
237            return lessThan(cast<Name>(lh), cast<Name>(rh));
238        case Type::Group:
239            return lessThan(cast<Group>(lh), cast<Group>(rh));
240        case Type::Range:
241            return lessThan(cast<Range>(lh), cast<Range>(rh));
242        case Type::Diff:
243            return lessThan(cast<Diff>(lh), cast<Diff>(rh));
244        case Type::Intersect:
245            return lessThan(cast<Intersect>(lh), cast<Intersect>(rh));
246        case Type::Rep:
247            return lessThan(cast<Rep>(lh), cast<Rep>(rh));
248        default:
249            llvm_unreachable("RE object of unknown type given to Memoizer");
250            return false;
251    }
252}
253
254inline bool RE_Transformer::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
255    return compare(lh, rh);
256}
257
258RE * RE_Transformer::transformRE(RE * re) {
259    RE * initialRE = re;
260    RE * finalRE = transform(re);
261    if (PrintOptions.isSet(ShowAllREs) && (initialRE != finalRE) && (mTransformationName != "")) {
262        errs() << mTransformationName << ":\n" << Printer_RE::PrintRE(finalRE) << '\n';
263    }
264    return finalRE;
265}
266
267RE * RE_Transformer::transform(RE * const from) {
268    assert (from);
269    const auto f = mMap.find(from);
270    if (f != mMap.end()) {
271        return f->second;
272    }
273
274    using T = RE::ClassTypeId;
275    RE * to = from;
276    #define TRANSFORM(Type) \
277        case T::Type: to = transform##Type(llvm::cast<Type>(from)); break
278    switch (from->getClassTypeId()) {
279        TRANSFORM(Alt);
280        TRANSFORM(Assertion);
281        TRANSFORM(CC);
282        TRANSFORM(Range);
283        TRANSFORM(Diff);
284        TRANSFORM(End);
285        TRANSFORM(Intersect);
286        TRANSFORM(Name);
287        TRANSFORM(Group);
288        TRANSFORM(Rep);
289        TRANSFORM(Seq);
290        TRANSFORM(Start);
291        default: llvm_unreachable("Unknown RE type");
292    }
293    #undef TRANSFORM
294    assert (to);
295
296    // Do we already have a memoized version of the transformed RE?
297    if (from != to) {
298        const auto f = mMap.find(to);
299        if (LLVM_LIKELY(f == mMap.end())) {
300            mMap.emplace(to, to);
301        } else {
302            to = f->second;
303        }
304    }
305
306    mMap.emplace(from, to);
307
308    return to;
309}
310
311RE * RE_Transformer::transformName(Name * nm) {
312    if (mNameTransform == NameTransformationMode::None) {
313        return nm;
314    }
315    RE * const d = nm->getDefinition();
316    if (LLVM_UNLIKELY(d == nullptr)) {
317        UndefinedNameError(nm);
318    }
319    return transform(d);
320}
321
322RE * RE_Transformer::transformCC(CC * cc) {
323    return cc;
324}
325
326RE * RE_Transformer::transformStart(Start * s) {
327    return s;
328}
329
330RE * RE_Transformer::transformEnd(End * e) {
331    return e;
332}
333
334RE * RE_Transformer::transformSeq(Seq * seq) {
335    std::vector<RE *> elems;
336    elems.reserve(seq->size());
337    bool any_changed = false;
338    for (RE * e : *seq) {
339        RE * e1 = transform(e);
340        if (e1 != e) any_changed = true;
341        elems.push_back(e1);
342    }
343    if (!any_changed) return seq;
344    return makeSeq(elems.begin(), elems.end());
345}
346
347RE * RE_Transformer::transformAlt(Alt * alt) {
348    std::vector<RE *> elems;
349    elems.reserve(alt->size());
350    bool any_changed = false;
351    for (RE * e : *alt) {
352        RE * e1 = transform(e);
353        if (e1 != e) any_changed = true;
354        elems.push_back(e1);
355    }
356    if (!any_changed) return alt;
357    return makeAlt(elems.begin(), elems.end());
358}
359
360RE * RE_Transformer::transformRep(Rep * r) {
361    RE * x0 = r->getRE();
362    RE * x = transform(x0);
363    if (x == x0) {
364        return r;
365    } else {
366        return makeRep(x, r->getLB(), r->getUB());
367    }
368}
369
370RE * RE_Transformer::transformIntersect(Intersect * ix) {
371    RE * x0 = ix->getLH();
372    RE * y0 = ix->getRH();
373    RE * x = transform(x0);
374    RE * y = transform(y0);
375    if ((x == x0) && (y == y0)) {
376        return ix;
377    } else {
378        return makeIntersect(x, y);
379    }
380}
381
382RE * RE_Transformer::transformDiff(Diff * d) {
383    RE * x0 = d->getLH();
384    RE * y0 = d->getRH();
385    RE * x = transform(x0);
386    RE * y = transform(y0);
387    if ((x == x0) && (y == y0)) {
388        return d;
389    } else {
390        return makeDiff(x, y);
391    }
392}
393
394RE * RE_Transformer::transformRange(Range * rg) {
395    RE * x0 = rg->getLo();
396    RE * y0 = rg->getHi();
397    RE * x = transform(x0);
398    RE * y = transform(y0);
399    if ((x == x0) && (y == y0)) {
400        return rg;
401    } else {
402        return makeRange(x, y);
403    }
404}
405
406RE * RE_Transformer::transformGroup(Group * g) {
407    RE * x0 = g->getRE();
408    RE * x = transform(x0);
409    if (x == x0) {
410        return g;
411    } else {
412        return makeGroup(g->getMode(), x, g->getSense());
413    }
414}
415
416RE * RE_Transformer::transformAssertion(Assertion * a) {
417    RE * x0 = a->getAsserted();
418    RE * x = transform(x0);
419    if (x == x0) {
420        return a;
421    } else {
422        return makeAssertion(x, a->getKind(), a->getSense());
423    }
424}
425
426inline bool RE_Inspector::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
427    return compare(lh, rh);
428}
429
430void RE_Inspector::inspectRE(RE * re) {
431    inspect(re);
432}
433
434void RE_Inspector::inspect(RE * const re) {
435    assert (re);
436    if (mIgnoreNonUnique == InspectionMode::IgnoreNonUnique) {
437        if (mMap.count(re)) return;
438        mMap.emplace(re);
439    }
440    using T = RE::ClassTypeId;
441    #define INSPECT(Type) \
442        case T::Type: inspect##Type(llvm::cast<Type>(re)); break
443    switch (re->getClassTypeId()) {
444        INSPECT(Alt);
445        INSPECT(Assertion);
446        INSPECT(CC);
447        INSPECT(Range);
448        INSPECT(Diff);
449        INSPECT(End);
450        INSPECT(Intersect);
451        INSPECT(Name);
452        INSPECT(Group);
453        INSPECT(Rep);
454        INSPECT(Seq);
455        INSPECT(Start);
456        default: llvm_unreachable("Unknown RE type");
457    }
458    #undef INSPECT
459}
460
461void RE_Inspector::inspectName(Name * nm) {
462    RE * const d = nm->getDefinition();
463    if (d) inspect(d);
464}
465
466void RE_Inspector::inspectCC(CC * cc) {
467
468}
469
470void RE_Inspector::inspectStart(Start * s) {
471
472}
473
474void RE_Inspector::inspectEnd(End * e) {
475
476}
477
478void RE_Inspector::inspectSeq(Seq * seq) {
479    for (RE * e : *seq) {
480        inspect(e);
481    }
482}
483
484void RE_Inspector::inspectAlt(Alt * alt) {
485    for (RE * e : *alt) {
486        inspect(e);
487    }
488}
489
490void RE_Inspector::inspectRep(Rep * r) {
491    inspect(r->getRE());
492}
493
494void RE_Inspector::inspectIntersect(Intersect * ix) {
495    inspect(ix->getLH());
496    inspect(ix->getRH());
497}
498
499void RE_Inspector::inspectDiff(Diff * d) {
500    inspect(d->getLH());
501    inspect(d->getRH());
502}
503
504void RE_Inspector::inspectRange(Range * rg) {
505    inspect(rg->getLo());
506    inspect(rg->getHi());
507}
508
509void RE_Inspector::inspectGroup(Group * g) {
510    inspect(g->getRE());
511}
512
513void RE_Inspector::inspectAssertion(Assertion * a) {
514    inspect(a->getAsserted());
515}
516
517}
Note: See TracBrowser for help on using the repository browser.