source: icGREP/icgrep-devel/icgrep/re/re_compiler.h @ 5810

Last change on this file since 5810 was 5810, checked in by cameron, 19 months ago

RE optimizations

File size: 5.7 KB
RevLine 
[3850]1/*
2 *  Copyright (c) 2014 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
[4197]7#ifndef RE_TO_PABLO_COMPILER_H
8#define RE_TO_PABLO_COMPILER_H
[3850]9
[5267]10#include <re/re_seq.h>  // for Seq
[5233]11#include <boost/container/flat_map.hpp>
[5357]12#include <pablo/builder.hpp>
[5267]13#include <vector>       // for vector<>::iterator
14namespace cc { class CC_Compiler; }
15namespace pablo { class PabloAST; }
16namespace pablo { class PabloBuilder; }
17namespace pablo { class PabloKernel; }
18namespace re { class Alt; }
19namespace re { class Assertion; }
20namespace re { class Diff; }
21namespace re { class Intersect; }
22namespace re { class Name; }
23namespace re { class RE; }
24namespace re { class Rep; }
[5555]25namespace re { class CC; }
[3850]26
[5267]27//namespace UCD {
28//class UnicodeSet;
29//}
[4657]30
[4411]31/*   Marker streams represent the results of matching steps.
32     Three types of marker streams are used internally.
[5045]33     FinalMatchUnit markers are used for character classes and
[4411]34     other strings identified by a one bit at their final position.
[5045]35     InitialPostPositionUnit markers are used to mark matches with
36     a 1 bit immediately after a match.   InitialPostPositionUnit markers
[4411]37     are generally required whenever a regular expression element
38     can match the empty string (e.g., * and ? repeated items).
[5045]39     FinalPostPositionUnit markers are used for single code unit
[4411]40     lookahead assertions. 
[4340]41*/
[4411]42
[4194]43namespace re {
[4340]44
[5810]45enum MarkerPosition {FinalMatchUnit, InitialPostPositionUnit, FinalPostPositionUnit};
[4340]46
47struct MarkerType { 
48    MarkerPosition pos;
[4438]49    pablo::PabloAST * stream;
[5233]50    MarkerType & operator =(const MarkerType &) = default;
[4340]51};
52
[5233]53inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
[4340]54
[5233]55inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
56
[4439]57inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
[4340]58
59
[4197]60class RE_Compiler {
61public:
[4210]62
[5780]63    RE_Compiler(pablo::PabloKernel * kernel, cc::CC_Compiler & ccCompiler);
[5732]64    pablo::PabloAST * compile(RE * re);
[4210]65
[5308]66    static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
67   
[4197]68private:
[4214]69
[5233]70    struct NameMap {
71        NameMap(NameMap * parent = nullptr) : mParent(parent), mMap() {}
72        bool get(const Name * name, MarkerType & marker) const {
73            auto f = mMap.find(name);
74            if (f == mMap.end()) {
75                return mParent ? mParent->get(name, marker) : false;
76            } else {
77                marker = f->second;
78                return true;
79            }
80        }
81        void add(const Name * const name, MarkerType marker) {
82            mMap.emplace(name, std::move(marker));
83        }
84        NameMap * getParent() const { return mParent; }
85    private:
86        NameMap * const mParent;
87        boost::container::flat_map<const Name *, MarkerType> mMap;
88    };
89
[4622]90    MarkerType compile(RE * re, pablo::PabloBuilder & cg);
[4841]91
[4622]92    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
[4829]93    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
[5555]94    MarkerType compileCC(CC * cc, MarkerType marker, pablo::PabloBuilder & pb);
[4831]95    MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
[5233]96    MarkerType compileSeqTail(Seq::iterator current, const Seq::iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
[4831]97    MarkerType compileAlt(Alt * alt, MarkerType marker, pablo::PabloBuilder & pb);
98    MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
99    MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
100    MarkerType compileDiff(Diff * diff, MarkerType marker, pablo::PabloBuilder & cg);
101    MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
[5720]102    pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated_j, int j, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
[5710]103    pablo::PabloAST * reachable(pablo::PabloAST * repeated, int length, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
[4280]104    static bool isFixedLength(RE * regexp);
[5555]105    MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, int ifGroupSize, pablo::PabloBuilder & pb);
[4622]106    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
[5555]107    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  pablo::PabloBuilder & pb);
[4194]108
[4831]109    MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
[4829]110    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
[5782]111    MarkerType compileStart(MarkerType marker, pablo::PabloBuilder & pb);
112    MarkerType compileEnd(MarkerType marker, pablo::PabloBuilder & pb);
[4829]113
[4841]114    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
115    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
116
[4622]117private:
118
[5217]119    pablo::PabloKernel * const                      mKernel;
[5134]120    bool                                            mCountOnly;
[4622]121    cc::CC_Compiler &                               mCCCompiler;
[5091]122    pablo::PabloAST *                               mLineBreak;
[4340]123    pablo::PabloAST *                               mCRLF;
[4439]124    pablo::PabloAST *                               mInitial;
[5202]125    pablo::PabloAST *                               mNonFinal;
[4520]126    pablo::PabloAST *                               mFinal;
[4609]127    pablo::PabloAST *                               mWhileTest;
[4442]128    int                                             mStarDepth;
[5202]129    pablo::PabloBuilder &                           mPB;
[5233]130    NameMap *                                       mCompiledName;
131    NameMap                                         mBaseMap;
[3850]132};
133
[4194]134}
135
[4197]136#endif // COMPILER_H
Note: See TracBrowser for help on using the repository browser.