QCodeEdit 2.2
|
00001 /**************************************************************************** 00002 ** 00003 ** Copyright (C) 2006-2009 fullmetalcoder <fullmetalcoder@hotmail.fr> 00004 ** 00005 ** This file is part of the Edyuk project <http://edyuk.org> 00006 ** 00007 ** This file may be used under the terms of the GNU General Public License 00008 ** version 3 as published by the Free Software Foundation and appearing in the 00009 ** file GPL.txt included in the packaging of this file. 00010 ** 00011 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00012 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00013 ** 00014 ****************************************************************************/ 00015 00016 #ifndef _Q_NFA_H_ 00017 #define _Q_NFA_H_ 00018 00024 #include <QChar> 00025 #include <QList> 00026 #include <QHash> 00027 #include <QStack> 00028 #include <QString> 00029 00030 #include "light_vector.h" 00031 00032 struct QNFA; 00033 00034 typedef light_vector<quint16> QNFASet; 00035 00036 class QNFABranch : public light_vector<QNFA*> 00037 { 00038 public: 00039 ~QNFABranch(); 00040 }; 00041 00042 enum NFAType 00043 { 00044 Char = 0, 00045 00046 Match = 1, 00047 00048 CxtBeg = 2, 00049 CxtEnd = 4, 00050 CxtEsc = 8, 00051 00052 ContextBegin = Match | CxtBeg, 00053 ContextEnd = Match | CxtEnd, 00054 EscapeSeq = Match | CxtEsc, 00055 00056 Escaped = 16, 00057 Exclusive = 32, 00058 StayOnLine = 64, 00059 00060 Reserved = 128 00061 }; 00062 00063 enum NFAAssertion 00064 { 00065 NoAssertion = 0, 00066 00067 One = 0, // default standard 00068 ZeroOrOne = 1, // ? 00069 ZeroOrMore = 2, // * 00070 OneOrMore = 4, // + 00071 00072 WordStart = 8, 00073 WordEnd = 16, 00074 00075 Word = 32, 00076 NonWord = 64, 00077 00078 Digit = 128, 00079 NonDigit = 256, 00080 00081 Space = 512, 00082 NonSpace = 1024, 00083 00084 CaseSensitive = 2048 00085 }; 00086 00087 struct QCharTreeNode; 00088 00089 typedef QHash<quint16, QCharTreeNode> QCharTreeLevel; 00090 00091 struct QCharTreeNode 00092 { 00093 inline QCharTreeNode(quint16 v = 0) { value.unicode = v; } 00094 inline QCharTreeNode(const QCharTreeNode& o) { value = o.value; next = o.next; } 00095 00096 union 00097 { 00098 int action; 00099 quint16 unicode; 00100 } value; 00101 00102 QCharTreeLevel next; 00103 }; 00104 00105 Q_DECLARE_TYPEINFO(QCharTreeNode, Q_MOVABLE_TYPE); 00106 00107 typedef QCharTreeLevel QCharTree; 00108 00109 struct QNFA 00110 { 00111 QNFA(); 00112 ~QNFA(); 00113 00114 QNFASet c; 00115 QCharTree tree; 00116 00117 union 00118 { 00119 QNFA *next; 00120 QNFABranch *branch; 00121 } out; 00122 00123 quint8 type; 00124 quint16 assertion; 00125 00126 int actionid; 00127 00128 static quint32 _count; 00129 }; 00130 00131 struct QNFAMatchContext 00132 { 00133 inline QNFAMatchContext(QNFA *root = 0) : context(root) {} 00134 00135 inline QNFAMatchContext& operator = (QNFAMatchContext *c) 00136 { 00137 if ( c ) 00138 { 00139 context = c->context; 00140 parents = c->parents; 00141 meaningless = c->meaningless; 00142 } else { 00143 reset(); 00144 } 00145 00146 return *this; 00147 } 00148 00149 inline QNFAMatchContext& operator = (const QNFAMatchContext& c) 00150 { 00151 context = c.context; 00152 parents = c.parents; 00153 meaningless = c.meaningless; 00154 00155 return *this; 00156 } 00157 00158 inline void reset() 00159 { 00160 context = 0; 00161 00162 while ( parents.count() ) 00163 context = parents.pop(); 00164 } 00165 00166 QNFA *context; 00167 QNFASet meaningless; 00168 QStack<QNFA*> parents; 00169 }; 00170 00171 class QNFAMatchHandler 00172 { 00173 public: 00174 virtual ~QNFAMatchHandler() {} 00175 00176 virtual void matched(int pos, int len, int action) = 0; 00177 }; 00178 00179 class QNFAMatchNotifier 00180 { 00181 private: 00182 struct Command 00183 { 00184 inline Command(int p, int len, int act) 00185 : pos(p), length(len), action(act) {} 00186 00187 int pos; 00188 int length; 00189 int action; 00190 }; 00191 00192 typedef QList<Command> CommandList; 00193 00194 public: 00195 inline QNFAMatchNotifier(QNFAMatchHandler *h) 00196 : handler(h) {} 00197 00198 inline QNFAMatchNotifier& operator = (const QNFAMatchNotifier& n) 00199 { 00200 handler = n.handler; 00201 00202 return *this; 00203 } 00204 00205 inline void operator () (int pos, int len, int action) 00206 { 00207 if ( handler && (m_buffers.isEmpty() || m_pending.count()) ) 00208 handler->matched(pos, len, action); 00209 else 00210 m_buffers.top() << Command(pos, len, action); 00211 } 00212 00213 inline int bufferLevel() const 00214 { 00215 return m_buffers.count(); 00216 } 00217 00218 inline void startBuffering() 00219 { 00220 m_buffers.push(CommandList()); 00221 } 00222 00223 inline void stopBuffering() 00224 { 00225 m_pending = m_buffers.pop(); 00226 } 00227 00228 inline void flush() 00229 { 00230 foreach ( Command c, m_pending ) 00231 handler->matched(c.pos, c.length, c.action); 00232 00233 m_pending.clear(); 00234 } 00235 00236 inline void clear() 00237 { 00238 m_pending.clear(); 00239 m_buffers.clear(); 00240 } 00241 00242 private: 00243 QNFAMatchHandler *handler; 00244 00245 CommandList m_pending; 00246 QStack<CommandList> m_buffers; 00247 }; 00248 00249 void match( QNFAMatchContext *lexer, 00250 const QChar *d, 00251 int length, 00252 QNFAMatchNotifier notify); 00253 00254 inline void match( QNFAMatchContext *lexer, 00255 const QString& s, 00256 QNFAMatchNotifier notify) 00257 { match(lexer, s.constData(), s.length(), notify); } 00258 00259 QNFA* lexer(); 00260 00261 void squeeze(QNFA *nfa); 00262 void squeeze(QCharTreeLevel& lvl); 00263 00264 QNFA* sharedContext(const QString& start, 00265 QNFA *other, 00266 bool cs); 00267 00268 QNFA* context( const QString& start, 00269 const QString& stop, 00270 const QString& escape, 00271 int action, 00272 QNFA **handler = 0, 00273 bool cs = true); 00274 00275 inline void addNFA(QNFA *context, QNFA *nfa) 00276 { context->out.branch->append(nfa); } 00277 00278 bool plain(const QString& word, QString *dest); 00279 00280 void addWord( QCharTree& tree, 00281 const QString& w, 00282 int action, 00283 bool cs); 00284 00285 void addWord( QNFA *lexer, 00286 const QString& w, 00287 int action, 00288 bool cs); 00289 00290 void addSequence( QNFA *lexer, 00291 const QString& w, 00292 int action, 00293 bool cs); 00294 00295 QNFA* sequence( const QChar *d, 00296 int length, 00297 QNFA **end, 00298 bool cs); 00299 00300 inline QNFA* sequence( 00301 const QString& s, 00302 QNFA **end, 00303 bool cs) 00304 { return sequence(s.constData(), s.length(), end, cs); } 00305 00306 #endif //!_Q_NFA_H_