boost/boost/regex/v4/states.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   4  * Dr John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost Software License, Version 1.0. (See accompanying file
   8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         states.cpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Declares internal state machine structures.
  17   */
  18
  19 #ifndef BOOST_REGEX_V4_STATES_HPP
  20 #define BOOST_REGEX_V4_STATES_HPP
  21
  22 #ifdef BOOST_HAS_ABI_HEADERS
  23 #  include BOOST_ABI_PREFIX
  24 #endif
  25
  26 namespace boost{
  27 namespace re_detail{
  28
  29 /*** mask_type *******************************************************
  30 Whenever we have a choice of two alternatives, we use an array of bytes
  31 to indicate which of the two alternatives it is possible to take for any
  32 given input character.  If mask_take is set, then we can take the next
  33 state, and if mask_skip is set then we can take the alternative.
  34 ***********************************************************************/
  35 enum mask_type
  36 {
  37    mask_take = 1,
  38    mask_skip = 2,
  39    mask_any = mask_skip | mask_take,
  40    mask_all = mask_any
  41 };
  42
  43 /*** helpers **********************************************************
  44 These helpers let us use function overload resolution to detect whether
  45 we have narrow or wide character strings:
  46 ***********************************************************************/
  47 struct _narrow_type{};
  48 struct _wide_type{};
  49 template <class charT> struct is_byte;
  50 template<>             struct is_byte<char>         { typedef _narrow_type width_type; };
  51 template<>             struct is_byte<unsigned char>{ typedef _narrow_type width_type; };
  52 template<>             struct is_byte<signed char>  { typedef _narrow_type width_type; };
  53 template <class charT> struct is_byte               { typedef _wide_type width_type; };
  54
  55 /*** enum syntax_element_type ******************************************
  56 Every record in the state machine falls into one of the following types:
  57 ***********************************************************************/
  58 enum syntax_element_type
  59 {
  60    // start of a marked sub-expression, or perl-style (?...) extension
  61    syntax_element_startmark = 0,
  62    // end of a marked sub-expression, or perl-style (?...) extension
  63    syntax_element_endmark = syntax_element_startmark + 1,
  64    // any sequence of literal characters
  65    syntax_element_literal = syntax_element_endmark + 1,
  66    // start of line assertion: ^
  67    syntax_element_start_line = syntax_element_literal + 1,
  68    // end of line assertion $
  69    syntax_element_end_line = syntax_element_start_line + 1,
  70    // match any character: .
  71    syntax_element_wild = syntax_element_end_line + 1,
  72    // end of expression: we have a match when we get here
  73    syntax_element_match = syntax_element_wild + 1,
  74    // perl style word boundary: \b
  75    syntax_element_word_boundary = syntax_element_match + 1,
  76    // perl style within word boundary: \B
  77    syntax_element_within_word = syntax_element_word_boundary + 1,
  78    // start of word assertion: \<
  79    syntax_element_word_start = syntax_element_within_word + 1,
  80    // end of word assertion: \>
  81    syntax_element_word_end = syntax_element_word_start + 1,
  82    // start of buffer assertion: \`
  83    syntax_element_buffer_start = syntax_element_word_end + 1,
  84    // end of buffer assertion: \'
  85    syntax_element_buffer_end = syntax_element_buffer_start + 1,
  86    // backreference to previously matched sub-expression
  87    syntax_element_backref = syntax_element_buffer_end + 1,
  88    // either a wide character set [..] or one with multicharacter collating elements:
  89    syntax_element_long_set = syntax_element_backref + 1,
  90    // narrow character set: [...]
  91    syntax_element_set = syntax_element_long_set + 1,
  92    // jump to a new state in the machine:
  93    syntax_element_jump = syntax_element_set + 1,
  94    // choose between two production states:
  95    syntax_element_alt = syntax_element_jump + 1,
  96    // a repeat
  97    syntax_element_rep = syntax_element_alt + 1,
  98    // match a combining character sequence
  99    syntax_element_combining = syntax_element_rep + 1,
 100    // perl style soft buffer end: \z
 101    syntax_element_soft_buffer_end = syntax_element_combining + 1,
 102    // perl style continuation: \G
 103    syntax_element_restart_continue = syntax_element_soft_buffer_end + 1,
 104    // single character repeats:
 105    syntax_element_dot_rep = syntax_element_restart_continue + 1,
 106    syntax_element_char_rep = syntax_element_dot_rep + 1,
 107    syntax_element_short_set_rep = syntax_element_char_rep + 1,
 108    syntax_element_long_set_rep = syntax_element_short_set_rep + 1
 109 };
 110
 111 #ifdef BOOST_REGEX_DEBUG
 112 // dwa 09/26/00 - This is needed to suppress warnings about an ambiguous conversion
 113 std::ostream& operator<<(std::ostream&, syntax_element_type);
 114 #endif
 115
 116 struct re_syntax_base;
 117
 118 /*** union offset_type ************************************************
 119 Points to another state in the machine.  During machine construction
 120 we use integral offsets, but these are converted to pointers before
 121 execution of the machine.
 122 ***********************************************************************/
 123 union offset_type
 124 {
 125    re_syntax_base*   p;
 126    std::size_t       i;
 127 };
 128
 129 /*** struct re_syntax_base ********************************************
 130 Base class for all states in the machine.
 131 ***********************************************************************/
 132 struct re_syntax_base
 133 {
 134    syntax_element_type   type;         // what kind of state this is
 135    offset_type           next;         // next state in the machine
 136    unsigned int          can_be_null;  // true if we match a NULL string
 137 };
 138
 139 /*** struct re_brace **************************************************
 140 Base class for all states in the machine.
 141 ***********************************************************************/
 142 struct re_brace : public re_syntax_base
 143 {
 144    // The index to match, can be zero (don't mark the sub-expression)
 145    // or negative (for perl style (?...) extentions):
 146    int index;
 147 };
 148
 149 /*** struct re_literal ************************************************
 150 A string of literals, following this structure will be an
 151 array of characters: charT[length]
 152 ***********************************************************************/
 153 struct re_literal : public re_syntax_base
 154 {
 155    unsigned int length;
 156 };
 157
 158 /*** struct re_set_long ***********************************************
 159 A wide character set of characters, following this structure will be
 160 an array of type charT:
 161 First csingles null-terminated strings
 162 Then 2 * cranges NULL terminated strings
 163 Then cequivalents NULL terminated strings
 164 ***********************************************************************/
 165 struct re_set_long : public re_syntax_base
 166 {
 167    unsigned int            csingles, cranges, cequivalents;
 168    boost::uint_fast32_t    cclasses;
 169    bool                    isnot;
 170    bool                    singleton;
 171 };
 172
 173 /*** struct re_set ****************************************************
 174 A set of narrow-characters, matches any of _map which is none-zero
 175 ***********************************************************************/
 176 struct re_set : public re_syntax_base
 177 {
 178    unsigned char _map[256];
 179 };
 180
 181 /*** struct re_jump ***************************************************
 182 Jump to a new location in the machine (not next).
 183 ***********************************************************************/
 184 struct re_jump : public re_syntax_base
 185 {
 186    offset_type     alt;           // location to jump to
 187    unsigned char   _map[256];     // which characters can take the jump
 188 };
 189
 190 /*** struct re_repeat *************************************************
 191 Repeat a section of the machine
 192 ***********************************************************************/
 193 struct re_repeat : public re_jump
 194 {
 195    unsigned   min, max;  // min and max allowable repeats
 196    int        id;        // Unique identifier for this repeat
 197    bool       leading;   // True if this repeat is at the start of the machine (lets us optimize some searches)
 198    bool       greedy;    // True if this is a greedy repeat
 199 };
 200
 201 /*** enum re_jump_size_type *******************************************
 202 Provides compiled size of re_jump structure (allowing for trailing alignment).
 203 We provide this so we know how manybytes to insert when constructing the machine
 204 (The value of padding_mask is defined in regex_raw_buffer.hpp).
 205 ***********************************************************************/
 206 enum re_jump_size_type
 207 {
 208    re_jump_size = (sizeof(re_jump) + padding_mask) & ~(padding_mask),
 209    re_repeater_size = (sizeof(re_repeat) + padding_mask) & ~(padding_mask)
 210 };
 211
 212 /*** proc re_is_set_member *********************************************
 213 Forward declaration: we'll need this one later...
 214 ***********************************************************************/
 215 template <class iterator, class charT, class traits_type, class Allocator>
 216 iterator BOOST_REGEX_CALL re_is_set_member(iterator next,
 217                           iterator last,
 218                           const re_set_long* set_,
 219                           const reg_expression<charT, traits_type, Allocator>& e);
 220
 221 } // namespace re_detail
 222
 223 } // namespace boost
 224
 225 #ifdef BOOST_HAS_ABI_HEADERS
 226 #  include BOOST_ABI_SUFFIX
 227 #endif
 228
 229 #endif
 230
 231