1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
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.
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.
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
21 #ifndef _REGEX_INTERNAL_H
22 #define _REGEX_INTERNAL_H 1
24 /* Number of bits in a byte. */
26 /* Number of single byte character. */
29 #define COLL_ELEM_LEN_MAX 8
31 /* The character which represents newline. */
32 #define NEWLINE_CHAR '\n'
34 /* Rename to standard API for using out of glibc. */
36 # define __wctype wctype
37 # define __iswctype iswctype
38 # define __btowc btowc
39 # define __mempcpy memcpy
40 # define attribute_hidden
41 #endif /* not _LIBC */
43 extern const char __re_error_msgid[] attribute_hidden;
44 extern const size_t __re_error_msgid_idx[] attribute_hidden;
46 /* Number of bits in an unsinged int. */
47 #define UINT_BITS (sizeof (unsigned int) * BYTE_BITS)
48 /* Number of unsigned int in an bit_set. */
49 #define BITSET_UINTS ((SBC_MAX + UINT_BITS - 1) / UINT_BITS)
50 typedef unsigned int bitset[BITSET_UINTS];
51 typedef unsigned int *re_bitset_ptr_t;
53 #define bitset_set(set,i) (set[i / UINT_BITS] |= 1 << i % UINT_BITS)
54 #define bitset_clear(set,i) (set[i / UINT_BITS] &= ~(1 << i % UINT_BITS))
55 #define bitset_contain(set,i) (set[i / UINT_BITS] & (1 << i % UINT_BITS))
56 #define bitset_empty(set) memset (set, 0, sizeof (unsigned int) * BITSET_UINTS)
57 #define bitset_set_all(set) \
58 memset (set, 255, sizeof (unsigned int) * BITSET_UINTS)
59 #define bitset_copy(dest,src) \
60 memcpy (dest, src, sizeof (unsigned int) * BITSET_UINTS)
61 static inline void bitset_not (bitset set);
62 static inline void bitset_merge (bitset dest, const bitset src);
63 static inline void bitset_not_merge (bitset dest, const bitset src);
65 #define PREV_WORD_CONSTRAINT 0x0001
66 #define PREV_NOTWORD_CONSTRAINT 0x0002
67 #define NEXT_WORD_CONSTRAINT 0x0004
68 #define NEXT_NOTWORD_CONSTRAINT 0x0008
69 #define PREV_NEWLINE_CONSTRAINT 0x0010
70 #define NEXT_NEWLINE_CONSTRAINT 0x0020
71 #define PREV_BEGBUF_CONSTRAINT 0x0040
72 #define NEXT_ENDBUF_CONSTRAINT 0x0080
73 #define DUMMY_CONSTRAINT 0x0100
77 INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
78 WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
79 WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
80 LINE_FIRST = PREV_NEWLINE_CONSTRAINT,
81 LINE_LAST = NEXT_NEWLINE_CONSTRAINT,
82 BUF_FIRST = PREV_BEGBUF_CONSTRAINT,
83 BUF_LAST = NEXT_ENDBUF_CONSTRAINT,
84 WORD_DELIM = DUMMY_CONSTRAINT
98 /* Token type, these are used only by token. */
110 OP_CLOSE_EQUIV_CLASS,
117 /* Tree type, these are used only by tree. */
122 #ifdef RE_ENABLE_I18N
124 #endif /* RE_ENABLE_I18N */
126 /* Node type, These are used by token, node, tree. */
142 #ifdef RE_ENABLE_I18N
145 /* If this character set is the non-matching list. */
146 unsigned int non_match : 1;
148 /* Multibyte characters. */
152 /* Collating symbols. */
158 /* Equivalence classes. */
160 int32_t *equiv_classes;
164 /* Range expressions. */
166 uint32_t *range_starts;
167 uint32_t *range_ends;
168 # else /* not _LIBC */
169 wchar_t *range_starts;
171 # endif /* not _LIBC */
174 /* Character classes. */
175 wctype_t *char_classes;
178 #endif /* RE_ENABLE_I18N */
182 re_token_type_t type;
185 unsigned char c; /* for CHARACTER */
186 re_bitset_ptr_t sbcset; /* for SIMPLE_BRACKET */
187 #ifdef RE_ENABLE_I18N
188 re_charset_t *mbcset; /* for COMPLEX_BRACKET */
189 #endif /* RE_ENABLE_I18N */
190 int idx; /* for BACK_REF */
191 re_context_type ctx_type; /* for ANCHOR */
194 int entity; /* for OP_CONTEXT_NODE, index of the entity */
195 re_node_set *bkref_eclosure;
198 unsigned int constraint : 10; /* context constraint */
199 unsigned int duplicated : 1;
200 #ifdef RE_ENABLE_I18N
201 unsigned int mb_partial : 1;
205 #define IS_EPSILON_NODE(type) \
206 ((type) == OP_ALT || (type) == OP_DUP_ASTERISK || (type) == OP_DUP_PLUS || \
207 (type) == OP_DUP_QUESTION || (type) == ANCHOR)
209 #define ACCEPT_MB_NODE(type) \
210 ((type) == COMPLEX_BRACKET || (type) == OP_PERIOD)
214 /* Indicate the raw buffer which is the original string passed as an
215 argument of regexec(), re_search(), etc.. */
216 const unsigned char *raw_mbs;
217 /* Index in RAW_MBS. Each character mbs[i] corresponds to
218 raw_mbs[raw_mbs_idx + i]. */
220 /* Store the multibyte string. In case of "case insensitive mode" like
221 REG_ICASE, upper cases of the string are stored, otherwise MBS points
222 the same address that RAW_MBS points. */
224 /* Store the case sensitive multibyte string. In case of
225 "case insensitive mode", the original string are stored,
226 otherwise MBS_CASE points the same address that MBS points. */
227 unsigned char *mbs_case;
228 #ifdef RE_ENABLE_I18N
229 /* Store the wide character string which is corresponding to MBS. */
233 /* The length of the valid characters in the buffers. */
235 /* The length of the buffers MBS, MBS_CASE, and WCS. */
237 /* The index in MBS, which is updated by re_string_fetch_byte. */
239 /* This is length_of_RAW_MBS - RAW_MBS_IDX. */
241 /* The context of mbs[0]. We store the context independently, since
242 the context of mbs[0] may be different from raw_mbs[0], which is
243 the beginning of the input string. */
244 unsigned int tip_context;
245 /* The translation passed as a part of an argument of re_compile_pattern. */
246 RE_TRANSLATE_TYPE trans;
247 /* 1 if REG_ICASE. */
248 unsigned int icase : 1;
250 typedef struct re_string_t re_string_t;
251 /* In case of REG_ICASE, we allocate the buffer dynamically for mbs. */
252 #define MBS_ALLOCATED(pstr) (pstr->icase)
253 /* In case that we need translation, we allocate the buffer dynamically
254 for mbs_case. Note that mbs == mbs_case if not REG_ICASE. */
255 #define MBS_CASE_ALLOCATED(pstr) (pstr->trans != NULL)
258 static reg_errcode_t re_string_allocate (re_string_t *pstr,
259 const unsigned char *str, int len,
261 RE_TRANSLATE_TYPE trans, int icase);
262 static reg_errcode_t re_string_construct (re_string_t *pstr,
263 const unsigned char *str, int len,
264 RE_TRANSLATE_TYPE trans, int icase);
265 static reg_errcode_t re_string_reconstruct (re_string_t *pstr, int idx,
266 int eflags, int newline);
267 static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr,
269 #ifdef RE_ENABLE_I18N
270 static void build_wcs_buffer (re_string_t *pstr);
271 static void build_wcs_upper_buffer (re_string_t *pstr);
272 #endif /* RE_ENABLE_I18N */
273 static void build_upper_buffer (re_string_t *pstr);
274 static void re_string_translate_buffer (re_string_t *pstr);
275 static void re_string_destruct (re_string_t *pstr);
276 #ifdef RE_ENABLE_I18N
277 static int re_string_elem_size_at (const re_string_t *pstr, int idx);
278 static inline int re_string_char_size_at (const re_string_t *pstr, int idx);
279 static inline wint_t re_string_wchar_at (const re_string_t *pstr, int idx);
280 #endif /* RE_ENABLE_I18N */
281 static unsigned int re_string_context_at (const re_string_t *input, int idx,
282 int eflags, int newline_anchor);
283 #define re_string_peek_byte(pstr, offset) \
284 ((pstr)->mbs[(pstr)->cur_idx + offset])
285 #define re_string_peek_byte_case(pstr, offset) \
286 ((pstr)->mbs_case[(pstr)->cur_idx + offset])
287 #define re_string_fetch_byte(pstr) \
288 ((pstr)->mbs[(pstr)->cur_idx++])
289 #define re_string_fetch_byte_case(pstr) \
290 ((pstr)->mbs_case[(pstr)->cur_idx++])
291 #define re_string_first_byte(pstr, idx) \
292 ((idx) == (pstr)->len || (pstr)->wcs[idx] != WEOF)
293 #define re_string_is_single_byte_char(pstr, idx) \
294 ((pstr)->wcs[idx] != WEOF && ((pstr)->len == (idx) \
295 || (pstr)->wcs[(idx) + 1] != WEOF))
296 #define re_string_eoi(pstr) ((pstr)->len == (pstr)->cur_idx)
297 #define re_string_cur_idx(pstr) ((pstr)->cur_idx)
298 #define re_string_get_buffer(pstr) ((pstr)->mbs)
299 #define re_string_length(pstr) ((pstr)->len)
300 #define re_string_byte_at(pstr,idx) ((pstr)->mbs[idx])
301 #define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
302 #define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
304 #define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t)))
305 #define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t)))
306 #define re_free(p) free (p)
310 struct bin_tree_t *parent;
311 struct bin_tree_t *left;
312 struct bin_tree_t *right;
314 /* `node_idx' is the index in dfa->nodes, if `type' == 0.
315 Otherwise `type' indicate the type of this node. */
316 re_token_type_t type;
321 re_node_set eclosure;
323 typedef struct bin_tree_t bin_tree_t;
326 #define CONTEXT_WORD 1
327 #define CONTEXT_NEWLINE (CONTEXT_WORD << 1)
328 #define CONTEXT_BEGBUF (CONTEXT_NEWLINE << 1)
329 #define CONTEXT_ENDBUF (CONTEXT_BEGBUF << 1)
331 #define IS_WORD_CONTEXT(c) ((c) & CONTEXT_WORD)
332 #define IS_NEWLINE_CONTEXT(c) ((c) & CONTEXT_NEWLINE)
333 #define IS_BEGBUF_CONTEXT(c) ((c) & CONTEXT_BEGBUF)
334 #define IS_ENDBUF_CONTEXT(c) ((c) & CONTEXT_ENDBUF)
335 #define IS_ORDINARY_CONTEXT(c) ((c) == 0)
337 #define IS_WORD_CHAR(ch) (isalnum (ch) || (ch) == '_')
338 #define IS_NEWLINE(ch) ((ch) == NEWLINE_CHAR)
340 #define NOT_SATISFY_PREV_CONSTRAINT(constraint,context) \
341 ((((constraint) & PREV_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
342 || ((constraint & PREV_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
343 || ((constraint & PREV_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context))\
344 || ((constraint & PREV_BEGBUF_CONSTRAINT) && !IS_BEGBUF_CONTEXT (context)))
346 #define NOT_SATISFY_NEXT_CONSTRAINT(constraint,context) \
347 ((((constraint) & NEXT_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
348 || (((constraint) & NEXT_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
349 || (((constraint) & NEXT_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context)) \
350 || (((constraint) & NEXT_ENDBUF_CONSTRAINT) && !IS_ENDBUF_CONTEXT (context)))
356 re_node_set *entrance_nodes;
357 struct re_dfastate_t **trtable;
358 struct re_dfastate_t **trtable_search;
359 /* If this state is a special state.
360 A state is a special state if the state is the halt state, or
362 unsigned int context : 2;
363 unsigned int halt : 1;
364 /* If this state can accept `multi byte'.
365 Note that we refer to multibyte characters, and multi character
366 collating elements as `multi byte'. */
367 unsigned int accept_mb : 1;
368 /* If this state has backreference node(s). */
369 unsigned int has_backref : 1;
370 unsigned int has_constraint : 1;
372 typedef struct re_dfastate_t re_dfastate_t;
376 /* start <= node < end */
381 struct re_state_table_entry
385 re_dfastate_t **array;
388 struct re_backref_cache_entry
398 /* EFLAGS of the argument of regexec. */
400 /* Where the matching ends. */
402 /* The string object corresponding to the input string. */
404 /* The state log used by the matcher. */
405 re_dfastate_t **state_log;
407 /* Back reference cache. */
410 struct re_backref_cache_entry *bkref_ents;
412 } re_match_context_t;
416 re_bitset_ptr_t word_char;
418 /* number of subexpressions `re_nsub' is in regex_t. */
420 re_subexp_t *subexps;
425 bin_tree_t *str_tree;
429 re_node_set *eclosures;
430 re_node_set *inveclosures;
431 struct re_state_table_entry *state_table;
432 unsigned int state_hash_mask;
433 re_dfastate_t *init_state;
434 re_dfastate_t *init_state_word;
435 re_dfastate_t *init_state_nl;
436 re_dfastate_t *init_state_begbuf;
439 int nbackref; /* The number of backreference in this dfa. */
440 /* If this dfa has "multibyte node", which is a backreference or
441 a node which can accept multibyte character or multi character
442 collating element. */
443 unsigned int has_mb_node : 1;
445 typedef struct re_dfa_t re_dfa_t;
447 static reg_errcode_t re_node_set_alloc (re_node_set *set, int size);
448 static reg_errcode_t re_node_set_init_1 (re_node_set *set, int elem);
449 static reg_errcode_t re_node_set_init_2 (re_node_set *set, int elem1,
451 #define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set))
452 static reg_errcode_t re_node_set_init_copy (re_node_set *dest,
453 const re_node_set *src);
454 static reg_errcode_t re_node_set_intersect (re_node_set *dest,
455 const re_node_set *src1,
456 const re_node_set *src2);
457 static reg_errcode_t re_node_set_add_intersect (re_node_set *dest,
458 const re_node_set *src1,
459 const re_node_set *src2);
460 static reg_errcode_t re_node_set_init_union (re_node_set *dest,
461 const re_node_set *src1,
462 const re_node_set *src2);
463 static reg_errcode_t re_node_set_merge (re_node_set *dest,
464 const re_node_set *src);
465 static int re_node_set_insert (re_node_set *set, int elem);
466 static int re_node_set_compare (const re_node_set *set1,
467 const re_node_set *set2);
468 static int re_node_set_contains (const re_node_set *set, int elem);
469 static void re_node_set_remove_at (re_node_set *set, int idx);
470 #define re_node_set_empty(p) ((p)->nelem = 0)
471 #define re_node_set_free(set) re_free ((set)->elems)
472 static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token, int mode);
473 static re_dfastate_t *re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa,
474 const re_node_set *nodes);
475 static re_dfastate_t *re_acquire_state_context (reg_errcode_t *err,
477 const re_node_set *nodes,
478 unsigned int context);
492 bracket_elem_type type;
502 /* Inline functions for bitset operation. */
508 for (bitset_i = 0; bitset_i < BITSET_UINTS; ++bitset_i)
509 set[bitset_i] = ~set[bitset_i];
513 bitset_merge (dest, src)
518 for (bitset_i = 0; bitset_i < BITSET_UINTS; ++bitset_i)
519 dest[bitset_i] |= src[bitset_i];
523 bitset_not_merge (dest, src)
528 for (i = 0; i < BITSET_UINTS; ++i)
532 #ifdef RE_ENABLE_I18N
533 /* Inline functions for re_string. */
535 re_string_char_size_at (pstr, idx)
536 const re_string_t *pstr;
542 for (byte_idx = 1; idx + byte_idx < pstr->len; ++byte_idx)
543 if (pstr->wcs[idx + byte_idx] != WEOF)
549 re_string_wchar_at (pstr, idx)
550 const re_string_t *pstr;
554 return (wint_t) pstr->mbs[idx];
555 return (wint_t) pstr->wcs[idx];
559 re_string_elem_size_at (pstr, idx)
560 const re_string_t *pstr;
564 const unsigned char *p;
566 const int32_t *table, *indirect;
568 # include <locale/weight.h>
569 uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
573 table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
574 extra = (const char *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
575 indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
576 _NL_COLLATE_INDIRECTMB);
579 return p - (const unsigned char *) pstr->mbs - idx;
585 #endif /* RE_ENABLE_I18N */
587 #endif /* _REGEX_INTERNAL_H */