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

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