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