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

Last change on this file since 6184 was 6184, checked in by nmedfort, 9 months ago

Initial version of PipelineKernel? + revised StreamSet? model.

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