3 * Copyright (c) 1998-2002
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)
13 * LOCATION: see http://www.boost.org for most recent version.
15 * VERSION see <boost/version.hpp>
16 * DESCRIPTION: Declares internal state machine structures.
19 #ifndef BOOST_REGEX_V4_STATES_HPP
20 #define BOOST_REGEX_V4_STATES_HPP
22 #ifdef BOOST_HAS_ABI_HEADERS
23 # include BOOST_ABI_PREFIX
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 ***********************************************************************/
39 mask_any = mask_skip | mask_take,
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{};
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; };
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
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,
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
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);
116 struct re_syntax_base;
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 ***********************************************************************/
129 /*** struct re_syntax_base ********************************************
130 Base class for all states in the machine.
131 ***********************************************************************/
132 struct re_syntax_base
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
139 /*** struct re_brace **************************************************
140 Base class for all states in the machine.
141 ***********************************************************************/
142 struct re_brace : public re_syntax_base
144 // The index to match, can be zero (don't mark the sub-expression)
145 // or negative (for perl style (?...) extentions):
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
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
167 unsigned int csingles, cranges, cequivalents;
168 boost::uint_fast32_t cclasses;
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
178 unsigned char _map[256];
181 /*** struct re_jump ***************************************************
182 Jump to a new location in the machine (not next).
183 ***********************************************************************/
184 struct re_jump : public re_syntax_base
186 offset_type alt; // location to jump to
187 unsigned char _map[256]; // which characters can take the jump
190 /*** struct re_repeat *************************************************
191 Repeat a section of the machine
192 ***********************************************************************/
193 struct re_repeat : public re_jump
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
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
208 re_jump_size = (sizeof(re_jump) + padding_mask) & ~(padding_mask),
209 re_repeater_size = (sizeof(re_repeat) + padding_mask) & ~(padding_mask)
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,
218 const re_set_long* set_,
219 const reg_expression<charT, traits_type, Allocator>& e);
221 } // namespace re_detail
225 #ifdef BOOST_HAS_ABI_HEADERS
226 # include BOOST_ABI_SUFFIX