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