source/regex.h

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