nfa.h

Go to the documentation of this file.

#pragma once
 
#include <stack>
#include <string>
#include <vector>
#include <unordered_set>
#include <core/double_buffer.hpp>
#include <core/pos2d.h>
 
namespace teditor {
namespace parser {
 
 
 
struct NFA {
  NFA(const std::string& reg);
 
  size_t find(const std::string& str, size_t start = 0, size_t end = 0);
 
  size_t findAny(const std::string& str, size_t& matchStartPos,
                 size_t start = 0, size_t end = 0);
 
  ~NFA() { for (auto itr : states) delete itr; }
 
  bool isMatch(bool lastStateRemaining = false) const;
  bool areActiveStatesEmpty() const { return acs.current().empty(); }
  const Point& getMatchPos() const { return matchState->matchPos; }
  bool step(char c, const Point& pos);
  void reset();
  static const size_t NoMatch;
 
private:
  enum Specials {
    Split = 256,    // splitter NFA state
    Match,          // terminal state
    Digit,          // \d
    WhiteSpace,     // \s
    NonWhiteSpace,  // \S
    Any,            // .
    AnyFromList,    // [...], [A-Z], [a-z], [0-9]
    NoneFromList,   // [^...]
    Bracket,        // Temporary state for recognizing groups
    Alternation,    // Temporary state for recgonizing alternations
  };  // enum Specials
 
  struct State {
    int c;
    std::string s;    // for matching with a set of possible chars (aka [...])
    State* next;
    State* other;     // used only with Split state
    Point matchPos;  // used only for matches
    State() : c(0), s(), next(nullptr), other(nullptr) {}
    State(int _c): c(_c), s(), next(nullptr), other(nullptr) {}
    bool isMatch(char in) const;
  };  // struct State
 
  typedef std::unordered_set<State*> Actives;
 
  std::string regex;
  std::vector<State*> states;  // all states for this NFA
  State *startState;
  State *matchState;
  // during matching these are the "active" states
  // this does NOT own the underlying pointers
  // uses double-buffering to avoid corruption
  DoubleBuffer<Actives> acs;
 
  void stepThroughSplitStates();
  void checkForSplitState(State* st, const Point& pos, Actives& ac);
 
  // used only while compiling the regex's
  // this does NOT own any of the underlying pointers
  struct Fragment {
    State* entry;
    std::vector<State*> tails;
    Fragment(): entry(nullptr), tails() {}
    Fragment(State* e);
    void addState(State* s);
    void appendState(State* s) { tails.push_back(s); }
  };  // struct Fragment
 
  // stack of fragments used during the regex compilation
  std::stack<Fragment> fragments;
 
  // used to store intermediate regex compiler state
  struct CompilerState {
    bool prevBackSlash;
    bool prevSqBracketOpen;
    bool isUnderRange;
    bool isUnderSqBracket;
    CompilerState();
    void validate(const std::string& reg);
  };  // struct CompilerState
 
  void parseChar(char c, CompilerState& cState);
  void parseGeneral(char c, CompilerState& cState);
  void parseInsideSqBracket(char c, CompilerState& cState);
  State* createState(int c);
  void addNewStateFor(int c);
  void stitchFragments();
};  // struct NFA
 
}  // namespace parser
}  // namespace teditor