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

Last change on this file since 5881 was 5881, checked in by cameron, 14 months ago

Grapheme Cluster Break kernel

File size: 6.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; 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    void addPrecompiled(std::string precompiledName, pablo::PabloAST * precompiledStream);
72
73    pablo::PabloAST * compile(RE * re, pablo::PabloAST * const initialCursors = nullptr);
74
75    static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
76   
77private:
78
79    struct NameMap {
80        NameMap(NameMap * parent = nullptr) : mParent(parent), mMap() {}
81        bool get(const Name * name, MarkerType & marker) const {
82            auto f = mMap.find(name);
83            if (f == mMap.end()) {
84                return mParent ? mParent->get(name, marker) : false;
85            } else {
86                marker = f->second;
87                return true;
88            }
89        }
90        void add(const Name * const name, MarkerType marker) {
91            mMap.emplace(name, std::move(marker));
92        }
93        NameMap * getParent() const { return mParent; }
94    private:
95        NameMap * const mParent;
96        boost::container::flat_map<const Name *, MarkerType> mMap;
97    };
98
99
100    MarkerType compile(RE * re, pablo::PabloBuilder & pb);
101    MarkerType compile(RE * re, pablo::PabloAST * const cursors, pablo::PabloBuilder & pb);
102
103    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
104    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
105    MarkerType compileCC(CC * cc, MarkerType marker, pablo::PabloBuilder & pb);
106    MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
107    MarkerType compileSeqTail(Seq::const_iterator current, const Seq::const_iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
108    MarkerType compileAlt(Alt * alt, MarkerType base, pablo::PabloBuilder & pb);
109    MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
110    MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
111    MarkerType compileDiff(Diff * diff, MarkerType marker, pablo::PabloBuilder & cg);
112    MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
113    pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated_j, int j, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
114    pablo::PabloAST * reachable(pablo::PabloAST * repeated, int length, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
115    static bool isFixedLength(RE * regexp);
116    MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, int ifGroupSize, pablo::PabloBuilder & pb);
117    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
118    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  pablo::PabloBuilder & pb);
119
120    MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
121    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
122    MarkerType compileStart(MarkerType marker, pablo::PabloBuilder & pb);
123    MarkerType compileEnd(MarkerType marker, pablo::PabloBuilder & pb);
124
125    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
126    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
127
128    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
129    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
130    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
131
132private:
133
134    pablo::PabloBlock * const                       mEntryScope;
135    std::vector<cc::Alphabet *>                     mAlphabets;
136    std::vector<std::unique_ptr<cc::CC_Compiler>>   mAlphabetCompilers;
137
138    bool                                            mCountOnly;
139    cc::CC_Compiler &                               mCCCompiler;
140    pablo::PabloAST *                               mLineBreak;
141    pablo::PabloAST *                               mNonFinal;
142    pablo::PabloAST *                               mFinal;
143    pablo::PabloAST *                               mWhileTest;
144    int                                             mStarDepth;
145    NameMap *                                       mCompiledName;
146    NameMap                                         mBaseMap;
147    std::map<std::string, pablo::PabloAST *>        mExternalNameMap;
148
149};
150
151}
152
153#endif // COMPILER_H
Note: See TracBrowser for help on using the repository browser.