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

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

Contextual assertion simplification using more context and additional assertion types

File size: 15.8 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    if ((!mTransformationName.empty()) && (PrintOptions.isSet(ShowAllREs) || (PrintOptions.isSet(ShowREs) && (initialRE != finalRE))))  {
295        errs() << mTransformationName << ":\n" << Printer_RE::PrintRE(finalRE) << '\n';
296    }
297    return finalRE;
298}
299
300RE * RE_Transformer::transform(RE * const from) { assert (from);
301    using T = RE::ClassTypeId;
302    RE * to = from;
303    #define TRANSFORM(Type) \
304        case T::Type: to = transform##Type(llvm::cast<Type>(from)); break
305    switch (from->getClassTypeId()) {
306        TRANSFORM(Alt);
307        TRANSFORM(Assertion);
308        TRANSFORM(CC);
309        TRANSFORM(Range);
310        TRANSFORM(Diff);
311        TRANSFORM(End);
312        TRANSFORM(Intersect);
313        TRANSFORM(Name);
314        TRANSFORM(Group);
315        TRANSFORM(Rep);
316        TRANSFORM(Seq);
317        TRANSFORM(Start);
318        default: llvm_unreachable("Unknown RE type");
319    }
320    #undef TRANSFORM
321    assert (to);
322
323    // Do we already have a memoized version of the transformed RE?
324    if (from != to) {
325        const auto f = mMap.find(to);
326        if (LLVM_LIKELY(f == mMap.end())) {
327            mMap.emplace(to, to);
328        } else {
329            to = f->second;
330        }
331    }
332
333    return to;
334}
335
336RE * RE_Transformer::transformName(Name * nm) {
337    if (mNameTransform == NameTransformationMode::None) {
338        return nm;
339    }
340    RE * const defn = nm->getDefinition();
341    if (LLVM_UNLIKELY(defn == nullptr)) {
342        UndefinedNameError(nm);
343    }
344    RE * t = transform(defn);
345    if (t == defn) return nm;
346    return t;
347}
348
349RE * RE_Transformer::transformCC(CC * cc) {
350    return cc;
351}
352
353RE * RE_Transformer::transformStart(Start * s) {
354    return s;
355}
356
357RE * RE_Transformer::transformEnd(End * e) {
358    return e;
359}
360
361RE * RE_Transformer::transformSeq(Seq * seq) {
362    std::vector<RE *> elems;
363    elems.reserve(seq->size());
364    bool any_changed = false;
365    for (RE * e : *seq) {
366        RE * e1 = transform(e);
367        if (e1 != e) any_changed = true;
368        elems.push_back(e1);
369    }
370    if (!any_changed) return seq;
371    return makeSeq(elems.begin(), elems.end());
372}
373
374RE * RE_Transformer::transformAlt(Alt * alt) {
375    std::vector<RE *> elems;
376    elems.reserve(alt->size());
377    bool any_changed = false;
378    for (RE * e : *alt) {
379        RE * e1 = transform(e);
380        if (e1 != e) any_changed = true;
381        elems.push_back(e1);
382    }
383    if (!any_changed) return alt;
384    return makeAlt(elems.begin(), elems.end());
385}
386
387RE * RE_Transformer::transformRep(Rep * r) {
388    RE * x0 = r->getRE();
389    RE * x = transform(x0);
390    if (x == x0) {
391        return r;
392    } else {
393        return makeRep(x, r->getLB(), r->getUB());
394    }
395}
396
397RE * RE_Transformer::transformIntersect(Intersect * ix) {
398    RE * x0 = ix->getLH();
399    RE * y0 = ix->getRH();
400    RE * x = transform(x0);
401    RE * y = transform(y0);
402    if ((x == x0) && (y == y0)) {
403        return ix;
404    } else {
405        return makeIntersect(x, y);
406    }
407}
408
409RE * RE_Transformer::transformDiff(Diff * d) {
410    RE * x0 = d->getLH();
411    RE * y0 = d->getRH();
412    RE * x = transform(x0);
413    RE * y = transform(y0);
414    if ((x == x0) && (y == y0)) {
415        return d;
416    } else {
417        return makeDiff(x, y);
418    }
419}
420
421RE * RE_Transformer::transformRange(Range * rg) {
422    RE * x0 = rg->getLo();
423    RE * y0 = rg->getHi();
424    RE * x = transform(x0);
425    RE * y = transform(y0);
426    if ((x == x0) && (y == y0)) {
427        return rg;
428    } else {
429        return makeRange(x, y);
430    }
431}
432
433RE * RE_Transformer::transformGroup(Group * g) {
434    RE * x0 = g->getRE();
435    RE * x = transform(x0);
436    if (x == x0) {
437        return g;
438    } else {
439        return makeGroup(g->getMode(), x, g->getSense());
440    }
441}
442
443RE * RE_Transformer::transformAssertion(Assertion * a) {
444    RE * x0 = a->getAsserted();
445    RE * x = transform(x0);
446    if (x == x0) {
447        return a;
448    } else {
449        return makeAssertion(x, a->getKind(), a->getSense());
450    }
451}
452
453inline bool RE_Inspector::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
454    return compare(lh, rh);
455}
456
457void RE_Inspector::inspectRE(RE * re) {
458    inspect(re);
459}
460
461void RE_Inspector::inspect(RE * const re) {
462    assert (re);
463    if (mIgnoreNonUnique == InspectionMode::IgnoreNonUnique) {
464        if (mMap.count(re)) return;
465        mMap.emplace(re);
466    }
467    using T = RE::ClassTypeId;
468    #define INSPECT(Type) \
469        case T::Type: inspect##Type(llvm::cast<Type>(re)); break
470    switch (re->getClassTypeId()) {
471        INSPECT(Alt);
472        INSPECT(Assertion);
473        INSPECT(CC);
474        INSPECT(Range);
475        INSPECT(Diff);
476        INSPECT(End);
477        INSPECT(Intersect);
478        INSPECT(Name);
479        INSPECT(Group);
480        INSPECT(Rep);
481        INSPECT(Seq);
482        INSPECT(Start);
483        default: llvm_unreachable("Unknown RE type");
484    }
485    #undef INSPECT
486}
487
488void RE_Inspector::inspectName(Name * nm) {
489    RE * const d = nm->getDefinition();
490    if (d) inspect(d);
491}
492
493void RE_Inspector::inspectCC(CC * cc) {
494
495}
496
497void RE_Inspector::inspectStart(Start * s) {
498
499}
500
501void RE_Inspector::inspectEnd(End * e) {
502
503}
504
505void RE_Inspector::inspectSeq(Seq * seq) {
506    for (RE * e : *seq) {
507        inspect(e);
508    }
509}
510
511void RE_Inspector::inspectAlt(Alt * alt) {
512    for (RE * e : *alt) {
513        inspect(e);
514    }
515}
516
517void RE_Inspector::inspectRep(Rep * r) {
518    inspect(r->getRE());
519}
520
521void RE_Inspector::inspectIntersect(Intersect * ix) {
522    inspect(ix->getLH());
523    inspect(ix->getRH());
524}
525
526void RE_Inspector::inspectDiff(Diff * d) {
527    inspect(d->getLH());
528    inspect(d->getRH());
529}
530
531void RE_Inspector::inspectRange(Range * rg) {
532    inspect(rg->getLo());
533    inspect(rg->getHi());
534}
535
536void RE_Inspector::inspectGroup(Group * g) {
537    inspect(g->getRE());
538}
539
540void RE_Inspector::inspectAssertion(Assertion * a) {
541    inspect(a->getAsserted());
542}
543
544}
Note: See TracBrowser for help on using the repository browser.