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
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    r = simplifyAssertions(r);
103    //r = lookaheadPromotion(r);
104    return r;
105}
106
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    }
112    return r;
113}
114
115RE * regular_expression_passes(RE * re) {
116
117    //Optimization passes to simplify the AST.
118    RE * r = removeNullablePrefix(re);
119    r = removeNullableSuffix(r);
120    r = RE_Star_Normal().transformRE(r);
121    if (codegen::OptLevel > 1) {
122        r = minimizeRE(r);
123    } else {
124        r = simplifyRE(r);
125    }
126    r = resolveDiffs(r);
127    r = resolveAnchors(r, makeAlt());
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    }
131    return r;
132}
133
134static bool compare(const RE * const lh, const RE * const rh);
135
136static bool lessThan(const Seq * const lh, const Seq * const rh) {
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
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}
165
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:
260            return lessThan(cast<Alt>(lh), cast<Alt>(rh));
261        case Type::Seq:
262            return lessThan(cast<Seq>(lh), cast<Seq>(rh));
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
291RE * RE_Transformer::transformRE(RE * re) {
292    RE * initialRE = re;
293    RE * finalRE = transform(re);
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)  {
299        errs() << mTransformationName << ":\n" << Printer_RE::PrintRE(finalRE) << '\n';
300    }
301    return finalRE;
302}
303
304RE * RE_Transformer::transform(RE * const from) { assert (from);
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;
338}
339
340RE * RE_Transformer::transformName(Name * nm) {
341    if (mNameTransform == NameTransformationMode::None) {
342        return nm;
343    }
344    RE * const defn = nm->getDefinition();
345    if (LLVM_UNLIKELY(defn == nullptr)) {
346        UndefinedNameError(nm);
347    }
348    RE * t = transform(defn);
349    if (t == defn) return nm;
350    return t;
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
457inline bool RE_Inspector::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
458    return compare(lh, rh);
459}
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.