Pattern.h

#ifndef __PATTERN_H__
#define __PATTERN_H__

#include <vector>
#include <string>
#include <map>

class Matcher;
class NFANode;
class NFAQuantifierNode;

class Pattern
{
  friend class Matcher;
  friend class NFANode;
  friend class NFAQuantifierNode;
  private:
    Pattern(const std::string & rhs);
  protected:
    static std::map<std::string, Pattern *> compiledPatterns;
    static std::map<std::string, std::pair<std::string, unsigned long> > registeredPatterns;
  protected:
    std::map<NFANode*, bool> nodes;
    Matcher * matcher;
    NFANode * head;
    std::string pattern;
    bool error;
    int curInd;
    int groupCount;
    int nonCapGroupCount;
    unsigned long flags;
  protected:
    void raiseError();
    NFANode * registerNode(NFANode * node);

    std::string classUnion      (std::string s1, std::string s2)  const;
    std::string classIntersect  (std::string s1, std::string s2)  const;
    std::string classNegate     (std::string s1)                  const;
    std::string classCreateRange(char low,       char hi)         const;

    int getInt(int start, int end);
    bool quantifyCurly(int & sNum, int & eNum);
    NFANode * quantifyGroup(NFANode * start, NFANode * stop, const int gn);

    NFANode * quantify(NFANode * newNode);
    std::string parseClass();
    std::string parsePosix();
    std::string parseOctal();
    std::string parseHex();
    NFANode *   parseBackref();
    std::string parseEscape(bool & inv, bool & quo);
    NFANode * parseRegisteredPattern(NFANode ** end);
    NFANode * parseBehind(const bool pos, NFANode ** end);
    NFANode * parseQuote();
    NFANode * parse(const bool inParen = 0, const bool inOr = 0, NFANode ** end = NULL);
  public:
    const static unsigned long CASE_INSENSITIVE;
    const static unsigned long LITERAL;
    const static unsigned long DOT_MATCHES_ALL;
    const static unsigned long MULTILINE_MATCHING;
    const static unsigned long UNIX_LINE_MODE;
    const static int MIN_QMATCH;
    const static int MAX_QMATCH;
  public:
    static Pattern                    * compile        (const std::string & pattern,
                                                        const unsigned long mode = 0);
    static Pattern                    * compileAndKeep (const std::string & pattern,
                                                        const unsigned long mode = 0);

    static std::string                  replace        (const std::string & pattern,
                                                        const std::string & str,
                                                        const std::string & replacementText,
                                                        const unsigned long mode = 0);

    static std::vector<std::string>     split          (const std::string & pattern,
                                                        const std::string & str,
                                                        const bool keepEmptys = 0,
                                                        const unsigned long limit = 0,
                                                        const unsigned long mode = 0);

    static std::vector<std::string>     findAll        (const std::string & pattern,
                                                        const std::string & str,
                                                        const unsigned long mode = 0);

    static bool                         matches        (const std::string & pattern,
                                                        const std::string & str,
                                                        const unsigned long mode = 0);

    static bool                         registerPattern(const std::string & name,
                                                        const std::string & pattern,
                                                        const unsigned long mode = 0);

    static void                         unregisterPatterns();
    static void                         clearPatternCache();

    static std::pair<std::string, int>  findNthMatch   (const std::string & pattern,
                                                        const std::string & str,
                                                        const int matchNum,
                                                        const unsigned long mode = 0);
  public:
    ~Pattern();

    std::string               replace        (const std::string & str,
                                              const std::string & replacementText);
    std::vector<std::string>  split          (const std::string & str, const bool keepEmptys = 0,
                                              const unsigned long limit = 0);
    std::vector<std::string>  findAll        (const std::string & str);
    bool                      matches        (const std::string & str);
    unsigned long             getFlags       () const;
    std::string               getPattern     () const;
    Matcher                 * createMatcher  (const std::string & str);
};

class NFANode
{
  friend class Matcher;
  public:
    NFANode * next;
    NFANode();
    virtual ~NFANode();
    virtual void findAllNodes(std::map<NFANode*, bool> & soFar);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const = 0;
    inline virtual bool isGroupHeadNode()     const { return false; }
    inline virtual bool isStartOfInputNode()  const { return false; }
};
class NFACharNode : public NFANode
{
  protected:
    char ch;
  public:
    NFACharNode(const char c);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFACICharNode : public NFANode
{
  protected:
    char ch;
  public:
    NFACICharNode(const char c);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAStartNode : public NFANode
{
  public:
    NFAStartNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAEndNode : public NFANode
{
  public:
    NFAEndNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAQuantifierNode : public NFANode
{
  public:
    int min, max;
    NFANode * inner;
    virtual void findAllNodes(std::map<NFANode*, bool> & soFar);
    NFAQuantifierNode(Pattern * pat, NFANode * internal,
                      const int minMatch = Pattern::MIN_QMATCH,
                      const int maxMatch = Pattern::MAX_QMATCH);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAGreedyQuantifierNode : public NFAQuantifierNode
{
  public:
    NFAGreedyQuantifierNode(Pattern * pat, NFANode * internal,
                            const int minMatch = Pattern::MIN_QMATCH,
                            const int maxMatch = Pattern::MAX_QMATCH);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    virtual int matchInternal(const std::string & str, Matcher * matcher, const int curInd, const int soFar) const;
};
class NFALazyQuantifierNode : public NFAQuantifierNode
{
  public:
    NFALazyQuantifierNode(Pattern * pat, NFANode * internal,
                          const int minMatch = Pattern::MIN_QMATCH,
                          const int maxMatch = Pattern::MAX_QMATCH);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAPossessiveQuantifierNode : public NFAQuantifierNode
{
  public:
    NFAPossessiveQuantifierNode(Pattern * pat, NFANode * internal,
                                const int minMatch = Pattern::MIN_QMATCH,
                                const int maxMatch = Pattern::MAX_QMATCH);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAAcceptNode : public NFANode
{
  public:
    NFAAcceptNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAClassNode : public NFANode
{
  public:
    bool inv;
    std::map<char, bool> vals;
    NFAClassNode(const bool invert = 0);
    NFAClassNode(const std::string & clazz, const bool invert);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFACIClassNode : public NFANode
{
  public:
    bool inv;
    std::map<char, bool> vals;
    NFACIClassNode(const bool invert = 0);
    NFACIClassNode(const std::string & clazz, const bool invert);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFASubStartNode : public NFANode
{
  public:
    NFASubStartNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAOrNode : public NFANode
{
  public:
    NFANode * one;
    NFANode * two;
    NFAOrNode(NFANode * first, NFANode * second);
    virtual void findAllNodes(std::map<NFANode*, bool> & soFar);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAQuoteNode : public NFANode
{
  public:
    std::string qStr;
    NFAQuoteNode(const std::string & quoted);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFACIQuoteNode : public NFANode
{
  public:
    std::string qStr;
    NFACIQuoteNode(const std::string & quoted);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFALookAheadNode : public NFANode
{
  public:
    bool pos;
    NFANode * inner;
    NFALookAheadNode(NFANode * internal, const bool positive);
    virtual void findAllNodes(std::map<NFANode*, bool> & soFar);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFALookBehindNode : public NFANode
{
  public:
    bool pos;
    std::string mStr;
    NFALookBehindNode(const std::string & str, const bool positive);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAStartOfLineNode : public NFANode
{
  public:
    NFAStartOfLineNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAEndOfLineNode : public NFANode
{
  public:
    NFAEndOfLineNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAReferenceNode : public NFANode
{
  public:
    int gi;
    NFAReferenceNode(const int groupIndex);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAStartOfInputNode : public NFANode
{
  public:
    NFAStartOfInputNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    inline virtual bool isStartOfInputNode()  const { return true; }
};
class NFAEndOfInputNode : public NFANode
{
  public:
    bool term;
    NFAEndOfInputNode(const bool lookForTerm);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAWordBoundaryNode : public NFANode
{
  public:
    bool pos;
    NFAWordBoundaryNode(const bool positive);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAEndOfMatchNode : public NFANode
{
  public:
    NFAEndOfMatchNode();
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAGroupHeadNode : public NFANode
{
  public:
    int gi;
    NFAGroupHeadNode(const int groupIndex);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    inline virtual bool isGroupHeadNode()     const { return true; }
};
class NFAGroupTailNode : public NFANode
{
  public:
    int gi;
    NFAGroupTailNode(const int groupIndex);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAGroupLoopPrologueNode : public NFANode
{
  public:
    int gi;
    NFAGroupLoopPrologueNode(const int groupIndex);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};
class NFAGroupLoopNode : public NFANode
{
  public:
    int gi, min, max, type;
    NFANode * inner;
    NFAGroupLoopNode(NFANode * internal, const int minMatch,
                     const int maxMatch, const int groupIndex, const int matchType);
    virtual void findAllNodes(std::map<NFANode*, bool> & soFar);
    virtual int match(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    int matchGreedy(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    int matchLazy(const std::string & str, Matcher * matcher, const int curInd = 0) const;
    int matchPossessive(const std::string & str, Matcher * matcher, const int curInd = 0) const;
};

#endif

---