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

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

RE Validation

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