Branch data     Line data    Source code

       1                 :            : // $Id: NFA.h 6219 2008-10-01 05:39:07Z vern $
       2                 :            : //
       3                 :            : // See the file "COPYING" in the main distribution directory for copyright.
       4                 :            : 
       5                 :            : #ifndef nfa_h
       6                 :            : #define nfa_h
       7                 :            : 
       8                 :            : #include "RE.h"
       9                 :            : #include "IntSet.h"
      10                 :            : 
      11                 :            : class NFA_State;
      12                 :            : class EquivClass;
      13                 :            : 
      14                 :     394056 : declare(PList,NFA_State);
      15                 :            : typedef PList(NFA_State) NFA_state_list;
      16                 :            : 
      17                 :            : #define NO_ACCEPT 0
      18                 :            : 
      19                 :            : #define NO_UPPER_BOUND -1
      20                 :            : 
      21                 :            : #define SYM_BOL 256
      22                 :            : #define SYM_EOL 257
      23                 :            : #define NUM_SYM 258
      24                 :            : 
      25                 :            : #define SYM_EPSILON 259
      26                 :            : #define SYM_CCL 260    
      27                 :            : 
      28                 :            : 
      29                 :            : class NFA_State : public BroObj  {
      30                 :            : public:
      31                 :            :         NFA_State(int sym, EquivClass* ec);
      32                 :            :         NFA_State(CCL* ccl);
      33                 :            :         ~NFA_State();
      34                 :            : 
      35                 :      68290 :         void AddXtion(NFA_State* next_state)    { xtions.append(next_state); }
      36                 :       9318 :         NFA_state_list* Transitions()           { return &xtions; }
      37                 :            :         void AddXtionsTo(NFA_state_list* ns);
      38                 :            : 
      39                 :        444 :         void SetAccept(int accept_val)  { accept = accept_val; }
      40                 :      19422 :         int Accept() const              { return accept; }
      41                 :            : 
      42                 :            :         // Returns a deep copy of this NFA state and everything it points
      43                 :            :         // to.  Upon return, each state's marker is set to point to its
      44                 :            :         // copy.
      45                 :            :         NFA_State* DeepCopy();
      46                 :            : 
      47                 :      32118 :         void SetMark(NFA_State* m)      { mark = m; }
      48                 :      14206 :         NFA_State* Mark() const         { return mark; }
      49                 :            :         void ClearMarks();
      50                 :            : 
      51                 :     150975 :         int TransSym() const    { return sym; }
      52                 :      18034 :         CCL* TransCCL() const   { return ccl; }
      53                 :     370663 :         int ID() const          { return id; }
      54                 :            : 
      55                 :            :         NFA_state_list* EpsilonClosure();
      56                 :            : 
      57                 :            :         void Describe(ODesc* d) const;
      58                 :            :         void Dump(FILE* f);
      59                 :            : 
      60                 :            :         // Recursivly count all the reachable states.
      61                 :            :         unsigned int TotalMemoryAllocation() const;
      62                 :            : 
      63                 :            : protected:
      64                 :            :         int sym;        // if SYM_CCL, then use ccl
      65                 :            :         CCL* ccl;       // if nil, then use sym
      66                 :            :         int accept;
      67                 :            :         int id; // number that uniquely identifies this state
      68                 :            :         NFA_state_list xtions;
      69                 :            :         NFA_state_list* epsclosure;
      70                 :            :         NFA_State* mark;
      71                 :            : };
      72                 :            : 
      73 [ +  - ][ #  # ]:        367 : class EpsilonState : public NFA_State {
      74                 :            : public:
      75                 :      35723 :         EpsilonState()  : NFA_State(SYM_EPSILON, 0)     { }
      76                 :            : };
      77                 :            : 
      78                 :            : class NFA_Machine : public BroObj {
      79                 :            : public:
      80                 :            :         NFA_Machine(NFA_State* first, NFA_State* final = 0);
      81                 :            :         ~NFA_Machine();
      82                 :            : 
      83                 :      44370 :         NFA_State* FirstState() const   { return first_state; }
      84                 :            : 
      85                 :            :         void SetFinalState(NFA_State* final)    { final_state = final; }
      86                 :      19586 :         NFA_State* FinalState() const           { return final_state; }
      87                 :            : 
      88                 :            :         void AddAccept(int accept_val);
      89                 :            : 
      90                 :       1699 :         void MakeClosure()      { MakePositiveClosure(); MakeOptional(); }
      91                 :            :         void MakeOptional();
      92                 :            :         void MakePositiveClosure();
      93                 :            : 
      94                 :            :         // re{lower,upper}; upper can be NO_UPPER_BOUND = infinity.
      95                 :            :         void MakeRepl(int lower, int upper);
      96                 :            : 
      97                 :       1518 :         void MarkBOL()          { bol = 1; }
      98                 :        759 :         void MarkEOL()          { eol = 1; }
      99                 :            : 
     100                 :            :         NFA_Machine* DuplicateMachine();
     101                 :            :         void LinkCopies(int n);
     102                 :            :         void InsertEpsilon();
     103                 :            :         void AppendEpsilon();
     104                 :            : 
     105                 :            :         void AppendState(NFA_State* new_state);
     106                 :            :         void AppendMachine(NFA_Machine* new_mach);
     107                 :            : 
     108                 :            :         void Describe(ODesc* d) const;
     109                 :            :         void Dump(FILE* f);
     110                 :            :         void DumpStats(FILE* f);
     111                 :            : 
     112                 :          0 :         unsigned int MemoryAllocation() const
     113                 :          0 :                 { return padded_sizeof(*this) + first_state->TotalMemoryAllocation(); }
     114                 :            : 
     115                 :            : protected:
     116                 :            :         NFA_State* first_state;
     117                 :            :         NFA_State* final_state;
     118                 :            :         int bol, eol;
     119                 :            : };
     120                 :            : 
     121                 :            : extern NFA_Machine* make_alternate(NFA_Machine* m1, NFA_Machine* m2);
     122                 :            : 
     123                 :            : // The epsilon closure is the set of all states reachable by an arbitrary
     124                 :            : // number of epsilon transitions, which themselves do not have epsilon
     125                 :            : // transitions going out, unioned with the set of states which have non-null
     126                 :            : // accepting numbers.  "states" is deleted by the call.  The return value
     127                 :            : // is the epsilon closure (sorted by state IDs()).
     128                 :            : extern NFA_state_list* epsilon_closure(NFA_state_list* states);
     129                 :            : 
     130                 :            : // For sorting NFA states based on their ID fields (decreasing)
     131                 :            : extern int NFA_state_cmp_neg(const void* v1, const void* v2);
     132                 :            : 
     133                 :            : #endif