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