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

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

ShowREs: transformations whose name begins '.' are hidden, e.g., .ToUTF8; can show with -ShowAllREs

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