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

Last change on this file since 5812 was 5812, checked in by nmedfort, 13 months ago

Bug fix for RE local + some clean up of RE local and the RE Compiler

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