]>
Commit | Line | Data |
---|---|---|
3b0bdc72 | 1 | /* Extended regular expression matching and search library. |
550aafb9 | 2 | Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
3b0bdc72 UD |
3 | This file is part of the GNU C Library. |
4 | Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>. | |
5 | ||
6 | The GNU C Library is free software; you can redistribute it and/or | |
7 | modify it under the terms of the GNU Lesser General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2.1 of the License, or (at your option) any later version. | |
10 | ||
11 | The GNU C Library is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Lesser General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU Lesser General Public | |
17 | License along with the GNU C Library; if not, write to the Free | |
18 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA | |
19 | 02111-1307 USA. */ | |
20 | ||
21 | #ifndef _REGEX_INTERNAL_H | |
22 | #define _REGEX_INTERNAL_H 1 | |
23 | ||
54e1cabc UD |
24 | #include <assert.h> |
25 | #include <ctype.h> | |
54e1cabc UD |
26 | #include <stdio.h> |
27 | #include <stdlib.h> | |
28 | #include <string.h> | |
29 | ||
e40a38b3 UD |
30 | #if defined HAVE_LANGINFO_H || defined HAVE_LANGINFO_CODESET || defined _LIBC |
31 | # include <langinfo.h> | |
32 | #endif | |
54e1cabc UD |
33 | #if defined HAVE_LOCALE_H || defined _LIBC |
34 | # include <locale.h> | |
35 | #endif | |
36 | #if defined HAVE_WCHAR_H || defined _LIBC | |
37 | # include <wchar.h> | |
38 | #endif /* HAVE_WCHAR_H || _LIBC */ | |
39 | #if defined HAVE_WCTYPE_H || defined _LIBC | |
40 | # include <wctype.h> | |
41 | #endif /* HAVE_WCTYPE_H || _LIBC */ | |
e699dda3 UD |
42 | #if defined _LIBC |
43 | # include <bits/libc-lock.h> | |
44 | #else | |
45 | # define __libc_lock_define(CLASS,NAME) | |
46 | # define __libc_lock_init(NAME) do { } while (0) | |
47 | # define __libc_lock_lock(NAME) do { } while (0) | |
48 | # define __libc_lock_unlock(NAME) do { } while (0) | |
49 | #endif | |
54e1cabc UD |
50 | |
51 | /* In case that the system doesn't have isblank(). */ | |
52 | #if !defined _LIBC && !defined HAVE_ISBLANK && !defined isblank | |
53 | # define isblank(ch) ((ch) == ' ' || (ch) == '\t') | |
54 | #endif | |
55 | ||
56 | #ifdef _LIBC | |
57 | # ifndef _RE_DEFINE_LOCALE_FUNCTIONS | |
58 | # define _RE_DEFINE_LOCALE_FUNCTIONS 1 | |
59 | # include <locale/localeinfo.h> | |
60 | # include <locale/elem-hash.h> | |
61 | # include <locale/coll-lookup.h> | |
62 | # endif | |
63 | #endif | |
64 | ||
65 | /* This is for other GNU distributions with internationalized messages. */ | |
df759c2a | 66 | #if (HAVE_LIBINTL_H && ENABLE_NLS) || defined _LIBC |
54e1cabc UD |
67 | # include <libintl.h> |
68 | # ifdef _LIBC | |
69 | # undef gettext | |
70 | # define gettext(msgid) \ | |
9cfe5381 | 71 | INTUSE(__dcgettext) (_libc_intl_domainname, msgid, LC_MESSAGES) |
54e1cabc UD |
72 | # endif |
73 | #else | |
74 | # define gettext(msgid) (msgid) | |
75 | #endif | |
76 | ||
77 | #ifndef gettext_noop | |
78 | /* This define is so xgettext can find the internationalizable | |
79 | strings. */ | |
80 | # define gettext_noop(String) String | |
81 | #endif | |
82 | ||
5a6bbb41 UD |
83 | #if (defined MB_CUR_MAX && HAVE_LOCALE_H && HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_WCRTOMB && HAVE_MBRTOWC && HAVE_WCSCOLL) || _LIBC |
84 | # define RE_ENABLE_I18N | |
54e1cabc UD |
85 | #endif |
86 | ||
87 | #if __GNUC__ >= 3 | |
88 | # define BE(expr, val) __builtin_expect (expr, val) | |
89 | #else | |
90 | # define BE(expr, val) (expr) | |
91 | # define inline | |
92 | #endif | |
93 | ||
a334319f UD |
94 | /* Number of bits in a byte. */ |
95 | #define BYTE_BITS 8 | |
3b0bdc72 UD |
96 | /* Number of single byte character. */ |
97 | #define SBC_MAX 256 | |
98 | ||
99 | #define COLL_ELEM_LEN_MAX 8 | |
100 | ||
101 | /* The character which represents newline. */ | |
102 | #define NEWLINE_CHAR '\n' | |
1843975c | 103 | #define WIDE_NEWLINE_CHAR L'\n' |
3b0bdc72 UD |
104 | |
105 | /* Rename to standard API for using out of glibc. */ | |
106 | #ifndef _LIBC | |
107 | # define __wctype wctype | |
108 | # define __iswctype iswctype | |
109 | # define __btowc btowc | |
54e1cabc UD |
110 | # define __mempcpy mempcpy |
111 | # define __wcrtomb wcrtomb | |
27bbfab0 | 112 | # define __regfree regfree |
434d3784 UD |
113 | # define attribute_hidden |
114 | #endif /* not _LIBC */ | |
3b0bdc72 | 115 | |
ce859332 | 116 | #ifdef __GNUC__ |
93226feb | 117 | # define __attribute(arg) __attribute__ (arg) |
ce859332 | 118 | #else |
93226feb | 119 | # define __attribute(arg) |
ce859332 UD |
120 | #endif |
121 | ||
6455d255 UD |
122 | extern const char __re_error_msgid[] attribute_hidden; |
123 | extern const size_t __re_error_msgid_idx[] attribute_hidden; | |
3b0bdc72 | 124 | |
a334319f UD |
125 | /* Number of bits in an unsinged int. */ |
126 | #define UINT_BITS (sizeof (unsigned int) * BYTE_BITS) | |
127 | /* Number of unsigned int in an bit_set. */ | |
128 | #define BITSET_UINTS ((SBC_MAX + UINT_BITS - 1) / UINT_BITS) | |
129 | typedef unsigned int bitset[BITSET_UINTS]; | |
130 | typedef unsigned int *re_bitset_ptr_t; | |
131 | typedef const unsigned int *re_const_bitset_ptr_t; | |
132 | ||
133 | #define bitset_set(set,i) (set[i / UINT_BITS] |= 1 << i % UINT_BITS) | |
134 | #define bitset_clear(set,i) (set[i / UINT_BITS] &= ~(1 << i % UINT_BITS)) | |
135 | #define bitset_contain(set,i) (set[i / UINT_BITS] & (1 << i % UINT_BITS)) | |
136 | #define bitset_empty(set) memset (set, 0, sizeof (unsigned int) * BITSET_UINTS) | |
137 | #define bitset_set_all(set) \ | |
138 | memset (set, 255, sizeof (unsigned int) * BITSET_UINTS) | |
139 | #define bitset_copy(dest,src) \ | |
140 | memcpy (dest, src, sizeof (unsigned int) * BITSET_UINTS) | |
141 | static inline void bitset_not (bitset set); | |
142 | static inline void bitset_merge (bitset dest, const bitset src); | |
143 | static inline void bitset_not_merge (bitset dest, const bitset src); | |
144 | static inline void bitset_mask (bitset dest, const bitset src); | |
3b0bdc72 UD |
145 | |
146 | #define PREV_WORD_CONSTRAINT 0x0001 | |
147 | #define PREV_NOTWORD_CONSTRAINT 0x0002 | |
148 | #define NEXT_WORD_CONSTRAINT 0x0004 | |
149 | #define NEXT_NOTWORD_CONSTRAINT 0x0008 | |
150 | #define PREV_NEWLINE_CONSTRAINT 0x0010 | |
151 | #define NEXT_NEWLINE_CONSTRAINT 0x0020 | |
152 | #define PREV_BEGBUF_CONSTRAINT 0x0040 | |
153 | #define NEXT_ENDBUF_CONSTRAINT 0x0080 | |
550aafb9 UD |
154 | #define WORD_DELIM_CONSTRAINT 0x0100 |
155 | #define NOT_WORD_DELIM_CONSTRAINT 0x0200 | |
3b0bdc72 UD |
156 | |
157 | typedef enum | |
158 | { | |
159 | INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT, | |
160 | WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT, | |
161 | WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT, | |
550aafb9 | 162 | INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT, |
3b0bdc72 UD |
163 | LINE_FIRST = PREV_NEWLINE_CONSTRAINT, |
164 | LINE_LAST = NEXT_NEWLINE_CONSTRAINT, | |
165 | BUF_FIRST = PREV_BEGBUF_CONSTRAINT, | |
166 | BUF_LAST = NEXT_ENDBUF_CONSTRAINT, | |
550aafb9 UD |
167 | WORD_DELIM = WORD_DELIM_CONSTRAINT, |
168 | NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT | |
3b0bdc72 UD |
169 | } re_context_type; |
170 | ||
171 | typedef struct | |
172 | { | |
173 | int alloc; | |
174 | int nelem; | |
175 | int *elems; | |
176 | } re_node_set; | |
177 | ||
178 | typedef enum | |
179 | { | |
180 | NON_TYPE = 0, | |
181 | ||
ad7f28c2 UD |
182 | /* Node type, These are used by token, node, tree. */ |
183 | CHARACTER = 1, | |
184 | END_OF_RE = 2, | |
185 | SIMPLE_BRACKET = 3, | |
186 | OP_BACK_REF = 4, | |
187 | OP_PERIOD = 5, | |
188 | #ifdef RE_ENABLE_I18N | |
189 | COMPLEX_BRACKET = 6, | |
190 | OP_UTF8_PERIOD = 7, | |
191 | #endif /* RE_ENABLE_I18N */ | |
192 | ||
fe9434bb UD |
193 | /* We define EPSILON_BIT as a macro so that OP_OPEN_SUBEXP is used |
194 | when the debugger shows values of this enum type. */ | |
195 | #define EPSILON_BIT 8 | |
ad7f28c2 UD |
196 | OP_OPEN_SUBEXP = EPSILON_BIT | 0, |
197 | OP_CLOSE_SUBEXP = EPSILON_BIT | 1, | |
198 | OP_ALT = EPSILON_BIT | 2, | |
199 | OP_DUP_ASTERISK = EPSILON_BIT | 3, | |
02f3550c | 200 | ANCHOR = EPSILON_BIT | 4, |
ad7f28c2 UD |
201 | |
202 | /* Tree type, these are used only by tree. */ | |
203 | CONCAT = 16, | |
02f3550c | 204 | SUBEXP = 17, |
ad7f28c2 | 205 | |
3b0bdc72 | 206 | /* Token type, these are used only by token. */ |
02f3550c UD |
207 | OP_DUP_PLUS = 18, |
208 | OP_DUP_QUESTION, | |
209 | OP_OPEN_BRACKET, | |
3b0bdc72 UD |
210 | OP_CLOSE_BRACKET, |
211 | OP_CHARSET_RANGE, | |
212 | OP_OPEN_DUP_NUM, | |
213 | OP_CLOSE_DUP_NUM, | |
214 | OP_NON_MATCH_LIST, | |
215 | OP_OPEN_COLL_ELEM, | |
216 | OP_CLOSE_COLL_ELEM, | |
217 | OP_OPEN_EQUIV_CLASS, | |
218 | OP_CLOSE_EQUIV_CLASS, | |
219 | OP_OPEN_CHAR_CLASS, | |
220 | OP_CLOSE_CHAR_CLASS, | |
221 | OP_WORD, | |
222 | OP_NOTWORD, | |
e2b6bfa3 UD |
223 | OP_SPACE, |
224 | OP_NOTSPACE, | |
ad7f28c2 | 225 | BACK_SLASH |
3b0bdc72 | 226 | |
3b0bdc72 UD |
227 | } re_token_type_t; |
228 | ||
c0a0f9a3 | 229 | #ifdef RE_ENABLE_I18N |
3b0bdc72 UD |
230 | typedef struct |
231 | { | |
3b0bdc72 UD |
232 | /* Multibyte characters. */ |
233 | wchar_t *mbchars; | |
3b0bdc72 UD |
234 | |
235 | /* Collating symbols. */ | |
c0a0f9a3 | 236 | # ifdef _LIBC |
3b0bdc72 | 237 | int32_t *coll_syms; |
c0a0f9a3 | 238 | # endif |
3b0bdc72 UD |
239 | |
240 | /* Equivalence classes. */ | |
c0a0f9a3 | 241 | # ifdef _LIBC |
3b0bdc72 | 242 | int32_t *equiv_classes; |
c0a0f9a3 | 243 | # endif |
3b0bdc72 UD |
244 | |
245 | /* Range expressions. */ | |
c0a0f9a3 | 246 | # ifdef _LIBC |
3b0bdc72 UD |
247 | uint32_t *range_starts; |
248 | uint32_t *range_ends; | |
c0a0f9a3 | 249 | # else /* not _LIBC */ |
434d3784 UD |
250 | wchar_t *range_starts; |
251 | wchar_t *range_ends; | |
c0a0f9a3 | 252 | # endif /* not _LIBC */ |
3b0bdc72 UD |
253 | |
254 | /* Character classes. */ | |
255 | wctype_t *char_classes; | |
81c64d40 UD |
256 | |
257 | /* If this character set is the non-matching list. */ | |
258 | unsigned int non_match : 1; | |
259 | ||
260 | /* # of multibyte characters. */ | |
261 | int nmbchars; | |
262 | ||
263 | /* # of collating symbols. */ | |
264 | int ncoll_syms; | |
265 | ||
266 | /* # of equivalence classes. */ | |
267 | int nequiv_classes; | |
268 | ||
269 | /* # of range expressions. */ | |
270 | int nranges; | |
271 | ||
272 | /* # of character classes. */ | |
3b0bdc72 UD |
273 | int nchar_classes; |
274 | } re_charset_t; | |
c0a0f9a3 | 275 | #endif /* RE_ENABLE_I18N */ |
3b0bdc72 UD |
276 | |
277 | typedef struct | |
278 | { | |
3b0bdc72 UD |
279 | union |
280 | { | |
281 | unsigned char c; /* for CHARACTER */ | |
282 | re_bitset_ptr_t sbcset; /* for SIMPLE_BRACKET */ | |
c0a0f9a3 | 283 | #ifdef RE_ENABLE_I18N |
3b0bdc72 | 284 | re_charset_t *mbcset; /* for COMPLEX_BRACKET */ |
c0a0f9a3 | 285 | #endif /* RE_ENABLE_I18N */ |
3b0bdc72 UD |
286 | int idx; /* for BACK_REF */ |
287 | re_context_type ctx_type; /* for ANCHOR */ | |
3b0bdc72 | 288 | } opr; |
81c64d40 UD |
289 | #if __GNUC__ >= 2 |
290 | re_token_type_t type : 8; | |
291 | #else | |
292 | re_token_type_t type; | |
293 | #endif | |
3b0bdc72 UD |
294 | unsigned int constraint : 10; /* context constraint */ |
295 | unsigned int duplicated : 1; | |
6b6557e8 | 296 | unsigned int opt_subexp : 1; |
3b0bdc72 | 297 | #ifdef RE_ENABLE_I18N |
02f3550c | 298 | unsigned int accept_mb : 1; |
65e6becf UD |
299 | /* These 2 bits can be moved into the union if needed (e.g. if running out |
300 | of bits; move opr.c to opr.c.c and move the flags to opr.c.flags). */ | |
3b0bdc72 UD |
301 | unsigned int mb_partial : 1; |
302 | #endif | |
65e6becf | 303 | unsigned int word_char : 1; |
3b0bdc72 UD |
304 | } re_token_t; |
305 | ||
ad7f28c2 | 306 | #define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT) |
3b0bdc72 UD |
307 | |
308 | struct re_string_t | |
309 | { | |
612546c6 UD |
310 | /* Indicate the raw buffer which is the original string passed as an |
311 | argument of regexec(), re_search(), etc.. */ | |
c202c2c5 | 312 | const unsigned char *raw_mbs; |
3b0bdc72 | 313 | /* Store the multibyte string. In case of "case insensitive mode" like |
612546c6 UD |
314 | REG_ICASE, upper cases of the string are stored, otherwise MBS points |
315 | the same address that RAW_MBS points. */ | |
c202c2c5 | 316 | unsigned char *mbs; |
3b0bdc72 UD |
317 | #ifdef RE_ENABLE_I18N |
318 | /* Store the wide character string which is corresponding to MBS. */ | |
c0a0f9a3 | 319 | wint_t *wcs; |
bb3f4825 | 320 | int *offsets; |
612546c6 | 321 | mbstate_t cur_state; |
3b0bdc72 | 322 | #endif |
81c64d40 UD |
323 | /* Index in RAW_MBS. Each character mbs[i] corresponds to |
324 | raw_mbs[raw_mbs_idx + i]. */ | |
325 | int raw_mbs_idx; | |
612546c6 UD |
326 | /* The length of the valid characters in the buffers. */ |
327 | int valid_len; | |
bb3f4825 UD |
328 | /* The corresponding number of bytes in raw_mbs array. */ |
329 | int valid_raw_len; | |
330 | /* The length of the buffers MBS and WCS. */ | |
612546c6 UD |
331 | int bufs_len; |
332 | /* The index in MBS, which is updated by re_string_fetch_byte. */ | |
333 | int cur_idx; | |
bb3f4825 UD |
334 | /* length of RAW_MBS array. */ |
335 | int raw_len; | |
336 | /* This is RAW_LEN - RAW_MBS_IDX + VALID_LEN - VALID_RAW_LEN. */ | |
612546c6 | 337 | int len; |
ac3d553b UD |
338 | /* End of the buffer may be shorter than its length in the cases such |
339 | as re_match_2, re_search_2. Then, we use STOP for end of the buffer | |
340 | instead of LEN. */ | |
bb3f4825 UD |
341 | int raw_stop; |
342 | /* This is RAW_STOP - RAW_MBS_IDX adjusted through OFFSETS. */ | |
ac3d553b UD |
343 | int stop; |
344 | ||
612546c6 UD |
345 | /* The context of mbs[0]. We store the context independently, since |
346 | the context of mbs[0] may be different from raw_mbs[0], which is | |
347 | the beginning of the input string. */ | |
348 | unsigned int tip_context; | |
349 | /* The translation passed as a part of an argument of re_compile_pattern. */ | |
a334319f | 350 | unsigned RE_TRANSLATE_TYPE trans; |
56b168be UD |
351 | /* Copy of re_dfa_t's word_char. */ |
352 | re_const_bitset_ptr_t word_char; | |
612546c6 | 353 | /* 1 if REG_ICASE. */ |
bb3f4825 UD |
354 | unsigned char icase; |
355 | unsigned char is_utf8; | |
356 | unsigned char map_notascii; | |
357 | unsigned char mbs_allocated; | |
358 | unsigned char offsets_needed; | |
56b168be UD |
359 | unsigned char newline_anchor; |
360 | unsigned char word_ops_used; | |
3c0fb574 | 361 | int mb_cur_max; |
3b0bdc72 UD |
362 | }; |
363 | typedef struct re_string_t re_string_t; | |
612546c6 | 364 | |
3b0bdc72 | 365 | |
f0c7c524 UD |
366 | struct re_dfa_t; |
367 | typedef struct re_dfa_t re_dfa_t; | |
8cae99db UD |
368 | |
369 | #ifndef _LIBC | |
370 | # ifdef __i386__ | |
371 | # define internal_function __attribute ((regparm (3), stdcall)) | |
372 | # else | |
373 | # define internal_function | |
374 | # endif | |
375 | #endif | |
376 | ||
a334319f UD |
377 | #ifndef RE_NO_INTERNAL_PROTOTYPES |
378 | static reg_errcode_t re_string_allocate (re_string_t *pstr, const char *str, | |
379 | int len, int init_len, | |
380 | RE_TRANSLATE_TYPE trans, int icase, | |
381 | const re_dfa_t *dfa) | |
382 | internal_function; | |
383 | static reg_errcode_t re_string_construct (re_string_t *pstr, const char *str, | |
384 | int len, RE_TRANSLATE_TYPE trans, | |
385 | int icase, const re_dfa_t *dfa) | |
386 | internal_function; | |
387 | static reg_errcode_t re_string_reconstruct (re_string_t *pstr, int idx, | |
388 | int eflags) internal_function; | |
612546c6 | 389 | static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr, |
56b168be UD |
390 | int new_buf_len) |
391 | internal_function; | |
a334319f | 392 | # ifdef RE_ENABLE_I18N |
8cae99db UD |
393 | static void build_wcs_buffer (re_string_t *pstr) internal_function; |
394 | static int build_wcs_upper_buffer (re_string_t *pstr) internal_function; | |
a334319f | 395 | # endif /* RE_ENABLE_I18N */ |
8cae99db UD |
396 | static void build_upper_buffer (re_string_t *pstr) internal_function; |
397 | static void re_string_translate_buffer (re_string_t *pstr) internal_function; | |
a334319f UD |
398 | static void re_string_destruct (re_string_t *pstr) internal_function; |
399 | # ifdef RE_ENABLE_I18N | |
400 | static int re_string_elem_size_at (const re_string_t *pstr, int idx) | |
401 | internal_function __attribute ((pure)); | |
402 | static inline int re_string_char_size_at (const re_string_t *pstr, int idx) | |
403 | internal_function __attribute ((pure)); | |
404 | static inline wint_t re_string_wchar_at (const re_string_t *pstr, int idx) | |
405 | internal_function __attribute ((pure)); | |
406 | # endif /* RE_ENABLE_I18N */ | |
3b0bdc72 | 407 | static unsigned int re_string_context_at (const re_string_t *input, int idx, |
5cf1ec52 UD |
408 | int eflags) |
409 | internal_function __attribute ((pure)); | |
a334319f UD |
410 | static unsigned char re_string_peek_byte_case (const re_string_t *pstr, |
411 | int idx) | |
412 | internal_function __attribute ((pure)); | |
413 | static unsigned char re_string_fetch_byte_case (re_string_t *pstr) | |
414 | internal_function __attribute ((pure)); | |
415 | #endif | |
3b0bdc72 UD |
416 | #define re_string_peek_byte(pstr, offset) \ |
417 | ((pstr)->mbs[(pstr)->cur_idx + offset]) | |
3b0bdc72 UD |
418 | #define re_string_fetch_byte(pstr) \ |
419 | ((pstr)->mbs[(pstr)->cur_idx++]) | |
3b0bdc72 | 420 | #define re_string_first_byte(pstr, idx) \ |
ebcf449f | 421 | ((idx) == (pstr)->valid_len || (pstr)->wcs[idx] != WEOF) |
3b0bdc72 | 422 | #define re_string_is_single_byte_char(pstr, idx) \ |
294b6bcc | 423 | ((pstr)->wcs[idx] != WEOF && ((pstr)->valid_len == (idx) + 1 \ |
15a7d175 | 424 | || (pstr)->wcs[(idx) + 1] != WEOF)) |
ac3d553b | 425 | #define re_string_eoi(pstr) ((pstr)->stop <= (pstr)->cur_idx) |
3b0bdc72 UD |
426 | #define re_string_cur_idx(pstr) ((pstr)->cur_idx) |
427 | #define re_string_get_buffer(pstr) ((pstr)->mbs) | |
428 | #define re_string_length(pstr) ((pstr)->len) | |
612546c6 | 429 | #define re_string_byte_at(pstr,idx) ((pstr)->mbs[idx]) |
3b0bdc72 UD |
430 | #define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx)) |
431 | #define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx)) | |
432 | ||
433 | #define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t))) | |
434 | #define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t))) | |
435 | #define re_free(p) free (p) | |
436 | ||
437 | struct bin_tree_t | |
438 | { | |
439 | struct bin_tree_t *parent; | |
440 | struct bin_tree_t *left; | |
441 | struct bin_tree_t *right; | |
02f3550c UD |
442 | struct bin_tree_t *first; |
443 | struct bin_tree_t *next; | |
444 | ||
445 | re_token_t token; | |
3b0bdc72 UD |
446 | |
447 | /* `node_idx' is the index in dfa->nodes, if `type' == 0. | |
448 | Otherwise `type' indicate the type of this node. */ | |
3b0bdc72 | 449 | int node_idx; |
3b0bdc72 UD |
450 | }; |
451 | typedef struct bin_tree_t bin_tree_t; | |
452 | ||
ee70274a UD |
453 | #define BIN_TREE_STORAGE_SIZE \ |
454 | ((1024 - sizeof (void *)) / sizeof (bin_tree_t)) | |
455 | ||
456 | struct bin_tree_storage_t | |
457 | { | |
458 | struct bin_tree_storage_t *next; | |
459 | bin_tree_t data[BIN_TREE_STORAGE_SIZE]; | |
460 | }; | |
461 | typedef struct bin_tree_storage_t bin_tree_storage_t; | |
3b0bdc72 UD |
462 | |
463 | #define CONTEXT_WORD 1 | |
464 | #define CONTEXT_NEWLINE (CONTEXT_WORD << 1) | |
465 | #define CONTEXT_BEGBUF (CONTEXT_NEWLINE << 1) | |
466 | #define CONTEXT_ENDBUF (CONTEXT_BEGBUF << 1) | |
467 | ||
468 | #define IS_WORD_CONTEXT(c) ((c) & CONTEXT_WORD) | |
469 | #define IS_NEWLINE_CONTEXT(c) ((c) & CONTEXT_NEWLINE) | |
470 | #define IS_BEGBUF_CONTEXT(c) ((c) & CONTEXT_BEGBUF) | |
471 | #define IS_ENDBUF_CONTEXT(c) ((c) & CONTEXT_ENDBUF) | |
472 | #define IS_ORDINARY_CONTEXT(c) ((c) == 0) | |
473 | ||
474 | #define IS_WORD_CHAR(ch) (isalnum (ch) || (ch) == '_') | |
475 | #define IS_NEWLINE(ch) ((ch) == NEWLINE_CHAR) | |
1843975c RM |
476 | #define IS_WIDE_WORD_CHAR(ch) (iswalnum (ch) || (ch) == L'_') |
477 | #define IS_WIDE_NEWLINE(ch) ((ch) == WIDE_NEWLINE_CHAR) | |
3b0bdc72 UD |
478 | |
479 | #define NOT_SATISFY_PREV_CONSTRAINT(constraint,context) \ | |
480 | ((((constraint) & PREV_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \ | |
481 | || ((constraint & PREV_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \ | |
482 | || ((constraint & PREV_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context))\ | |
483 | || ((constraint & PREV_BEGBUF_CONSTRAINT) && !IS_BEGBUF_CONTEXT (context))) | |
484 | ||
485 | #define NOT_SATISFY_NEXT_CONSTRAINT(constraint,context) \ | |
486 | ((((constraint) & NEXT_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \ | |
487 | || (((constraint) & NEXT_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \ | |
488 | || (((constraint) & NEXT_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context)) \ | |
489 | || (((constraint) & NEXT_ENDBUF_CONSTRAINT) && !IS_ENDBUF_CONTEXT (context))) | |
490 | ||
491 | struct re_dfastate_t | |
492 | { | |
493 | unsigned int hash; | |
494 | re_node_set nodes; | |
5cf1ec52 UD |
495 | re_node_set non_eps_nodes; |
496 | re_node_set inveclosure; | |
3b0bdc72 | 497 | re_node_set *entrance_nodes; |
ab4b89fe | 498 | struct re_dfastate_t **trtable, **word_trtable; |
56b168be | 499 | unsigned int context : 4; |
3b0bdc72 UD |
500 | unsigned int halt : 1; |
501 | /* If this state can accept `multi byte'. | |
502 | Note that we refer to multibyte characters, and multi character | |
503 | collating elements as `multi byte'. */ | |
504 | unsigned int accept_mb : 1; | |
505 | /* If this state has backreference node(s). */ | |
506 | unsigned int has_backref : 1; | |
507 | unsigned int has_constraint : 1; | |
508 | }; | |
509 | typedef struct re_dfastate_t re_dfastate_t; | |
510 | ||
3b0bdc72 UD |
511 | struct re_state_table_entry |
512 | { | |
513 | int num; | |
514 | int alloc; | |
bc15410e | 515 | re_dfastate_t **array; |
3b0bdc72 UD |
516 | }; |
517 | ||
6291ee3c UD |
518 | /* Array type used in re_sub_match_last_t and re_sub_match_top_t. */ |
519 | ||
520 | typedef struct | |
521 | { | |
522 | int next_idx; | |
523 | int alloc; | |
524 | re_dfastate_t **array; | |
525 | } state_array_t; | |
526 | ||
527 | /* Store information about the node NODE whose type is OP_CLOSE_SUBEXP. */ | |
528 | ||
529 | typedef struct | |
530 | { | |
531 | int node; | |
532 | int str_idx; /* The position NODE match at. */ | |
533 | state_array_t path; | |
534 | } re_sub_match_last_t; | |
535 | ||
536 | /* Store information about the node NODE whose type is OP_OPEN_SUBEXP. | |
537 | And information about the node, whose type is OP_CLOSE_SUBEXP, | |
538 | corresponding to NODE is stored in LASTS. */ | |
539 | ||
540 | typedef struct | |
541 | { | |
542 | int str_idx; | |
543 | int node; | |
a334319f | 544 | int next_last_offset; |
6291ee3c UD |
545 | state_array_t *path; |
546 | int alasts; /* Allocation size of LASTS. */ | |
547 | int nlasts; /* The number of LASTS. */ | |
548 | re_sub_match_last_t **lasts; | |
549 | } re_sub_match_top_t; | |
550 | ||
612546c6 UD |
551 | struct re_backref_cache_entry |
552 | { | |
553 | int node; | |
0742e48e UD |
554 | int str_idx; |
555 | int subexp_from; | |
556 | int subexp_to; | |
7db61208 UD |
557 | char more; |
558 | char unused; | |
559 | unsigned short int eps_reachable_subexps_map; | |
612546c6 UD |
560 | }; |
561 | ||
562 | typedef struct | |
563 | { | |
56b168be UD |
564 | /* The string object corresponding to the input string. */ |
565 | re_string_t input; | |
a2fd078a | 566 | #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L) |
a334319f | 567 | re_dfa_t *const dfa; |
a2fd078a | 568 | #else |
a334319f | 569 | re_dfa_t *dfa; |
a2fd078a | 570 | #endif |
612546c6 UD |
571 | /* EFLAGS of the argument of regexec. */ |
572 | int eflags; | |
573 | /* Where the matching ends. */ | |
574 | int match_last; | |
a3022b82 | 575 | int last_node; |
612546c6 UD |
576 | /* The state log used by the matcher. */ |
577 | re_dfastate_t **state_log; | |
578 | int state_log_top; | |
579 | /* Back reference cache. */ | |
580 | int nbkref_ents; | |
581 | int abkref_ents; | |
582 | struct re_backref_cache_entry *bkref_ents; | |
0742e48e | 583 | int max_mb_elem_len; |
6291ee3c UD |
584 | int nsub_tops; |
585 | int asub_tops; | |
586 | re_sub_match_top_t **sub_tops; | |
612546c6 UD |
587 | } re_match_context_t; |
588 | ||
0742e48e UD |
589 | typedef struct |
590 | { | |
0742e48e UD |
591 | re_dfastate_t **sifted_states; |
592 | re_dfastate_t **limited_states; | |
0742e48e UD |
593 | int last_node; |
594 | int last_str_idx; | |
a705c0d8 | 595 | re_node_set limits; |
0742e48e UD |
596 | } re_sift_context_t; |
597 | ||
a3022b82 UD |
598 | struct re_fail_stack_ent_t |
599 | { | |
600 | int idx; | |
601 | int node; | |
602 | regmatch_t *regs; | |
603 | re_node_set eps_via_nodes; | |
604 | }; | |
605 | ||
606 | struct re_fail_stack_t | |
607 | { | |
608 | int num; | |
609 | int alloc; | |
610 | struct re_fail_stack_ent_t *stack; | |
611 | }; | |
612 | ||
3b0bdc72 UD |
613 | struct re_dfa_t |
614 | { | |
3b0bdc72 | 615 | re_token_t *nodes; |
a334319f UD |
616 | int nodes_alloc; |
617 | int nodes_len; | |
3b0bdc72 | 618 | int *nexts; |
a7d5c291 | 619 | int *org_indices; |
3b0bdc72 UD |
620 | re_node_set *edests; |
621 | re_node_set *eclosures; | |
622 | re_node_set *inveclosures; | |
623 | struct re_state_table_entry *state_table; | |
3b0bdc72 UD |
624 | re_dfastate_t *init_state; |
625 | re_dfastate_t *init_state_word; | |
626 | re_dfastate_t *init_state_nl; | |
627 | re_dfastate_t *init_state_begbuf; | |
ee70274a UD |
628 | bin_tree_t *str_tree; |
629 | bin_tree_storage_t *str_tree_storage; | |
65e6becf | 630 | re_bitset_ptr_t sb_char; |
ee70274a | 631 | int str_tree_storage_idx; |
3c0fb574 UD |
632 | |
633 | /* number of subexpressions `re_nsub' is in regex_t. */ | |
3c0fb574 | 634 | unsigned int state_hash_mask; |
a334319f | 635 | int states_alloc; |
3b0bdc72 UD |
636 | int init_node; |
637 | int nbackref; /* The number of backreference in this dfa. */ | |
d8f73de8 | 638 | |
6291ee3c | 639 | /* Bitmap expressing which backreference is used. */ |
a334319f UD |
640 | unsigned int used_bkref_map; |
641 | unsigned int completed_bkref_map; | |
d8f73de8 | 642 | |
0742e48e | 643 | unsigned int has_plural_match : 1; |
6291ee3c UD |
644 | /* If this dfa has "multibyte node", which is a backreference or |
645 | a node which can accept multibyte character or multi character | |
646 | collating element. */ | |
3b0bdc72 | 647 | unsigned int has_mb_node : 1; |
3c0fb574 | 648 | unsigned int is_utf8 : 1; |
f0c7c524 | 649 | unsigned int map_notascii : 1; |
56b168be | 650 | unsigned int word_ops_used : 1; |
3c0fb574 | 651 | int mb_cur_max; |
a334319f | 652 | bitset word_char; |
56b168be | 653 | reg_syntax_t syntax; |
c06a6956 | 654 | int *subexp_map; |
ee70274a UD |
655 | #ifdef DEBUG |
656 | char* re_str; | |
657 | #endif | |
e699dda3 | 658 | __libc_lock_define (, lock) |
3b0bdc72 | 659 | }; |
3b0bdc72 | 660 | |
a334319f UD |
661 | #ifndef RE_NO_INTERNAL_PROTOTYPES |
662 | static reg_errcode_t re_node_set_alloc (re_node_set *set, int size) internal_function; | |
663 | static reg_errcode_t re_node_set_init_1 (re_node_set *set, int elem) internal_function; | |
664 | static reg_errcode_t re_node_set_init_2 (re_node_set *set, int elem1, | |
665 | int elem2) internal_function; | |
3b0bdc72 | 666 | #define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set)) |
a334319f UD |
667 | static reg_errcode_t re_node_set_init_copy (re_node_set *dest, |
668 | const re_node_set *src) internal_function; | |
669 | static reg_errcode_t re_node_set_add_intersect (re_node_set *dest, | |
670 | const re_node_set *src1, | |
671 | const re_node_set *src2) internal_function; | |
672 | static reg_errcode_t re_node_set_init_union (re_node_set *dest, | |
673 | const re_node_set *src1, | |
674 | const re_node_set *src2) internal_function; | |
675 | static reg_errcode_t re_node_set_merge (re_node_set *dest, | |
676 | const re_node_set *src) internal_function; | |
677 | static int re_node_set_insert (re_node_set *set, int elem) internal_function; | |
678 | static int re_node_set_insert_last (re_node_set *set, | |
679 | int elem) internal_function; | |
680 | static int re_node_set_compare (const re_node_set *set1, | |
681 | const re_node_set *set2) | |
682 | internal_function __attribute ((pure)); | |
683 | static int re_node_set_contains (const re_node_set *set, int elem) | |
684 | internal_function __attribute ((pure)); | |
685 | static void re_node_set_remove_at (re_node_set *set, int idx) internal_function; | |
485d775d UD |
686 | #define re_node_set_remove(set,id) \ |
687 | (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1)) | |
3b0bdc72 UD |
688 | #define re_node_set_empty(p) ((p)->nelem = 0) |
689 | #define re_node_set_free(set) re_free ((set)->elems) | |
02f3550c | 690 | static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token) internal_function; |
a334319f UD |
691 | static re_dfastate_t *re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, |
692 | const re_node_set *nodes) internal_function; | |
693 | static re_dfastate_t *re_acquire_state_context (reg_errcode_t *err, | |
694 | re_dfa_t *dfa, | |
695 | const re_node_set *nodes, | |
696 | unsigned int context) internal_function; | |
697 | static void free_state (re_dfastate_t *state) internal_function; | |
698 | #endif | |
3b0bdc72 UD |
699 | \f |
700 | ||
701 | typedef enum | |
702 | { | |
703 | SB_CHAR, | |
704 | MB_CHAR, | |
705 | EQUIV_CLASS, | |
706 | COLL_SYM, | |
707 | CHAR_CLASS | |
708 | } bracket_elem_type; | |
709 | ||
710 | typedef struct | |
711 | { | |
712 | bracket_elem_type type; | |
713 | union | |
714 | { | |
715 | unsigned char ch; | |
c202c2c5 | 716 | unsigned char *name; |
3b0bdc72 UD |
717 | wchar_t wch; |
718 | } opr; | |
719 | } bracket_elem_t; | |
720 | ||
721 | ||
722 | /* Inline functions for bitset operation. */ | |
723 | static inline void | |
a334319f | 724 | bitset_not (bitset set) |
3b0bdc72 UD |
725 | { |
726 | int bitset_i; | |
a334319f | 727 | for (bitset_i = 0; bitset_i < BITSET_UINTS; ++bitset_i) |
3b0bdc72 UD |
728 | set[bitset_i] = ~set[bitset_i]; |
729 | } | |
730 | ||
731 | static inline void | |
a334319f | 732 | bitset_merge (bitset dest, const bitset src) |
3b0bdc72 UD |
733 | { |
734 | int bitset_i; | |
a334319f | 735 | for (bitset_i = 0; bitset_i < BITSET_UINTS; ++bitset_i) |
3b0bdc72 UD |
736 | dest[bitset_i] |= src[bitset_i]; |
737 | } | |
738 | ||
739 | static inline void | |
a334319f UD |
740 | bitset_not_merge (bitset dest, const bitset src) |
741 | { | |
742 | int i; | |
743 | for (i = 0; i < BITSET_UINTS; ++i) | |
744 | dest[i] |= ~src[i]; | |
745 | } | |
746 | ||
747 | static inline void | |
748 | bitset_mask (bitset dest, const bitset src) | |
65e6becf UD |
749 | { |
750 | int bitset_i; | |
a334319f | 751 | for (bitset_i = 0; bitset_i < BITSET_UINTS; ++bitset_i) |
65e6becf UD |
752 | dest[bitset_i] &= src[bitset_i]; |
753 | } | |
754 | ||
a334319f | 755 | #if defined RE_ENABLE_I18N && !defined RE_NO_INTERNAL_PROTOTYPES |
3b0bdc72 UD |
756 | /* Inline functions for re_string. */ |
757 | static inline int | |
a334319f | 758 | internal_function |
17568537 | 759 | re_string_char_size_at (const re_string_t *pstr, int idx) |
3b0bdc72 UD |
760 | { |
761 | int byte_idx; | |
3c0fb574 | 762 | if (pstr->mb_cur_max == 1) |
3b0bdc72 | 763 | return 1; |
073a39d6 | 764 | for (byte_idx = 1; idx + byte_idx < pstr->valid_len; ++byte_idx) |
3b0bdc72 UD |
765 | if (pstr->wcs[idx + byte_idx] != WEOF) |
766 | break; | |
767 | return byte_idx; | |
768 | } | |
769 | ||
770 | static inline wint_t | |
a334319f | 771 | internal_function |
17568537 | 772 | re_string_wchar_at (const re_string_t *pstr, int idx) |
3b0bdc72 | 773 | { |
3c0fb574 | 774 | if (pstr->mb_cur_max == 1) |
3b0bdc72 UD |
775 | return (wint_t) pstr->mbs[idx]; |
776 | return (wint_t) pstr->wcs[idx]; | |
777 | } | |
778 | ||
779 | static int | |
a334319f | 780 | internal_function |
17568537 | 781 | re_string_elem_size_at (const re_string_t *pstr, int idx) |
3b0bdc72 | 782 | { |
a334319f | 783 | #ifdef _LIBC |
c202c2c5 | 784 | const unsigned char *p, *extra; |
3b0bdc72 UD |
785 | const int32_t *table, *indirect; |
786 | int32_t tmp; | |
a334319f | 787 | # include <locale/weight.h> |
3b0bdc72 UD |
788 | uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES); |
789 | ||
790 | if (nrules != 0) | |
791 | { | |
792 | table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); | |
c202c2c5 | 793 | extra = (const unsigned char *) |
15a7d175 | 794 | _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); |
3b0bdc72 UD |
795 | indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE, |
796 | _NL_COLLATE_INDIRECTMB); | |
797 | p = pstr->mbs + idx; | |
c202c2c5 | 798 | tmp = findidx (&p); |
92b27c74 | 799 | return p - pstr->mbs - idx; |
3b0bdc72 UD |
800 | } |
801 | else | |
a334319f | 802 | #endif /* _LIBC */ |
3b0bdc72 UD |
803 | return 1; |
804 | } | |
805 | #endif /* RE_ENABLE_I18N */ | |
806 | ||
807 | #endif /* _REGEX_INTERNAL_H */ |