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

Last change on this file since 5816 was 5816, checked in by cameron, 16 months ago

Supporting multiple alphabets in RE compilation - initial check-in

File size: 6.9 KB
RevLine 
[3850]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
[4197]7#ifndef RE_TO_PABLO_COMPILER_H
8#define RE_TO_PABLO_COMPILER_H
[3850]9
[5267]10#include <re/re_seq.h>  // for Seq
[5233]11#include <boost/container/flat_map.hpp>
[5357]12#include <pablo/builder.hpp>
[5267]13#include <vector>       // for vector<>::iterator
[5816]14namespace cc { class CC_Compiler; class Alphabet;}
[5267]15namespace pablo { class PabloAST; }
16namespace pablo { class PabloBuilder; }
17namespace pablo { class PabloKernel; }
[5816]18namespace pablo { class Var; }
[5267]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; }
[5555]26namespace re { class CC; }
[3850]27
[4411]28/*   Marker streams represent the results of matching steps.
29     Three types of marker streams are used internally.
[5045]30     FinalMatchUnit markers are used for character classes and
[4411]31     other strings identified by a one bit at their final position.
[5045]32     InitialPostPositionUnit markers are used to mark matches with
33     a 1 bit immediately after a match.   InitialPostPositionUnit markers
[4411]34     are generally required whenever a regular expression element
35     can match the empty string (e.g., * and ? repeated items).
[5045]36     FinalPostPositionUnit markers are used for single code unit
[4411]37     lookahead assertions. 
[4340]38*/
[4411]39
[4194]40namespace re {
[4340]41
[5812]42class RE_Compiler {
43public:
[4340]44
[5812]45    enum MarkerPosition {FinalMatchUnit, InitialPostPositionUnit, FinalPostPositionUnit};
[4340]46
[5812]47    struct MarkerType {
48        MarkerPosition pos;
49        pablo::PabloAST * stream;
50        MarkerType & operator =(const MarkerType &) = default;
51    };
[4340]52
[5780]53    RE_Compiler(pablo::PabloKernel * kernel, cc::CC_Compiler & ccCompiler);
[5816]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, pablo::Var * basis_set);
70
[5812]71    pablo::PabloAST * compile(RE * re, pablo::PabloAST * const initialCursors = nullptr);
[4210]72
[5308]73    static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
74   
[4197]75private:
[4214]76
[5233]77    struct NameMap {
78        NameMap(NameMap * parent = nullptr) : mParent(parent), mMap() {}
79        bool get(const Name * name, MarkerType & marker) const {
80            auto f = mMap.find(name);
81            if (f == mMap.end()) {
82                return mParent ? mParent->get(name, marker) : false;
83            } else {
84                marker = f->second;
85                return true;
86            }
87        }
88        void add(const Name * const name, MarkerType marker) {
89            mMap.emplace(name, std::move(marker));
90        }
91        NameMap * getParent() const { return mParent; }
92    private:
93        NameMap * const mParent;
94        boost::container::flat_map<const Name *, MarkerType> mMap;
95    };
96
[4841]97
[5812]98    MarkerType compile(RE * re, pablo::PabloBuilder & pb);
99    MarkerType compile(RE * re, pablo::PabloAST * const cursors, pablo::PabloBuilder & pb);
100
[4622]101    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
[4829]102    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
[5555]103    MarkerType compileCC(CC * cc, MarkerType marker, pablo::PabloBuilder & pb);
[4831]104    MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
[5233]105    MarkerType compileSeqTail(Seq::iterator current, const Seq::iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
[5812]106    MarkerType compileAlt(Alt * alt, MarkerType base, pablo::PabloBuilder & pb);
[4831]107    MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
108    MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
109    MarkerType compileDiff(Diff * diff, MarkerType marker, pablo::PabloBuilder & cg);
110    MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
[5720]111    pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated_j, int j, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
[5710]112    pablo::PabloAST * reachable(pablo::PabloAST * repeated, int length, int repeat_count, pablo::PabloAST * indexStream, pablo::PabloBuilder & pb);
[4280]113    static bool isFixedLength(RE * regexp);
[5555]114    MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, int ifGroupSize, pablo::PabloBuilder & pb);
[4622]115    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
[5555]116    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  pablo::PabloBuilder & pb);
[4194]117
[4831]118    MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
[4829]119    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
[5782]120    MarkerType compileStart(MarkerType marker, pablo::PabloBuilder & pb);
121    MarkerType compileEnd(MarkerType marker, pablo::PabloBuilder & pb);
[4829]122
[4841]123    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
124    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
125
[5812]126    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
127    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
128    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
129
[4622]130private:
131
[5217]132    pablo::PabloKernel * const                      mKernel;
[5816]133    std::vector<cc::Alphabet *>                     mAlphabets;
134    std::vector<std::unique_ptr<cc::CC_Compiler>>   mAlphabetCompilers;
135
[5134]136    bool                                            mCountOnly;
[4622]137    cc::CC_Compiler &                               mCCCompiler;
[5091]138    pablo::PabloAST *                               mLineBreak;
[4340]139    pablo::PabloAST *                               mCRLF;
[4439]140    pablo::PabloAST *                               mInitial;
[5202]141    pablo::PabloAST *                               mNonFinal;
[4520]142    pablo::PabloAST *                               mFinal;
[4609]143    pablo::PabloAST *                               mWhileTest;
[4442]144    int                                             mStarDepth;
[5202]145    pablo::PabloBuilder &                           mPB;
[5233]146    NameMap *                                       mCompiledName;
147    NameMap                                         mBaseMap;
[3850]148};
149
[4194]150}
151
[4197]152#endif // COMPILER_H
Note: See TracBrowser for help on using the repository browser.