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