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

Last change on this file was 5901, checked in by cameron, 3 months ago

RE compiler can generate UTF8_nonfinal if not provided externally

File size: 6.9 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    pablo::PabloAST * u8NonFinal(pablo::PabloBuilder & pb);
128    pablo::PabloAST * u8Final(pablo::PabloBuilder & pb);
129
130    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
131    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
132    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
133
134private:
135
136    pablo::PabloBlock * const                       mEntryScope;
137    std::vector<cc::Alphabet *>                     mAlphabets;
138    std::vector<std::unique_ptr<cc::CC_Compiler>>   mAlphabetCompilers;
139
140    cc::CC_Compiler &                               mCCCompiler;
141    pablo::PabloAST *                               mLineBreak;
142    re::Name *                                      mNonFinalName;
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.