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

Last change on this file since 6223 was 6223, checked in by cameron, 5 months ago

Contextual assertion simplifier from Jeremy Schwartz - initial check-in

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