root/lib/regex_internal.h

INCLUDED FROM

DEFINITIONS

1. bitset_set
2. bitset_clear
3. bitset_contain
4. bitset_empty
5. bitset_set_all
6. bitset_copy
7. bitset_not
8. bitset_merge
9. bitset_mask
10. re_string_char_size_at
11. re_string_wchar_at
12. re_string_elem_size_at

     1 /* Extended regular expression matching and search library.
     2    Copyright (C) 2002-2023 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, see
    18    <https://www.gnu.org/licenses/>.  */
    19 
    20 #ifndef _REGEX_INTERNAL_H
    21 #define _REGEX_INTERNAL_H 1
    22 
    23 #include <ctype.h>
    24 #include <stdio.h>
    25 #include <stdlib.h>
    26 #include <string.h>
    27 
    28 #include <langinfo.h>
    29 #include <locale.h>
    30 #include <wchar.h>
    31 #include <wctype.h>
    32 #include <stdint.h>
    33 
    34 #ifndef _LIBC
    35 # include <dynarray.h>
    36 #endif
    37 
    38 #include <intprops.h>
    39 #include <verify.h>
    40 
    41 #if defined DEBUG && DEBUG != 0
    42 # include <assert.h>
    43 # define DEBUG_ASSERT(x) assert (x)
    44 #else
    45 # define DEBUG_ASSERT(x) assume (x)
    46 #endif
    47 
    48 #ifdef _LIBC
    49 # include <libc-lock.h>
    50 # define lock_define(name) __libc_lock_define (, name)
    51 # define lock_init(lock) (__libc_lock_init (lock), 0)
    52 # define lock_fini(lock) ((void) 0)
    53 # define lock_lock(lock) __libc_lock_lock (lock)
    54 # define lock_unlock(lock) __libc_lock_unlock (lock)
    55 #elif defined GNULIB_LOCK && !defined GNULIB_REGEX_SINGLE_THREAD
    56 # include "glthread/lock.h"
    57 # define lock_define(name) gl_lock_define (, name)
    58 # define lock_init(lock) glthread_lock_init (&(lock))
    59 # define lock_fini(lock) glthread_lock_destroy (&(lock))
    60 # define lock_lock(lock) glthread_lock_lock (&(lock))
    61 # define lock_unlock(lock) glthread_lock_unlock (&(lock))
    62 #elif defined GNULIB_PTHREAD && !defined GNULIB_REGEX_SINGLE_THREAD
    63 # include <pthread.h>
    64 # define lock_define(name) pthread_mutex_t name;
    65 # define lock_init(lock) pthread_mutex_init (&(lock), 0)
    66 # define lock_fini(lock) pthread_mutex_destroy (&(lock))
    67 # define lock_lock(lock) pthread_mutex_lock (&(lock))
    68 # define lock_unlock(lock) pthread_mutex_unlock (&(lock))
    69 #else
    70 # define lock_define(name)
    71 # define lock_init(lock) 0
    72 # define lock_fini(lock) ((void) 0)
    73   /* The 'dfa' avoids an "unused variable 'dfa'" warning from GCC.  */
    74 # define lock_lock(lock) ((void) dfa)
    75 # define lock_unlock(lock) ((void) 0)
    76 #endif
    77 
    78 /* In case that the system doesn't have isblank().  */
    79 #if !defined _LIBC && ! (defined isblank || (HAVE_ISBLANK && HAVE_DECL_ISBLANK))
    80 # define isblank(ch) ((ch) == ' ' || (ch) == '\t')
    81 #endif
    82 
    83 /* regex code assumes isascii has its usual numeric meaning,
    84    even if the portable character set uses EBCDIC encoding,
    85    and even if wint_t is wider than int.  */
    86 #ifndef _LIBC
    87 # undef isascii
    88 # define isascii(c) (((c) & ~0x7f) == 0)
    89 #endif
    90 
    91 #ifdef _LIBC
    92 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
    93 #  define _RE_DEFINE_LOCALE_FUNCTIONS 1
    94 #   include <locale/localeinfo.h>
    95 #   include <locale/coll-lookup.h>
    96 # endif
    97 #endif
    98 
    99 /* This is for other GNU distributions with internationalized messages.  */
   100 #if (HAVE_LIBINTL_H && ENABLE_NLS) || defined _LIBC
   101 # include <libintl.h>
   102 # ifdef _LIBC
   103 #  undef gettext
   104 #  define gettext(msgid) \
   105   __dcgettext (_libc_intl_domainname, msgid, LC_MESSAGES)
   106 # endif
   107 #else
   108 # undef gettext
   109 # define gettext(msgid) (msgid)
   110 #endif
   111 
   112 #ifndef gettext_noop
   113 /* This define is so xgettext can find the internationalizable
   114    strings.  */
   115 # define gettext_noop(String) String
   116 #endif
   117 
   118 /* Number of ASCII characters.  */
   119 #define ASCII_CHARS 0x80
   120 
   121 /* Number of single byte characters.  */
   122 #define SBC_MAX (UCHAR_MAX + 1)
   123 
   124 #define COLL_ELEM_LEN_MAX 8
   125 
   126 /* The character which represents newline.  */
   127 #define NEWLINE_CHAR '\n'
   128 #define WIDE_NEWLINE_CHAR L'\n'
   129 
   130 /* Rename to standard API for using out of glibc.  */
   131 #ifndef _LIBC
   132 # undef __wctype
   133 # undef __iswalnum
   134 # undef __iswctype
   135 # undef __towlower
   136 # undef __towupper
   137 # define __wctype wctype
   138 # define __iswalnum iswalnum
   139 # define __iswctype iswctype
   140 # define __towlower towlower
   141 # define __towupper towupper
   142 # define __btowc btowc
   143 # define __mbrtowc mbrtowc
   144 # define __wcrtomb wcrtomb
   145 # define __regfree regfree
   146 #endif /* not _LIBC */
   147 
   148 /* Types related to integers.  Unless protected by #ifdef _LIBC, the
   149    regex code should avoid exact-width types like int32_t and uint64_t
   150    as some non-GCC platforms lack them, an issue when this code is
   151    used in Gnulib.  */
   152 
   153 #ifndef SSIZE_MAX
   154 # define SSIZE_MAX ((ssize_t) (SIZE_MAX / 2))
   155 #endif
   156 #ifndef ULONG_WIDTH
   157 # define ULONG_WIDTH REGEX_UINTEGER_WIDTH (ULONG_MAX)
   158 /* The number of usable bits in an unsigned integer type with maximum
   159    value MAX, as an int expression suitable in #if.  Cover all known
   160    practical hosts.  This implementation exploits the fact that MAX is
   161    1 less than a power of 2, and merely counts the number of 1 bits in
   162    MAX; "COBn" means "count the number of 1 bits in the low-order n bits".  */
   163 # define REGEX_UINTEGER_WIDTH(max) REGEX_COB128 (max)
   164 # define REGEX_COB128(n) (REGEX_COB64 ((n) >> 31 >> 31 >> 2) + REGEX_COB64 (n))
   165 # define REGEX_COB64(n) (REGEX_COB32 ((n) >> 31 >> 1) + REGEX_COB32 (n))
   166 # define REGEX_COB32(n) (REGEX_COB16 ((n) >> 16) + REGEX_COB16 (n))
   167 # define REGEX_COB16(n) (REGEX_COB8 ((n) >> 8) + REGEX_COB8 (n))
   168 # define REGEX_COB8(n) (REGEX_COB4 ((n) >> 4) + REGEX_COB4 (n))
   169 # define REGEX_COB4(n) (!!((n) & 8) + !!((n) & 4) + !!((n) & 2) + ((n) & 1))
   170 # if ULONG_MAX / 2 + 1 != 1ul << (ULONG_WIDTH - 1)
   171 #  error "ULONG_MAX out of range"
   172 # endif
   173 #endif
   174 
   175 /* The type of indexes into strings.  This is signed, not size_t,
   176    since the API requires indexes to fit in regoff_t anyway, and using
   177    signed integers makes the code a bit smaller and presumably faster.
   178    The traditional GNU regex implementation uses int for indexes.
   179    The POSIX-compatible implementation uses a possibly-wider type.
   180    The name 'Idx' is three letters to minimize the hassle of
   181    reindenting a lot of regex code that formerly used 'int'.  */
   182 typedef regoff_t Idx;
   183 #ifdef _REGEX_LARGE_OFFSETS
   184 # define IDX_MAX SSIZE_MAX
   185 #else
   186 # define IDX_MAX INT_MAX
   187 #endif
   188 
   189 /* A hash value, suitable for computing hash tables.  */
   190 typedef __re_size_t re_hashval_t;
   191 
   192 /* An integer used to represent a set of bits.  It must be unsigned,
   193    and must be at least as wide as unsigned int.  */
   194 typedef unsigned long int bitset_word_t;
   195 /* All bits set in a bitset_word_t.  */
   196 #define BITSET_WORD_MAX ULONG_MAX
   197 /* Number of bits in a bitset_word_t.  */
   198 #define BITSET_WORD_BITS ULONG_WIDTH
   199 
   200 /* Number of bitset_word_t values in a bitset_t.  */
   201 #define BITSET_WORDS ((SBC_MAX + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
   202 
   203 typedef bitset_word_t bitset_t[BITSET_WORDS];
   204 typedef bitset_word_t *re_bitset_ptr_t;
   205 typedef const bitset_word_t *re_const_bitset_ptr_t;
   206 
   207 #define PREV_WORD_CONSTRAINT 0x0001
   208 #define PREV_NOTWORD_CONSTRAINT 0x0002
   209 #define NEXT_WORD_CONSTRAINT 0x0004
   210 #define NEXT_NOTWORD_CONSTRAINT 0x0008
   211 #define PREV_NEWLINE_CONSTRAINT 0x0010
   212 #define NEXT_NEWLINE_CONSTRAINT 0x0020
   213 #define PREV_BEGBUF_CONSTRAINT 0x0040
   214 #define NEXT_ENDBUF_CONSTRAINT 0x0080
   215 #define WORD_DELIM_CONSTRAINT 0x0100
   216 #define NOT_WORD_DELIM_CONSTRAINT 0x0200
   217 
   218 typedef enum
   219 {
   220   INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
   221   WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
   222   WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
   223   INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
   224   LINE_FIRST = PREV_NEWLINE_CONSTRAINT,
   225   LINE_LAST = NEXT_NEWLINE_CONSTRAINT,
   226   BUF_FIRST = PREV_BEGBUF_CONSTRAINT,
   227   BUF_LAST = NEXT_ENDBUF_CONSTRAINT,
   228   WORD_DELIM = WORD_DELIM_CONSTRAINT,
   229   NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT
   230 } re_context_type;
   231 
   232 typedef struct
   233 {
   234   Idx alloc;
   235   Idx nelem;
   236   Idx *elems;
   237 } re_node_set;
   238 
   239 typedef enum
   240 {
   241   NON_TYPE = 0,
   242 
   243   /* Node type, These are used by token, node, tree.  */
   244   CHARACTER = 1,
   245   END_OF_RE = 2,
   246   SIMPLE_BRACKET = 3,
   247   OP_BACK_REF = 4,
   248   OP_PERIOD = 5,
   249   COMPLEX_BRACKET = 6,
   250   OP_UTF8_PERIOD = 7,
   251 
   252   /* We define EPSILON_BIT as a macro so that OP_OPEN_SUBEXP is used
   253      when the debugger shows values of this enum type.  */
   254 #define EPSILON_BIT 8
   255   OP_OPEN_SUBEXP = EPSILON_BIT | 0,
   256   OP_CLOSE_SUBEXP = EPSILON_BIT | 1,
   257   OP_ALT = EPSILON_BIT | 2,
   258   OP_DUP_ASTERISK = EPSILON_BIT | 3,
   259   ANCHOR = EPSILON_BIT | 4,
   260 
   261   /* Tree type, these are used only by tree. */
   262   CONCAT = 16,
   263   SUBEXP = 17,
   264 
   265   /* Token type, these are used only by token.  */
   266   OP_DUP_PLUS = 18,
   267   OP_DUP_QUESTION,
   268   OP_OPEN_BRACKET,
   269   OP_CLOSE_BRACKET,
   270   OP_CHARSET_RANGE,
   271   OP_OPEN_DUP_NUM,
   272   OP_CLOSE_DUP_NUM,
   273   OP_NON_MATCH_LIST,
   274   OP_OPEN_COLL_ELEM,
   275   OP_CLOSE_COLL_ELEM,
   276   OP_OPEN_EQUIV_CLASS,
   277   OP_CLOSE_EQUIV_CLASS,
   278   OP_OPEN_CHAR_CLASS,
   279   OP_CLOSE_CHAR_CLASS,
   280   OP_WORD,
   281   OP_NOTWORD,
   282   OP_SPACE,
   283   OP_NOTSPACE,
   284   BACK_SLASH
   285 
   286 } re_token_type_t;
   287 
   288 typedef struct
   289 {
   290   /* Multibyte characters.  */
   291   wchar_t *mbchars;
   292 
   293 #ifdef _LIBC
   294   /* Collating symbols.  */
   295   int32_t *coll_syms;
   296 #endif
   297 
   298 #ifdef _LIBC
   299   /* Equivalence classes. */
   300   int32_t *equiv_classes;
   301 #endif
   302 
   303   /* Range expressions. */
   304 #ifdef _LIBC
   305   uint32_t *range_starts;
   306   uint32_t *range_ends;
   307 #else
   308   wchar_t *range_starts;
   309   wchar_t *range_ends;
   310 #endif
   311 
   312   /* Character classes. */
   313   wctype_t *char_classes;
   314 
   315   /* If this character set is the non-matching list.  */
   316   unsigned int non_match : 1;
   317 
   318   /* # of multibyte characters.  */
   319   Idx nmbchars;
   320 
   321   /* # of collating symbols.  */
   322   Idx ncoll_syms;
   323 
   324   /* # of equivalence classes. */
   325   Idx nequiv_classes;
   326 
   327   /* # of range expressions. */
   328   Idx nranges;
   329 
   330   /* # of character classes. */
   331   Idx nchar_classes;
   332 } re_charset_t;
   333 
   334 typedef struct
   335 {
   336   union
   337   {
   338     unsigned char c;            /* for CHARACTER */
   339     re_bitset_ptr_t sbcset;     /* for SIMPLE_BRACKET */
   340     re_charset_t *mbcset;       /* for COMPLEX_BRACKET */
   341     Idx idx;                    /* for BACK_REF */
   342     re_context_type ctx_type;   /* for ANCHOR */
   343   } opr;
   344 #if (__GNUC__ >= 2 || defined __clang__) && !defined __STRICT_ANSI__
   345   re_token_type_t type : 8;
   346 #else
   347   re_token_type_t type;
   348 #endif
   349   unsigned int constraint : 10; /* context constraint */
   350   unsigned int duplicated : 1;
   351   unsigned int opt_subexp : 1;
   352   unsigned int accept_mb : 1;
   353   /* These 2 bits can be moved into the union if needed (e.g. if running out
   354      of bits; move opr.c to opr.c.c and move the flags to opr.c.flags).  */
   355   unsigned int mb_partial : 1;
   356   unsigned int word_char : 1;
   357 } re_token_t;
   358 
   359 #define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT)
   360 
   361 struct re_string_t
   362 {
   363   /* Indicate the raw buffer which is the original string passed as an
   364      argument of regexec(), re_search(), etc..  */
   365   const unsigned char *raw_mbs;
   366   /* Store the multibyte string.  In case of "case insensitive mode" like
   367      REG_ICASE, upper cases of the string are stored, otherwise MBS points
   368      the same address that RAW_MBS points.  */
   369   unsigned char *mbs;
   370   /* Store the wide character string which is corresponding to MBS.  */
   371   wint_t *wcs;
   372   Idx *offsets;
   373   mbstate_t cur_state;
   374   /* Index in RAW_MBS.  Each character mbs[i] corresponds to
   375      raw_mbs[raw_mbs_idx + i].  */
   376   Idx raw_mbs_idx;
   377   /* The length of the valid characters in the buffers.  */
   378   Idx valid_len;
   379   /* The corresponding number of bytes in raw_mbs array.  */
   380   Idx valid_raw_len;
   381   /* The length of the buffers MBS and WCS.  */
   382   Idx bufs_len;
   383   /* The index in MBS, which is updated by re_string_fetch_byte.  */
   384   Idx cur_idx;
   385   /* length of RAW_MBS array.  */
   386   Idx raw_len;
   387   /* This is RAW_LEN - RAW_MBS_IDX + VALID_LEN - VALID_RAW_LEN.  */
   388   Idx len;
   389   /* End of the buffer may be shorter than its length in the cases such
   390      as re_match_2, re_search_2.  Then, we use STOP for end of the buffer
   391      instead of LEN.  */
   392   Idx raw_stop;
   393   /* This is RAW_STOP - RAW_MBS_IDX adjusted through OFFSETS.  */
   394   Idx stop;
   395 
   396   /* The context of mbs[0].  We store the context independently, since
   397      the context of mbs[0] may be different from raw_mbs[0], which is
   398      the beginning of the input string.  */
   399   unsigned int tip_context;
   400   /* The translation passed as a part of an argument of re_compile_pattern.  */
   401   RE_TRANSLATE_TYPE trans;
   402   /* Copy of re_dfa_t's word_char.  */
   403   re_const_bitset_ptr_t word_char;
   404   /* true if REG_ICASE.  */
   405   unsigned char icase;
   406   unsigned char is_utf8;
   407   unsigned char map_notascii;
   408   unsigned char mbs_allocated;
   409   unsigned char offsets_needed;
   410   unsigned char newline_anchor;
   411   unsigned char word_ops_used;
   412   int mb_cur_max;
   413 };
   414 typedef struct re_string_t re_string_t;
   415 
   416 
   417 struct re_dfa_t;
   418 typedef struct re_dfa_t re_dfa_t;
   419 
   420 #ifndef _LIBC
   421 # define IS_IN(libc) false
   422 #endif
   423 
   424 #define re_string_peek_byte(pstr, offset) \
   425   ((pstr)->mbs[(pstr)->cur_idx + offset])
   426 #define re_string_fetch_byte(pstr) \
   427   ((pstr)->mbs[(pstr)->cur_idx++])
   428 #define re_string_first_byte(pstr, idx) \
   429   ((idx) == (pstr)->valid_len || (pstr)->wcs[idx] != WEOF)
   430 #define re_string_is_single_byte_char(pstr, idx) \
   431   ((pstr)->wcs[idx] != WEOF && ((pstr)->valid_len == (idx) + 1 \
   432                                 || (pstr)->wcs[(idx) + 1] != WEOF))
   433 #define re_string_eoi(pstr) ((pstr)->stop <= (pstr)->cur_idx)
   434 #define re_string_cur_idx(pstr) ((pstr)->cur_idx)
   435 #define re_string_get_buffer(pstr) ((pstr)->mbs)
   436 #define re_string_length(pstr) ((pstr)->len)
   437 #define re_string_byte_at(pstr,idx) ((pstr)->mbs[idx])
   438 #define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
   439 #define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
   440 
   441 #ifdef _LIBC
   442 # define MALLOC_0_IS_NONNULL 1
   443 #elif !defined MALLOC_0_IS_NONNULL
   444 # define MALLOC_0_IS_NONNULL 0
   445 #endif
   446 
   447 #ifndef MAX
   448 # define MAX(a,b) ((a) < (b) ? (b) : (a))
   449 #endif
   450 #ifndef MIN
   451 # define MIN(a,b) ((a) < (b) ? (a) : (b))
   452 #endif
   453 
   454 #define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t)))
   455 #define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t)))
   456 #define re_free(p) free (p)
   457 
   458 struct bin_tree_t
   459 {
   460   struct bin_tree_t *parent;
   461   struct bin_tree_t *left;
   462   struct bin_tree_t *right;
   463   struct bin_tree_t *first;
   464   struct bin_tree_t *next;
   465 
   466   re_token_t token;
   467 
   468   /* 'node_idx' is the index in dfa->nodes, if 'type' == 0.
   469      Otherwise 'type' indicate the type of this node.  */
   470   Idx node_idx;
   471 };
   472 typedef struct bin_tree_t bin_tree_t;
   473 
   474 #define BIN_TREE_STORAGE_SIZE \
   475   ((1024 - sizeof (void *)) / sizeof (bin_tree_t))
   476 
   477 struct bin_tree_storage_t
   478 {
   479   struct bin_tree_storage_t *next;
   480   bin_tree_t data[BIN_TREE_STORAGE_SIZE];
   481 };
   482 typedef struct bin_tree_storage_t bin_tree_storage_t;
   483 
   484 #define CONTEXT_WORD 1
   485 #define CONTEXT_NEWLINE (CONTEXT_WORD << 1)
   486 #define CONTEXT_BEGBUF (CONTEXT_NEWLINE << 1)
   487 #define CONTEXT_ENDBUF (CONTEXT_BEGBUF << 1)
   488 
   489 #define IS_WORD_CONTEXT(c) ((c) & CONTEXT_WORD)
   490 #define IS_NEWLINE_CONTEXT(c) ((c) & CONTEXT_NEWLINE)
   491 #define IS_BEGBUF_CONTEXT(c) ((c) & CONTEXT_BEGBUF)
   492 #define IS_ENDBUF_CONTEXT(c) ((c) & CONTEXT_ENDBUF)
   493 #define IS_ORDINARY_CONTEXT(c) ((c) == 0)
   494 
   495 #define IS_WORD_CHAR(ch) (isalnum (ch) || (ch) == '_')
   496 #define IS_NEWLINE(ch) ((ch) == NEWLINE_CHAR)
   497 #define IS_WIDE_WORD_CHAR(ch) (__iswalnum (ch) || (ch) == L'_')
   498 #define IS_WIDE_NEWLINE(ch) ((ch) == WIDE_NEWLINE_CHAR)
   499 
   500 #define NOT_SATISFY_PREV_CONSTRAINT(constraint,context) \
   501  ((((constraint) & PREV_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
   502   || ((constraint & PREV_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
   503   || ((constraint & PREV_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context))\
   504   || ((constraint & PREV_BEGBUF_CONSTRAINT) && !IS_BEGBUF_CONTEXT (context)))
   505 
   506 #define NOT_SATISFY_NEXT_CONSTRAINT(constraint,context) \
   507  ((((constraint) & NEXT_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
   508   || (((constraint) & NEXT_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
   509   || (((constraint) & NEXT_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context)) \
   510   || (((constraint) & NEXT_ENDBUF_CONSTRAINT) && !IS_ENDBUF_CONTEXT (context)))
   511 
   512 struct re_dfastate_t
   513 {
   514   re_hashval_t hash;
   515   re_node_set nodes;
   516   re_node_set non_eps_nodes;
   517   re_node_set inveclosure;
   518   re_node_set *entrance_nodes;
   519   struct re_dfastate_t **trtable, **word_trtable;
   520   unsigned int context : 4;
   521   unsigned int halt : 1;
   522   /* If this state can accept "multi byte".
   523      Note that we refer to multibyte characters, and multi character
   524      collating elements as "multi byte".  */
   525   unsigned int accept_mb : 1;
   526   /* If this state has backreference node(s).  */
   527   unsigned int has_backref : 1;
   528   unsigned int has_constraint : 1;
   529 };
   530 typedef struct re_dfastate_t re_dfastate_t;
   531 
   532 struct re_state_table_entry
   533 {
   534   Idx num;
   535   Idx alloc;
   536   re_dfastate_t **array;
   537 };
   538 
   539 /* Array type used in re_sub_match_last_t and re_sub_match_top_t.  */
   540 
   541 typedef struct
   542 {
   543   Idx next_idx;
   544   Idx alloc;
   545   re_dfastate_t **array;
   546 } state_array_t;
   547 
   548 /* Store information about the node NODE whose type is OP_CLOSE_SUBEXP.  */
   549 
   550 typedef struct
   551 {
   552   Idx node;
   553   Idx str_idx; /* The position NODE match at.  */
   554   state_array_t path;
   555 } re_sub_match_last_t;
   556 
   557 /* Store information about the node NODE whose type is OP_OPEN_SUBEXP.
   558    And information about the node, whose type is OP_CLOSE_SUBEXP,
   559    corresponding to NODE is stored in LASTS.  */
   560 
   561 typedef struct
   562 {
   563   Idx str_idx;
   564   Idx node;
   565   state_array_t *path;
   566   Idx alasts; /* Allocation size of LASTS.  */
   567   Idx nlasts; /* The number of LASTS.  */
   568   re_sub_match_last_t **lasts;
   569 } re_sub_match_top_t;
   570 
   571 struct re_backref_cache_entry
   572 {
   573   Idx node;
   574   Idx str_idx;
   575   Idx subexp_from;
   576   Idx subexp_to;
   577   bitset_word_t eps_reachable_subexps_map;
   578   char more;
   579 };
   580 
   581 typedef struct
   582 {
   583   /* The string object corresponding to the input string.  */
   584   re_string_t input;
   585   const re_dfa_t *const dfa;
   586   /* EFLAGS of the argument of regexec.  */
   587   int eflags;
   588   /* Where the matching ends.  */
   589   Idx match_last;
   590   Idx last_node;
   591   /* The state log used by the matcher.  */
   592   re_dfastate_t **state_log;
   593   Idx state_log_top;
   594   /* Back reference cache.  */
   595   Idx nbkref_ents;
   596   Idx abkref_ents;
   597   struct re_backref_cache_entry *bkref_ents;
   598   int max_mb_elem_len;
   599   Idx nsub_tops;
   600   Idx asub_tops;
   601   re_sub_match_top_t **sub_tops;
   602 } re_match_context_t;
   603 
   604 typedef struct
   605 {
   606   re_dfastate_t **sifted_states;
   607   re_dfastate_t **limited_states;
   608   Idx last_node;
   609   Idx last_str_idx;
   610   re_node_set limits;
   611 } re_sift_context_t;
   612 
   613 struct re_fail_stack_ent_t
   614 {
   615   Idx idx;
   616   Idx node;
   617   regmatch_t *regs;
   618   re_node_set eps_via_nodes;
   619 };
   620 
   621 struct re_fail_stack_t
   622 {
   623   Idx num;
   624   Idx alloc;
   625   struct re_fail_stack_ent_t *stack;
   626 };
   627 
   628 struct re_dfa_t
   629 {
   630   re_token_t *nodes;
   631   size_t nodes_alloc;
   632   size_t nodes_len;
   633   Idx *nexts;
   634   Idx *org_indices;
   635   re_node_set *edests;
   636   re_node_set *eclosures;
   637   re_node_set *inveclosures;
   638   struct re_state_table_entry *state_table;
   639   re_dfastate_t *init_state;
   640   re_dfastate_t *init_state_word;
   641   re_dfastate_t *init_state_nl;
   642   re_dfastate_t *init_state_begbuf;
   643   bin_tree_t *str_tree;
   644   bin_tree_storage_t *str_tree_storage;
   645   re_bitset_ptr_t sb_char;
   646   int str_tree_storage_idx;
   647 
   648   /* number of subexpressions 're_nsub' is in regex_t.  */
   649   re_hashval_t state_hash_mask;
   650   Idx init_node;
   651   Idx nbackref; /* The number of backreference in this dfa.  */
   652 
   653   /* Bitmap expressing which backreference is used.  */
   654   bitset_word_t used_bkref_map;
   655   bitset_word_t completed_bkref_map;
   656 
   657   unsigned int has_plural_match : 1;
   658   /* If this dfa has "multibyte node", which is a backreference or
   659      a node which can accept multibyte character or multi character
   660      collating element.  */
   661   unsigned int has_mb_node : 1;
   662   unsigned int is_utf8 : 1;
   663   unsigned int map_notascii : 1;
   664   unsigned int word_ops_used : 1;
   665   int mb_cur_max;
   666   bitset_t word_char;
   667   reg_syntax_t syntax;
   668   Idx *subexp_map;
   669 #ifdef DEBUG
   670   char* re_str;
   671 #endif
   672   lock_define (lock)
   673 };
   674 
   675 #define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set))
   676 #define re_node_set_remove(set,id) \
   677   (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1))
   678 #define re_node_set_empty(p) ((p)->nelem = 0)
   679 #define re_node_set_free(set) re_free ((set)->elems)
   680 
   681 
   682 typedef enum
   683 {
   684   SB_CHAR,
   685   MB_CHAR,
   686   EQUIV_CLASS,
   687   COLL_SYM,
   688   CHAR_CLASS
   689 } bracket_elem_type;
   690 
   691 typedef struct
   692 {
   693   bracket_elem_type type;
   694   union
   695   {
   696     unsigned char ch;
   697     unsigned char *name;
   698     wchar_t wch;
   699   } opr;
   700 } bracket_elem_t;
   701 
   702 
   703 /* Functions for bitset_t operation.  */
   704 
   705 static inline void
   706 bitset_set (bitset_t set, Idx i)
   707 {
   708   set[i / BITSET_WORD_BITS] |= (bitset_word_t) 1 << i % BITSET_WORD_BITS;
   709 }
   710 
   711 static inline void
   712 bitset_clear (bitset_t set, Idx i)
   713 {
   714   set[i / BITSET_WORD_BITS] &= ~ ((bitset_word_t) 1 << i % BITSET_WORD_BITS);
   715 }
   716 
   717 static inline bool
   718 bitset_contain (const bitset_t set, Idx i)
   719 {
   720   return (set[i / BITSET_WORD_BITS] >> i % BITSET_WORD_BITS) & 1;
   721 }
   722 
   723 static inline void
   724 bitset_empty (bitset_t set)
   725 {
   726   memset (set, '\0', sizeof (bitset_t));
   727 }
   728 
   729 static inline void
   730 bitset_set_all (bitset_t set)
   731 {
   732   memset (set, -1, sizeof (bitset_word_t) * (SBC_MAX / BITSET_WORD_BITS));
   733   if (SBC_MAX % BITSET_WORD_BITS != 0)
   734     set[BITSET_WORDS - 1] =
   735       ((bitset_word_t) 1 << SBC_MAX % BITSET_WORD_BITS) - 1;
   736 }
   737 
   738 static inline void
   739 bitset_copy (bitset_t dest, const bitset_t src)
   740 {
   741   memcpy (dest, src, sizeof (bitset_t));
   742 }
   743 
   744 static inline void
   745 bitset_not (bitset_t set)
   746 {
   747   int bitset_i;
   748   for (bitset_i = 0; bitset_i < SBC_MAX / BITSET_WORD_BITS; ++bitset_i)
   749     set[bitset_i] = ~set[bitset_i];
   750   if (SBC_MAX % BITSET_WORD_BITS != 0)
   751     set[BITSET_WORDS - 1] =
   752       ((((bitset_word_t) 1 << SBC_MAX % BITSET_WORD_BITS) - 1)
   753        & ~set[BITSET_WORDS - 1]);
   754 }
   755 
   756 static inline void
   757 bitset_merge (bitset_t dest, const bitset_t src)
   758 {
   759   int bitset_i;
   760   for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
   761     dest[bitset_i] |= src[bitset_i];
   762 }
   763 
   764 static inline void
   765 bitset_mask (bitset_t dest, const bitset_t src)
   766 {
   767   int bitset_i;
   768   for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
   769     dest[bitset_i] &= src[bitset_i];
   770 }
   771 
   772 /* Functions for re_string.  */
   773 static int
   774 __attribute__ ((pure, unused))
   775 re_string_char_size_at (const re_string_t *pstr, Idx idx)
   776 {
   777   int byte_idx;
   778   if (pstr->mb_cur_max == 1)
   779     return 1;
   780   for (byte_idx = 1; idx + byte_idx < pstr->valid_len; ++byte_idx)
   781     if (pstr->wcs[idx + byte_idx] != WEOF)
   782       break;
   783   return byte_idx;
   784 }
   785 
   786 static wint_t
   787 __attribute__ ((pure, unused))
   788 re_string_wchar_at (const re_string_t *pstr, Idx idx)
   789 {
   790   if (pstr->mb_cur_max == 1)
   791     return (wint_t) pstr->mbs[idx];
   792   return (wint_t) pstr->wcs[idx];
   793 }
   794 
   795 #ifdef _LIBC
   796 # include <locale/weight.h>
   797 #endif
   798 
   799 static int
   800 __attribute__ ((pure, unused))
   801 re_string_elem_size_at (const re_string_t *pstr, Idx idx)
   802 {
   803 #ifdef _LIBC
   804   const unsigned char *p, *extra;
   805   const int32_t *table, *indirect;
   806   uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
   807 
   808   if (nrules != 0)
   809     {
   810       table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
   811       extra = (const unsigned char *)
   812         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
   813       indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
   814                                                 _NL_COLLATE_INDIRECTMB);
   815       p = pstr->mbs + idx;
   816       findidx (table, indirect, extra, &p, pstr->len - idx);
   817       return p - pstr->mbs - idx;
   818     }
   819 #endif /* _LIBC */
   820 
   821   return 1;
   822 }
   823 
   824 #ifdef _LIBC
   825 # if __GNUC__ >= 7
   826 #  define FALLTHROUGH __attribute__ ((__fallthrough__))
   827 # else
   828 #  define FALLTHROUGH ((void) 0)
   829 # endif
   830 #else
   831 # include "attribute.h"
   832 #endif
   833 
   834 #endif /*  _REGEX_INTERNAL_H */