QCodeEdit 2.2
lib/qnfa/qnfa.h
Go to the documentation of this file.
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_