source/strings/regex.h

   1 #ifndef MSP_STRINGS_REGEX_H_
   2 #define MSP_STRINGS_REGEX_H_
   3
   4 #include <stdexcept>
   5 #include <string>
   6 #include "regmatch.h"
   7
   8 namespace Msp {
   9
  10 class bad_regex: public std::logic_error
  11 {
  12 public:
  13         bad_regex(const std::string &, const std::string &, const std::string::const_iterator &);
  14         virtual ~bad_regex() throw() { }
  15
  16 private:
  17         std::string make_where(const std::string &, const std::string::const_iterator &);
  18 };
  19
  20
  21 /**
  22 This class provides regular expression matching.  It supports a subset of
  23 POSIX.2 extended regex syntax.  Character classes, equivalence classes and
  24 collating elements are not supported.  Refer to the regex(7) manpage for more
  25 details.
  26
  27 A description of the internal workings of the class follows.  You may skip this
  28 if you are not a developer or otherwise interested.
  29
  30 The core of this class is a virtual machine running a non-deterministic finite
  31 automaton (NFA).  The state of the automaton is represented by an iterator into
  32 the code.  Transitions between states are represented by instructions.
  33 Instructions may take multiple bytes, so a valid code iterator may not be a
  34 valid NFA state.
  35
  36 The virtual machine may have any number of execution contexts at any one time.
  37 On every cycle, each context is advanced until an input-consuming instruction
  38 is encountered, keeping the input positions in sync with each other.  Execution
  39 continues as long as there's at least one context remaining.
  40
  41 The GROUP_BEGIN and GROUP_END instructions record the begin and end offset of a
  42 match group, respectively.  The GROUP_END instruction also marks the group as
  43 successfully matched.  If the target group was already matched, these
  44 instructions do nothing.
  45
  46 The JUMP instruction causes the execution iterator to be modified by an offset.
  47
  48 The ND_JUMP instruction causes the execution context to be split in two.  One
  49 continues directly after the instruction and the other continues at an offset.
  50
  51 The NEGATE instruction causes the result of the next match instruction to be
  52 negated.
  53
  54 Match instructions compare the input against a condition.  If the match
  55 succeeds, execution continues at the next instruction.  If the match fails,
  56 execution of that context is terminated.
  57
  58 The MATCH_BEGIN and MATCH_END instructions match the beginning and end of
  59 the input string, respectively.  They do not consume input.
  60
  61 The MATCH_CHAR instruction consumes the input character and matches it against
  62 a single character.  Since regexes often match sequences of printable character,
  63 a match for a non-opcode character may be encoded as the character itself.
  64
  65 The MATCH_RANGE instruction consumes the input character and matches it against
  66 an inclusive character range.
  67
  68 The MATCH_MASK instruction consumes the input character and matches it against
  69 a bitmask.
  70
  71 The MATCH_ANY instruction consumes the input character and always succeeds.
  72 */
  73 class Regex
  74 {
  75 private:
  76         typedef std::basic_string<unsigned char> Code;
  77         typedef unsigned short Count;
  78         typedef short Offset;
  79         typedef unsigned short Index;
  80
  81         enum Instruction
  82         {
  83                 FIRST_INSTRUCTION_ = 0,
  84
  85                 JUMP,
  86                 ND_JUMP,
  87
  88                 GROUP_BEGIN,
  89                 GROUP_END,
  90
  91                 NEGATE,
  92
  93                 MATCH_BEGIN,
  94                 MATCH_END,
  95                 MATCH_CHAR,
  96                 MATCH_RANGE,
  97                 MATCH_MASK,
  98                 MATCH_ANY,
  99
 100                 LAST_INSTRUCTION_ = 31
 101         };
 102
 103         struct RunContext
 104         {
 105                 Code::const_iterator citer;
 106                 std::vector<RegMatch::Group> groups;
 107         };
 108
 109         Code code;
 110         unsigned n_groups;
 111
 112 public:
 113         /** Constructs a new Regex object from a string representation. */
 114         Regex(const std::string &expr);
 115
 116 private:
 117         /** Compiles a regular expression into NFA bytecode.  , 2011The iterator will be
 118         advanced to the first unused character in the string. */
 119         Code compile(const std::string &expr, std::string::const_iterator &iter, unsigned &group, bool branch);
 120
 121         Code parse_atom(const std::string &, std::string::const_iterator &i, unsigned &);
 122         Code parse_brackets(const std::string &, std::string::const_iterator &);
 123         bool parse_repeat(const std::string &, std::string::const_iterator &, Count &, Count &);
 124
 125 public:
 126         /** Matches the regex against a string.  Refer to RegMatch documentation for
 127         more information on the resulting object. */
 128         RegMatch match(const std::string &str) const;
 129
 130 private:
 131         bool run(const std::string &, const std::string::const_iterator &, std::vector<RegMatch::Group> &) const;
 132         bool group_compare(const RegMatch::Group &, const RegMatch::Group &) const;
 133
 134 public:
 135         /** Returns a disassembled representation of the NFA bytecode.  For debugging
 136         purposes. */
 137         std::string disassemble() const;
 138 private:
 139         std::string disassemble_instruction(Code::const_iterator &) const;
 140 };
 141
 142 } // namespace Msp
 143
 144 #endif