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

Last change on this file was 5872, checked in by cameron, 6 days ago

Decoupling CC compilers from Pablo Kernel

File size: 6.8 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; class Alphabet;}
15namespace pablo { class PabloAST; }
16namespace pablo { class PabloBuilder; }
17namespace pablo { class PabloKernel; }
18namespace pablo { class Var; }
19namespace re { class Alt; }
20namespace re { class Assertion; }
21namespace re { class Diff; }
22namespace re { class Intersect; }
23namespace re { class Name; }
24namespace re { class RE; }
25namespace re { class Rep; }
26namespace re { class CC; }
27
28/*   Marker streams represent the results of matching steps.
29     Three types of marker streams are used internally.
30     FinalMatchUnit markers are used for character classes and
31     other strings identified by a one bit at their final position.
32     InitialPostPositionUnit markers are used to mark matches with
33     a 1 bit immediately after a match.   InitialPostPositionUnit markers
34     are generally required whenever a regular expression element
35     can match the empty string (e.g., * and ? repeated items).
36     FinalPostPositionUnit markers are used for single code unit
37     lookahead assertions. 
38*/
39
40namespace re {
41
42class RE_Compiler {
43public:
44
45    enum MarkerPosition {FinalMatchUnit, InitialPostPositionUnit, FinalPostPositionUnit};
46
47    struct MarkerType {
48        MarkerPosition pos;
49        pablo::PabloAST * stream;
50        MarkerType & operator =(const MarkerType &) = default;
51    };
52
53    RE_Compiler(pablo::PabloKernel * kernel, cc::CC_Compiler & ccCompiler);
54   
55    //
56    // The CCs (character classes) within a regular expression are generally
57    // expressed using a single alphabet.   But multiple alphabets may be
58    // used under some circumstances.   For example, regular expressions for
59    // Unicode may use both the Unicode alphabet for full Unicode characters
60    // as well as the Byte alphabet for the individual code units of UTF-8.
61    // In other cases, a multiplexed alphabet may be used for a certain
62    // subexpression, for example, if the subexpression involves a local
63    // language or a capture-backreference combination.
64    //
65    // Alphabets are added as needed using the addAlphabet method, giving both
66    // the alphabet value and the set of parallel bit streams that comprise
67    // a basis for the coded alphabet values.
68
69    void addAlphabet(cc::Alphabet * a, std::vector<pablo::PabloAST* > basis_set);
70
71    pablo::PabloAST * compile(RE * re, pablo::PabloAST * const initialCursors = nullptr);
72
73    static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
74   
75private:
76
77    struct NameMap {
78        NameMap(NameMap * parent = nullptr) : mParent(parent), mMap() {}
79        bool get(const Name * name, MarkerType & marker) const {
80            auto f = mMap.find(name);
81            if (f == mMap.end()) {
82                return mParent ? mParent->get(name, marker) : false;
83            } else {
84                marker = f->second;
85                return true;
86            }
87        }
88        void add(const Name * const name, MarkerType marker) {
89            mMap.emplace(name, std::move(marker));
90        }
91        NameMap * getParent() const { return mParent; }
92    private:
93        NameMap * const mParent;
94        boost::container::flat_map<const Name *, MarkerType> mMap;
95    };
96
97
98    MarkerType compile(RE * re, pablo::PabloBuilder & pb);
99    MarkerType compile(RE * re, pablo::PabloAST * const cursors, pablo::PabloBuilder & pb);
100
101    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
102    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
103    MarkerType compileCC(CC * cc, MarkerType marker, pablo::PabloBuilder & pb);
104    MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
105    MarkerType compileSeqTail(Seq::const_iterator current, const Seq::const_iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
106    MarkerType compileAlt(Alt * alt, MarkerType base, pablo::PabloBuilder & pb);
107    MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
108    MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
109    MarkerType compileDiff(Diff * diff, MarkerType marker, pablo::PabloBuilder & cg);
110    MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
111    pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated_j, int j, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
112    pablo::PabloAST * reachable(pablo::PabloAST * repeated, int length, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
113    static bool isFixedLength(RE * regexp);
114    MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, int ifGroupSize, pablo::PabloBuilder & pb);
115    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
116    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  pablo::PabloBuilder & pb);
117
118    MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
119    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
120    MarkerType compileStart(MarkerType marker, pablo::PabloBuilder & pb);
121    MarkerType compileEnd(MarkerType marker, pablo::PabloBuilder & pb);
122
123    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
124    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
125
126    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
127    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
128    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
129
130private:
131
132    pablo::PabloBlock * const                       mEntryScope;
133    std::vector<cc::Alphabet *>                     mAlphabets;
134    std::vector<std::unique_ptr<cc::CC_Compiler>>   mAlphabetCompilers;
135
136    bool                                            mCountOnly;
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};
146
147}
148
149#endif // COMPILER_H
Note: See TracBrowser for help on using the repository browser.