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

Last change on this file was 6297, checked in by cameron, 8 weeks ago

Merge branch 'master' of https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel

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