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

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

Allow RE compilers to be associated with any Pablo block, not just kernel entry

File size: 6.8 KB
Line 
1/*
2 *  Copyright (c) 2018 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; class Alphabet;}
15namespace pablo { class PabloAST; }
16namespace pablo { class PabloBlock; }
17namespace pablo { class Var; }
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::PabloBlock * scope, cc::CC_Compiler & ccCompiler);
53   
54    //
55    // The CCs (character classes) within a regular expression are generally
56    // expressed using a single alphabet.   But multiple alphabets may be
57    // used under some circumstances.   For example, regular expressions for
58    // Unicode may use both the Unicode alphabet for full Unicode characters
59    // as well as the Byte alphabet for the individual code units of UTF-8.
60    // In other cases, a multiplexed alphabet may be used for a certain
61    // subexpression, for example, if the subexpression involves a local
62    // language or a capture-backreference combination.
63    //
64    // Alphabets are added as needed using the addAlphabet method, giving both
65    // the alphabet value and the set of parallel bit streams that comprise
66    // a basis for the coded alphabet values.
67
68    void addAlphabet(cc::Alphabet * a, std::vector<pablo::PabloAST* > basis_set);
69   
70    void addPrecompiled(std::string precompiledName, pablo::PabloAST * precompiledStream);
71
72    pablo::PabloAST * compile(RE * re, pablo::PabloAST * const initialCursors = nullptr);
73
74    static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
75   
76private:
77
78    struct NameMap {
79        NameMap(NameMap * parent = nullptr) : mParent(parent), mMap() {}
80        bool get(const Name * name, MarkerType & marker) const {
81            auto f = mMap.find(name);
82            if (f == mMap.end()) {
83                return mParent ? mParent->get(name, marker) : false;
84            } else {
85                marker = f->second;
86                return true;
87            }
88        }
89        void add(const Name * const name, MarkerType marker) {
90            mMap.emplace(name, std::move(marker));
91        }
92        NameMap * getParent() const { return mParent; }
93    private:
94        NameMap * const mParent;
95        boost::container::flat_map<const Name *, MarkerType> mMap;
96    };
97
98
99    MarkerType compile(RE * re, pablo::PabloBuilder & pb);
100    MarkerType compile(RE * re, pablo::PabloAST * const cursors, pablo::PabloBuilder & pb);
101
102    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
103    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
104    MarkerType compileCC(CC * cc, MarkerType marker, pablo::PabloBuilder & pb);
105    MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
106    MarkerType compileSeqTail(Seq::const_iterator current, const Seq::const_iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
107    MarkerType compileAlt(Alt * alt, MarkerType base, pablo::PabloBuilder & pb);
108    MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
109    MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
110    MarkerType compileDiff(Diff * diff, MarkerType marker, pablo::PabloBuilder & cg);
111    MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
112    pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated_j, int j, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
113    pablo::PabloAST * reachable(pablo::PabloAST * repeated, int length, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
114    static bool isFixedLength(RE * regexp);
115    MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, int ifGroupSize, pablo::PabloBuilder & pb);
116    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
117    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  pablo::PabloBuilder & pb);
118
119    MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
120    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
121    MarkerType compileStart(MarkerType marker, pablo::PabloBuilder & pb);
122    MarkerType compileEnd(MarkerType marker, pablo::PabloBuilder & pb);
123
124    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
125    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
126
127    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
128    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
129    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
130
131private:
132
133    pablo::PabloBlock * const                       mEntryScope;
134    std::vector<cc::Alphabet *>                     mAlphabets;
135    std::vector<std::unique_ptr<cc::CC_Compiler>>   mAlphabetCompilers;
136
137    cc::CC_Compiler &                               mCCCompiler;
138    pablo::PabloAST *                               mLineBreak;
139    pablo::PabloAST *                               mNonFinal;
140    pablo::PabloAST *                               mFinal;
141    pablo::PabloAST *                               mWhileTest;
142    int                                             mStarDepth;
143    NameMap *                                       mCompiledName;
144    NameMap                                         mBaseMap;
145    std::map<std::string, pablo::PabloAST *>        mExternalNameMap;
146
147};
148
149}
150
151#endif // COMPILER_H
Note: See TracBrowser for help on using the repository browser.