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

Last change on this file since 6208 was 6208, checked in by cameron, 10 months ago

Unneeded capture removal

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