1 /* Extended regular expression matching and search library. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 This file is part of the GNU C Library. 4 Contributed by Isamu Hasegawa <isamu (at) yamato.ibm.com>. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 This program 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 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License along 17 with this program; if not, write to the Free Software Foundation, 18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 19 #include <sys/cdefs.h> 20 __RCSID("$NetBSD: regex_internal.c,v 1.2 2016/05/17 14:00:09 christos Exp $"); 21 22 23 static void re_string_construct_common (const char *str, Idx len, 24 re_string_t *pstr, 25 REG_TRANSLATE_TYPE trans, bool icase, 26 const re_dfa_t *dfa) internal_function; 27 static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa, 28 const re_node_set *nodes, 29 re_hashval_t hash) internal_function; 30 static re_dfastate_t *create_cd_newstate (const re_dfa_t *dfa, 31 const re_node_set *nodes, 32 unsigned int context, 33 re_hashval_t hash) internal_function; 34 35 /* Functions for string operation. */ 37 38 /* This function allocate the buffers. It is necessary to call 39 re_string_reconstruct before using the object. */ 40 41 static reg_errcode_t 42 internal_function 43 re_string_allocate (re_string_t *pstr, const char *str, Idx len, Idx init_len, 44 REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) 45 { 46 reg_errcode_t ret; 47 Idx init_buf_len; 48 49 /* Ensure at least one character fits into the buffers. */ 50 if (init_len < dfa->mb_cur_max) 51 init_len = dfa->mb_cur_max; 52 init_buf_len = (len + 1 < init_len) ? len + 1: init_len; 53 re_string_construct_common (str, len, pstr, trans, icase, dfa); 54 55 ret = re_string_realloc_buffers (pstr, init_buf_len); 56 if (BE (ret != REG_NOERROR, 0)) 57 return ret; 58 59 pstr->word_char = dfa->word_char; 60 pstr->word_ops_used = dfa->word_ops_used; 61 pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str; 62 pstr->valid_len = (pstr->mbs_allocated || dfa->mb_cur_max > 1) ? 0 : len; 63 pstr->valid_raw_len = pstr->valid_len; 64 return REG_NOERROR; 65 } 66 67 /* This function allocate the buffers, and initialize them. */ 68 69 static reg_errcode_t 70 internal_function 71 re_string_construct (re_string_t *pstr, const char *str, Idx len, 72 REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) 73 { 74 reg_errcode_t ret; 75 memset (pstr, '\0', sizeof (re_string_t)); 76 re_string_construct_common (str, len, pstr, trans, icase, dfa); 77 78 if (len > 0) 79 { 80 ret = re_string_realloc_buffers (pstr, len + 1); 81 if (BE (ret != REG_NOERROR, 0)) 82 return ret; 83 } 84 pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str; 85 86 if (icase) 87 { 88 #ifdef RE_ENABLE_I18N 89 if (dfa->mb_cur_max > 1) 90 { 91 while (1) 92 { 93 ret = build_wcs_upper_buffer (pstr); 94 if (BE (ret != REG_NOERROR, 0)) 95 return ret; 96 if (pstr->valid_raw_len >= len) 97 break; 98 if (pstr->bufs_len > pstr->valid_len + dfa->mb_cur_max) 99 break; 100 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2); 101 if (BE (ret != REG_NOERROR, 0)) 102 return ret; 103 } 104 } 105 else 106 #endif /* RE_ENABLE_I18N */ 107 build_upper_buffer (pstr); 108 } 109 else 110 { 111 #ifdef RE_ENABLE_I18N 112 if (dfa->mb_cur_max > 1) 113 build_wcs_buffer (pstr); 114 else 115 #endif /* RE_ENABLE_I18N */ 116 { 117 if (trans != NULL) 118 re_string_translate_buffer (pstr); 119 else 120 { 121 pstr->valid_len = pstr->bufs_len; 122 pstr->valid_raw_len = pstr->bufs_len; 123 } 124 } 125 } 126 127 return REG_NOERROR; 128 } 129 130 /* Helper functions for re_string_allocate, and re_string_construct. */ 131 132 static reg_errcode_t 133 internal_function 134 re_string_realloc_buffers (re_string_t *pstr, Idx new_buf_len) 135 { 136 #ifdef RE_ENABLE_I18N 137 if (pstr->mb_cur_max > 1) 138 { 139 wint_t *new_wcs = re_xrealloc (pstr->wcs, wint_t, new_buf_len); 140 if (BE (new_wcs == NULL, 0)) 141 return REG_ESPACE; 142 pstr->wcs = new_wcs; 143 if (pstr->offsets != NULL) 144 { 145 Idx *new_offsets = re_xrealloc (pstr->offsets, Idx, new_buf_len); 146 if (BE (new_offsets == NULL, 0)) 147 return REG_ESPACE; 148 pstr->offsets = new_offsets; 149 } 150 } 151 #endif /* RE_ENABLE_I18N */ 152 if (pstr->mbs_allocated) 153 { 154 unsigned char *new_mbs = re_realloc (pstr->mbs, unsigned char, 155 new_buf_len); 156 if (BE (new_mbs == NULL, 0)) 157 return REG_ESPACE; 158 pstr->mbs = new_mbs; 159 } 160 pstr->bufs_len = new_buf_len; 161 return REG_NOERROR; 162 } 163 164 165 static void 166 internal_function 167 re_string_construct_common (const char *str, Idx len, re_string_t *pstr, 168 REG_TRANSLATE_TYPE trans, bool icase, 169 const re_dfa_t *dfa) 170 { 171 pstr->raw_mbs = (const unsigned char *) str; 172 pstr->len = len; 173 pstr->raw_len = len; 174 pstr->trans = (unsigned REG_TRANSLATE_TYPE) trans; 175 pstr->icase = icase; 176 pstr->mbs_allocated = (trans != NULL || icase); 177 pstr->mb_cur_max = dfa->mb_cur_max; 178 pstr->is_utf8 = dfa->is_utf8; 179 pstr->map_notascii = dfa->map_notascii; 180 pstr->stop = pstr->len; 181 pstr->raw_stop = pstr->stop; 182 } 183 184 #ifdef RE_ENABLE_I18N 185 186 /* Build wide character buffer PSTR->WCS. 187 If the byte sequence of the string are: 188 <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3> 189 Then wide character buffer will be: 190 <wc1> , WEOF , <wc2> , WEOF , <wc3> 191 We use WEOF for padding, they indicate that the position isn't 192 a first byte of a multibyte character. 193 194 Note that this function assumes PSTR->VALID_LEN elements are already 195 built and starts from PSTR->VALID_LEN. */ 196 197 static void 198 internal_function 199 build_wcs_buffer (re_string_t *pstr) 200 { 201 #ifdef _LIBC 202 unsigned char buf[MB_LEN_MAX]; 203 assert (MB_LEN_MAX >= pstr->mb_cur_max); 204 #else 205 unsigned char buf[64]; 206 #endif 207 mbstate_t prev_st; 208 Idx byte_idx, end_idx, remain_len; 209 size_t mbclen; 210 211 /* Build the buffers from pstr->valid_len to either pstr->len or 212 pstr->bufs_len. */ 213 end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; 214 for (byte_idx = pstr->valid_len; byte_idx < end_idx;) 215 { 216 wchar_t wc; 217 const char *p; 218 219 remain_len = end_idx - byte_idx; 220 prev_st = pstr->cur_state; 221 /* Apply the translation if we need. */ 222 if (BE (pstr->trans != NULL, 0)) 223 { 224 int i, ch; 225 226 for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i) 227 { 228 ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i]; 229 buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch]; 230 } 231 p = (const char *) buf; 232 } 233 else 234 p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx; 235 mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state); 236 if (BE (mbclen == (size_t) -2, 0)) 237 { 238 /* The buffer doesn't have enough space, finish to build. */ 239 pstr->cur_state = prev_st; 240 break; 241 } 242 else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0)) 243 { 244 /* We treat these cases as a singlebyte character. */ 245 mbclen = 1; 246 wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]; 247 if (BE (pstr->trans != NULL, 0)) 248 wc = pstr->trans[wc]; 249 pstr->cur_state = prev_st; 250 } 251 252 /* Write wide character and padding. */ 253 pstr->wcs[byte_idx++] = wc; 254 /* Write paddings. */ 255 for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) 256 pstr->wcs[byte_idx++] = WEOF; 257 } 258 pstr->valid_len = byte_idx; 259 pstr->valid_raw_len = byte_idx; 260 } 261 262 /* Build wide character buffer PSTR->WCS like build_wcs_buffer, 263 but for REG_ICASE. */ 264 265 static reg_errcode_t 266 internal_function 267 build_wcs_upper_buffer (re_string_t *pstr) 268 { 269 mbstate_t prev_st; 270 Idx src_idx, byte_idx, end_idx, remain_len; 271 size_t mbclen; 272 #ifdef _LIBC 273 char buf[MB_LEN_MAX]; 274 assert (MB_LEN_MAX >= pstr->mb_cur_max); 275 #else 276 char buf[64]; 277 #endif 278 279 byte_idx = pstr->valid_len; 280 end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; 281 282 /* The following optimization assumes that ASCII characters can be 283 mapped to wide characters with a simple cast. */ 284 if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed) 285 { 286 while (byte_idx < end_idx) 287 { 288 wchar_t wc; 289 290 if (isascii (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]) 291 && mbsinit (&pstr->cur_state)) 292 { 293 /* In case of a singlebyte character. */ 294 pstr->mbs[byte_idx] 295 = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]); 296 /* The next step uses the assumption that wchar_t is encoded 297 ASCII-safe: all ASCII values can be converted like this. */ 298 pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx]; 299 ++byte_idx; 300 continue; 301 } 302 303 remain_len = end_idx - byte_idx; 304 prev_st = pstr->cur_state; 305 mbclen = mbrtowc (&wc, 306 ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx 307 + byte_idx), remain_len, &pstr->cur_state); 308 if (BE ((size_t) (mbclen + 2) > 2, 1)) 309 { 310 wchar_t wcu = wc; 311 if (iswlower (wc)) 312 { 313 size_t mbcdlen; 314 315 wcu = towupper (wc); 316 mbcdlen = wcrtomb (buf, wcu, &prev_st); 317 if (BE (mbclen == mbcdlen, 1)) 318 memcpy (pstr->mbs + byte_idx, buf, mbclen); 319 else 320 { 321 src_idx = byte_idx; 322 goto offsets_needed; 323 } 324 } 325 else 326 memcpy (pstr->mbs + byte_idx, 327 pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen); 328 pstr->wcs[byte_idx++] = wcu; 329 /* Write paddings. */ 330 for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) 331 pstr->wcs[byte_idx++] = WEOF; 332 } 333 else if (mbclen == (size_t) -1 || mbclen == 0) 334 { 335 /* It is an invalid character or '\0'. Just use the byte. */ 336 int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]; 337 pstr->mbs[byte_idx] = ch; 338 /* And also cast it to wide char. */ 339 pstr->wcs[byte_idx++] = (wchar_t) ch; 340 if (BE (mbclen == (size_t) -1, 0)) 341 pstr->cur_state = prev_st; 342 } 343 else 344 { 345 /* The buffer doesn't have enough space, finish to build. */ 346 pstr->cur_state = prev_st; 347 break; 348 } 349 } 350 pstr->valid_len = byte_idx; 351 pstr->valid_raw_len = byte_idx; 352 return REG_NOERROR; 353 } 354 else 355 for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;) 356 { 357 wchar_t wc; 358 const char *p; 359 offsets_needed: 360 remain_len = end_idx - byte_idx; 361 prev_st = pstr->cur_state; 362 if (BE (pstr->trans != NULL, 0)) 363 { 364 int i, ch; 365 366 for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i) 367 { 368 ch = pstr->raw_mbs [pstr->raw_mbs_idx + src_idx + i]; 369 buf[i] = pstr->trans[ch]; 370 } 371 p = (const char *) buf; 372 } 373 else 374 p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx; 375 mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state); 376 if (BE ((size_t) (mbclen + 2) > 2, 1)) 377 { 378 wchar_t wcu = wc; 379 if (iswlower (wc)) 380 { 381 size_t mbcdlen; 382 383 wcu = towupper (wc); 384 mbcdlen = wcrtomb ((char *) buf, wcu, &prev_st); 385 if (BE (mbclen == mbcdlen, 1)) 386 memcpy (pstr->mbs + byte_idx, buf, mbclen); 387 else if (mbcdlen != (size_t) -1) 388 { 389 size_t i; 390 391 if (byte_idx + mbcdlen > pstr->bufs_len) 392 { 393 pstr->cur_state = prev_st; 394 break; 395 } 396 397 if (pstr->offsets == NULL) 398 { 399 pstr->offsets = re_xmalloc (Idx, pstr->bufs_len); 400 401 if (pstr->offsets == NULL) 402 return REG_ESPACE; 403 } 404 if (!pstr->offsets_needed) 405 { 406 for (i = 0; i < (size_t) byte_idx; ++i) 407 pstr->offsets[i] = i; 408 pstr->offsets_needed = 1; 409 } 410 411 memcpy (pstr->mbs + byte_idx, buf, mbcdlen); 412 pstr->wcs[byte_idx] = wcu; 413 pstr->offsets[byte_idx] = src_idx; 414 for (i = 1; i < mbcdlen; ++i) 415 { 416 pstr->offsets[byte_idx + i] 417 = src_idx + (i < mbclen ? i : mbclen - 1); 418 pstr->wcs[byte_idx + i] = WEOF; 419 } 420 pstr->len += mbcdlen - mbclen; 421 if (pstr->raw_stop > src_idx) 422 pstr->stop += mbcdlen - mbclen; 423 end_idx = (pstr->bufs_len > pstr->len) 424 ? pstr->len : pstr->bufs_len; 425 byte_idx += mbcdlen; 426 src_idx += mbclen; 427 continue; 428 } 429 else 430 memcpy (pstr->mbs + byte_idx, p, mbclen); 431 } 432 else 433 memcpy (pstr->mbs + byte_idx, p, mbclen); 434 435 if (BE (pstr->offsets_needed != 0, 0)) 436 { 437 size_t i; 438 for (i = 0; i < mbclen; ++i) 439 pstr->offsets[byte_idx + i] = src_idx + i; 440 } 441 src_idx += mbclen; 442 443 pstr->wcs[byte_idx++] = wcu; 444 /* Write paddings. */ 445 for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) 446 pstr->wcs[byte_idx++] = WEOF; 447 } 448 else if (mbclen == (size_t) -1 || mbclen == 0) 449 { 450 /* It is an invalid character or '\0'. Just use the byte. */ 451 int ch = pstr->raw_mbs[pstr->raw_mbs_idx + src_idx]; 452 453 if (BE (pstr->trans != NULL, 0)) 454 ch = pstr->trans [ch]; 455 pstr->mbs[byte_idx] = ch; 456 457 if (BE (pstr->offsets_needed != 0, 0)) 458 pstr->offsets[byte_idx] = src_idx; 459 ++src_idx; 460 461 /* And also cast it to wide char. */ 462 pstr->wcs[byte_idx++] = (wchar_t) ch; 463 if (BE (mbclen == (size_t) -1, 0)) 464 pstr->cur_state = prev_st; 465 } 466 else 467 { 468 /* The buffer doesn't have enough space, finish to build. */ 469 pstr->cur_state = prev_st; 470 break; 471 } 472 } 473 pstr->valid_len = byte_idx; 474 pstr->valid_raw_len = src_idx; 475 return REG_NOERROR; 476 } 477 478 /* Skip characters until the index becomes greater than NEW_RAW_IDX. 479 Return the index. */ 480 481 static Idx 482 internal_function 483 re_string_skip_chars (re_string_t *pstr, Idx new_raw_idx, wint_t *last_wc) 484 { 485 mbstate_t prev_st; 486 Idx rawbuf_idx; 487 size_t mbclen; 488 wchar_t wc = 0; 489 490 /* Skip the characters which are not necessary to check. */ 491 for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len; 492 rawbuf_idx < new_raw_idx;) 493 { 494 Idx remain_len; 495 remain_len = pstr->len - rawbuf_idx; 496 prev_st = pstr->cur_state; 497 mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx, 498 remain_len, &pstr->cur_state); 499 if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0)) 500 { 501 /* We treat these cases as a singlebyte character. */ 502 mbclen = 1; 503 pstr->cur_state = prev_st; 504 } 505 /* Then proceed the next character. */ 506 rawbuf_idx += mbclen; 507 } 508 *last_wc = (wint_t) wc; 509 return rawbuf_idx; 510 } 511 #endif /* RE_ENABLE_I18N */ 512 513 /* Build the buffer PSTR->MBS, and apply the translation if we need. 514 This function is used in case of REG_ICASE. */ 515 516 static void 517 internal_function 518 build_upper_buffer (re_string_t *pstr) 519 { 520 Idx char_idx, end_idx; 521 end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; 522 523 for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx) 524 { 525 int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx]; 526 if (BE (pstr->trans != NULL, 0)) 527 ch = pstr->trans[ch]; 528 if (islower (ch)) 529 pstr->mbs[char_idx] = toupper (ch); 530 else 531 pstr->mbs[char_idx] = ch; 532 } 533 pstr->valid_len = char_idx; 534 pstr->valid_raw_len = char_idx; 535 } 536 537 /* Apply TRANS to the buffer in PSTR. */ 538 539 static void 540 internal_function 541 re_string_translate_buffer (re_string_t *pstr) 542 { 543 Idx buf_idx, end_idx; 544 end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; 545 546 for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx) 547 { 548 int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx]; 549 pstr->mbs[buf_idx] = pstr->trans[ch]; 550 } 551 552 pstr->valid_len = buf_idx; 553 pstr->valid_raw_len = buf_idx; 554 } 555 556 /* This function re-construct the buffers. 557 Concretely, convert to wide character in case of pstr->mb_cur_max > 1, 558 convert to upper case in case of REG_ICASE, apply translation. */ 559 560 static reg_errcode_t 561 internal_function 562 re_string_reconstruct (re_string_t *pstr, Idx idx, int eflags) 563 { 564 Idx offset; 565 566 if (BE (pstr->raw_mbs_idx <= idx, 0)) 567 offset = idx - pstr->raw_mbs_idx; 568 else 569 { 570 /* Reset buffer. */ 571 #ifdef RE_ENABLE_I18N 572 if (pstr->mb_cur_max > 1) 573 memset (&pstr->cur_state, '\0', sizeof (mbstate_t)); 574 #endif /* RE_ENABLE_I18N */ 575 pstr->len = pstr->raw_len; 576 pstr->stop = pstr->raw_stop; 577 pstr->valid_len = 0; 578 pstr->raw_mbs_idx = 0; 579 pstr->valid_raw_len = 0; 580 pstr->offsets_needed = 0; 581 pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF 582 : CONTEXT_NEWLINE | CONTEXT_BEGBUF); 583 if (!pstr->mbs_allocated) 584 pstr->mbs = (unsigned char *) pstr->raw_mbs; 585 offset = idx; 586 } 587 588 if (BE (offset != 0, 1)) 589 { 590 /* Are the characters which are already checked remain? */ 591 if (BE (offset < pstr->valid_raw_len, 1) 592 #ifdef RE_ENABLE_I18N 593 /* Handling this would enlarge the code too much. 594 Accept a slowdown in that case. */ 595 && pstr->offsets_needed == 0 596 #endif 597 ) 598 { 599 /* Yes, move them to the front of the buffer. */ 600 pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags); 601 #ifdef RE_ENABLE_I18N 602 if (pstr->mb_cur_max > 1) 603 memmove (pstr->wcs, pstr->wcs + offset, 604 (pstr->valid_len - offset) * sizeof (wint_t)); 605 #endif /* RE_ENABLE_I18N */ 606 if (BE (pstr->mbs_allocated, 0)) 607 memmove (pstr->mbs, pstr->mbs + offset, 608 pstr->valid_len - offset); 609 pstr->valid_len -= offset; 610 pstr->valid_raw_len -= offset; 611 #if DEBUG 612 assert (pstr->valid_len > 0); 613 #endif 614 } 615 else 616 { 617 /* No, skip all characters until IDX. */ 618 #ifdef RE_ENABLE_I18N 619 if (BE (pstr->offsets_needed, 0)) 620 { 621 pstr->len = pstr->raw_len - idx + offset; 622 pstr->stop = pstr->raw_stop - idx + offset; 623 pstr->offsets_needed = 0; 624 } 625 #endif 626 pstr->valid_len = 0; 627 pstr->valid_raw_len = 0; 628 #ifdef RE_ENABLE_I18N 629 if (pstr->mb_cur_max > 1) 630 { 631 Idx wcs_idx; 632 wint_t wc = WEOF; 633 634 if (pstr->is_utf8) 635 { 636 const unsigned char *raw, *p, *q, *end; 637 638 /* Special case UTF-8. Multi-byte chars start with any 639 byte other than 0x80 - 0xbf. */ 640 raw = pstr->raw_mbs + pstr->raw_mbs_idx; 641 end = raw + (offset - pstr->mb_cur_max); 642 for (p = raw + offset - 1; p >= end; --p) 643 if ((*p & 0xc0) != 0x80) 644 { 645 mbstate_t cur_state; 646 wchar_t wc2; 647 Idx mlen = raw + pstr->len - p; 648 unsigned char buf[6]; 649 size_t mbclen; 650 651 q = p; 652 if (BE (pstr->trans != NULL, 0)) 653 { 654 int i = mlen < 6 ? mlen : 6; 655 while (--i >= 0) 656 buf[i] = pstr->trans[p[i]]; 657 q = buf; 658 } 659 /* XXX Don't use mbrtowc, we know which conversion 660 to use (UTF-8 -> UCS4). */ 661 memset (&cur_state, 0, sizeof (cur_state)); 662 mbclen = mbrtowc (&wc2, (const char *) p, mlen, 663 &cur_state); 664 if (raw + offset - p <= mbclen && mbclen < (size_t) -2) 665 { 666 memset (&pstr->cur_state, '\0', 667 sizeof (mbstate_t)); 668 pstr->valid_len = mbclen - (raw + offset - p); 669 wc = wc2; 670 } 671 break; 672 } 673 } 674 675 if (wc == WEOF) 676 pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx; 677 if (BE (pstr->valid_len, 0)) 678 { 679 for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx) 680 pstr->wcs[wcs_idx] = WEOF; 681 if (pstr->mbs_allocated) 682 memset (pstr->mbs, -1, pstr->valid_len); 683 } 684 pstr->valid_raw_len = pstr->valid_len; 685 pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0) 686 && IS_WIDE_WORD_CHAR (wc)) 687 ? CONTEXT_WORD 688 : ((IS_WIDE_NEWLINE (wc) 689 && pstr->newline_anchor) 690 ? CONTEXT_NEWLINE : 0)); 691 } 692 else 693 #endif /* RE_ENABLE_I18N */ 694 { 695 int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1]; 696 if (pstr->trans) 697 c = pstr->trans[c]; 698 pstr->tip_context = (bitset_contain (pstr->word_char, c) 699 ? CONTEXT_WORD 700 : ((IS_NEWLINE (c) && pstr->newline_anchor) 701 ? CONTEXT_NEWLINE : 0)); 702 } 703 } 704 if (!BE (pstr->mbs_allocated, 0)) 705 pstr->mbs += offset; 706 } 707 pstr->raw_mbs_idx = idx; 708 pstr->len -= offset; 709 pstr->stop -= offset; 710 711 /* Then build the buffers. */ 712 #ifdef RE_ENABLE_I18N 713 if (pstr->mb_cur_max > 1) 714 { 715 if (pstr->icase) 716 { 717 reg_errcode_t ret = build_wcs_upper_buffer (pstr); 718 if (BE (ret != REG_NOERROR, 0)) 719 return ret; 720 } 721 else 722 build_wcs_buffer (pstr); 723 } 724 else 725 #endif /* RE_ENABLE_I18N */ 726 if (BE (pstr->mbs_allocated, 0)) 727 { 728 if (pstr->icase) 729 build_upper_buffer (pstr); 730 else if (pstr->trans != NULL) 731 re_string_translate_buffer (pstr); 732 } 733 else 734 pstr->valid_len = pstr->len; 735 736 pstr->cur_idx = 0; 737 return REG_NOERROR; 738 } 739 740 static unsigned char 741 internal_function __attribute ((pure)) 742 re_string_peek_byte_case (const re_string_t *pstr, Idx idx) 743 { 744 int ch; 745 Idx off; 746 747 /* Handle the common (easiest) cases first. */ 748 if (BE (!pstr->mbs_allocated, 1)) 749 return re_string_peek_byte (pstr, idx); 750 751 #ifdef RE_ENABLE_I18N 752 if (pstr->mb_cur_max > 1 753 && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx)) 754 return re_string_peek_byte (pstr, idx); 755 #endif 756 757 off = pstr->cur_idx + idx; 758 #ifdef RE_ENABLE_I18N 759 if (pstr->offsets_needed) 760 off = pstr->offsets[off]; 761 #endif 762 763 ch = pstr->raw_mbs[pstr->raw_mbs_idx + off]; 764 765 #ifdef RE_ENABLE_I18N 766 /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I 767 this function returns CAPITAL LETTER I instead of first byte of 768 DOTLESS SMALL LETTER I. The latter would confuse the parser, 769 since peek_byte_case doesn't advance cur_idx in any way. */ 770 if (pstr->offsets_needed && !isascii (ch)) 771 return re_string_peek_byte (pstr, idx); 772 #endif 773 774 return ch; 775 } 776 777 static unsigned char 778 internal_function __attribute ((pure)) 779 re_string_fetch_byte_case (re_string_t *pstr) 780 { 781 if (BE (!pstr->mbs_allocated, 1)) 782 return re_string_fetch_byte (pstr); 783 784 #ifdef RE_ENABLE_I18N 785 if (pstr->offsets_needed) 786 { 787 Idx off; 788 int ch; 789 790 /* For tr_TR.UTF-8 [[:islower:]] there is 791 [[: CAPITAL LETTER I WITH DOT lower:]] in mbs. Skip 792 in that case the whole multi-byte character and return 793 the original letter. On the other side, with 794 [[: DOTLESS SMALL LETTER I return [[:I, as doing 795 anything else would complicate things too much. */ 796 797 if (!re_string_first_byte (pstr, pstr->cur_idx)) 798 return re_string_fetch_byte (pstr); 799 800 off = pstr->offsets[pstr->cur_idx]; 801 ch = pstr->raw_mbs[pstr->raw_mbs_idx + off]; 802 803 if (! isascii (ch)) 804 return re_string_fetch_byte (pstr); 805 806 re_string_skip_bytes (pstr, 807 re_string_char_size_at (pstr, pstr->cur_idx)); 808 return ch; 809 } 810 #endif 811 812 return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++]; 813 } 814 815 static void 816 internal_function 817 re_string_destruct (re_string_t *pstr) 818 { 819 #ifdef RE_ENABLE_I18N 820 re_free (pstr->wcs); 821 re_free (pstr->offsets); 822 #endif /* RE_ENABLE_I18N */ 823 if (pstr->mbs_allocated) 824 re_free (pstr->mbs); 825 } 826 827 /* Return the context at IDX in INPUT. */ 828 829 static unsigned int 830 internal_function 831 re_string_context_at (const re_string_t *input, Idx idx, int eflags) 832 { 833 int c; 834 if (BE (! REG_VALID_INDEX (idx), 0)) 835 /* In this case, we use the value stored in input->tip_context, 836 since we can't know the character in input->mbs[-1] here. */ 837 return input->tip_context; 838 if (BE (idx == input->len, 0)) 839 return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF 840 : CONTEXT_NEWLINE | CONTEXT_ENDBUF); 841 #ifdef RE_ENABLE_I18N 842 if (input->mb_cur_max > 1) 843 { 844 wint_t wc; 845 Idx wc_idx = idx; 846 while(input->wcs[wc_idx] == WEOF) 847 { 848 #ifdef DEBUG 849 /* It must not happen. */ 850 assert (REG_VALID_INDEX (wc_idx)); 851 #endif 852 --wc_idx; 853 if (! REG_VALID_INDEX (wc_idx)) 854 return input->tip_context; 855 } 856 wc = input->wcs[wc_idx]; 857 if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc)) 858 return CONTEXT_WORD; 859 return (IS_WIDE_NEWLINE (wc) && input->newline_anchor 860 ? CONTEXT_NEWLINE : 0); 861 } 862 else 863 #endif 864 { 865 c = re_string_byte_at (input, idx); 866 if (bitset_contain (input->word_char, c)) 867 return CONTEXT_WORD; 868 return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0; 869 } 870 } 871 872 /* Functions for set operation. */ 874 875 static reg_errcode_t 876 internal_function 877 re_node_set_alloc (re_node_set *set, Idx size) 878 { 879 set->alloc = size; 880 set->nelem = 0; 881 set->elems = re_xmalloc (Idx, size); 882 if (BE (set->elems == NULL, 0)) 883 return REG_ESPACE; 884 return REG_NOERROR; 885 } 886 887 static reg_errcode_t 888 internal_function 889 re_node_set_init_1 (re_node_set *set, Idx elem) 890 { 891 set->alloc = 1; 892 set->nelem = 1; 893 set->elems = re_malloc (Idx, 1); 894 if (BE (set->elems == NULL, 0)) 895 { 896 set->alloc = set->nelem = 0; 897 return REG_ESPACE; 898 } 899 set->elems[0] = elem; 900 return REG_NOERROR; 901 } 902 903 static reg_errcode_t 904 internal_function 905 re_node_set_init_2 (re_node_set *set, Idx elem1, Idx elem2) 906 { 907 set->alloc = 2; 908 set->elems = re_malloc (Idx, 2); 909 if (BE (set->elems == NULL, 0)) 910 return REG_ESPACE; 911 if (elem1 == elem2) 912 { 913 set->nelem = 1; 914 set->elems[0] = elem1; 915 } 916 else 917 { 918 set->nelem = 2; 919 if (elem1 < elem2) 920 { 921 set->elems[0] = elem1; 922 set->elems[1] = elem2; 923 } 924 else 925 { 926 set->elems[0] = elem2; 927 set->elems[1] = elem1; 928 } 929 } 930 return REG_NOERROR; 931 } 932 933 static reg_errcode_t 934 internal_function 935 re_node_set_init_copy (re_node_set *dest, const re_node_set *src) 936 { 937 dest->nelem = src->nelem; 938 if (src->nelem > 0) 939 { 940 dest->alloc = dest->nelem; 941 dest->elems = re_malloc (Idx, dest->alloc); 942 if (BE (dest->elems == NULL, 0)) 943 { 944 dest->alloc = dest->nelem = 0; 945 return REG_ESPACE; 946 } 947 memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]); 948 } 949 else 950 re_node_set_init_empty (dest); 951 return REG_NOERROR; 952 } 953 954 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to 955 DEST. Return value indicate the error code or REG_NOERROR if succeeded. 956 Note: We assume dest->elems is NULL, when dest->alloc is 0. */ 957 958 static reg_errcode_t 959 internal_function 960 re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, 961 const re_node_set *src2) 962 { 963 Idx i1, i2, is, id, delta, sbase; 964 if (src1->nelem == 0 || src2->nelem == 0) 965 return REG_NOERROR; 966 967 /* We need dest->nelem + 2 * elems_in_intersection; this is a 968 conservative estimate. */ 969 if (src1->nelem + src2->nelem + dest->nelem > dest->alloc) 970 { 971 Idx new_alloc = src1->nelem + src2->nelem + dest->alloc; 972 Idx *new_elems; 973 if (sizeof (Idx) < 3 974 && (new_alloc < dest->alloc 975 || ((Idx) (src1->nelem + src2->nelem) < src1->nelem))) 976 return REG_ESPACE; 977 new_elems = re_xrealloc (dest->elems, Idx, new_alloc); 978 if (BE (new_elems == NULL, 0)) 979 return REG_ESPACE; 980 dest->elems = new_elems; 981 dest->alloc = new_alloc; 982 } 983 984 /* Find the items in the intersection of SRC1 and SRC2, and copy 985 into the top of DEST those that are not already in DEST itself. */ 986 sbase = dest->nelem + src1->nelem + src2->nelem; 987 i1 = src1->nelem - 1; 988 i2 = src2->nelem - 1; 989 id = dest->nelem - 1; 990 for (;;) 991 { 992 if (src1->elems[i1] == src2->elems[i2]) 993 { 994 /* Try to find the item in DEST. Maybe we could binary search? */ 995 while (REG_VALID_INDEX (id) && dest->elems[id] > src1->elems[i1]) 996 --id; 997 998 if (! REG_VALID_INDEX (id) || dest->elems[id] != src1->elems[i1]) 999 dest->elems[--sbase] = src1->elems[i1]; 1000 1001 if (! REG_VALID_INDEX (--i1) || ! REG_VALID_INDEX (--i2)) 1002 break; 1003 } 1004 1005 /* Lower the highest of the two items. */ 1006 else if (src1->elems[i1] < src2->elems[i2]) 1007 { 1008 if (! REG_VALID_INDEX (--i2)) 1009 break; 1010 } 1011 else 1012 { 1013 if (! REG_VALID_INDEX (--i1)) 1014 break; 1015 } 1016 } 1017 1018 id = dest->nelem - 1; 1019 is = dest->nelem + src1->nelem + src2->nelem - 1; 1020 delta = is - sbase + 1; 1021 1022 /* Now copy. When DELTA becomes zero, the remaining 1023 DEST elements are already in place; this is more or 1024 less the same loop that is in re_node_set_merge. */ 1025 dest->nelem += delta; 1026 if (delta > 0 && REG_VALID_INDEX (id)) 1027 for (;;) 1028 { 1029 if (dest->elems[is] > dest->elems[id]) 1030 { 1031 /* Copy from the top. */ 1032 dest->elems[id + delta--] = dest->elems[is--]; 1033 if (delta == 0) 1034 break; 1035 } 1036 else 1037 { 1038 /* Slide from the bottom. */ 1039 dest->elems[id + delta] = dest->elems[id]; 1040 if (! REG_VALID_INDEX (--id)) 1041 break; 1042 } 1043 } 1044 1045 /* Copy remaining SRC elements. */ 1046 memcpy (dest->elems, dest->elems + sbase, delta * sizeof dest->elems[0]); 1047 1048 return REG_NOERROR; 1049 } 1050 1051 /* Calculate the union set of the sets SRC1 and SRC2. And store it to 1052 DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ 1053 1054 static reg_errcode_t 1055 internal_function 1056 re_node_set_init_union (re_node_set *dest, const re_node_set *src1, 1057 const re_node_set *src2) 1058 { 1059 Idx i1, i2, id; 1060 if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0) 1061 { 1062 dest->alloc = src1->nelem + src2->nelem; 1063 if (sizeof (Idx) < 2 && dest->alloc < src1->nelem) 1064 return REG_ESPACE; 1065 dest->elems = re_xmalloc (Idx, dest->alloc); 1066 if (BE (dest->elems == NULL, 0)) 1067 return REG_ESPACE; 1068 } 1069 else 1070 { 1071 if (src1 != NULL && src1->nelem > 0) 1072 return re_node_set_init_copy (dest, src1); 1073 else if (src2 != NULL && src2->nelem > 0) 1074 return re_node_set_init_copy (dest, src2); 1075 else 1076 re_node_set_init_empty (dest); 1077 return REG_NOERROR; 1078 } 1079 for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;) 1080 { 1081 if (src1->elems[i1] > src2->elems[i2]) 1082 { 1083 dest->elems[id++] = src2->elems[i2++]; 1084 continue; 1085 } 1086 if (src1->elems[i1] == src2->elems[i2]) 1087 ++i2; 1088 dest->elems[id++] = src1->elems[i1++]; 1089 } 1090 if (i1 < src1->nelem) 1091 { 1092 memcpy (dest->elems + id, src1->elems + i1, 1093 (src1->nelem - i1) * sizeof dest->elems[0]); 1094 id += src1->nelem - i1; 1095 } 1096 else if (i2 < src2->nelem) 1097 { 1098 memcpy (dest->elems + id, src2->elems + i2, 1099 (src2->nelem - i2) * sizeof dest->elems[0]); 1100 id += src2->nelem - i2; 1101 } 1102 dest->nelem = id; 1103 return REG_NOERROR; 1104 } 1105 1106 /* Calculate the union set of the sets DEST and SRC. And store it to 1107 DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ 1108 1109 static reg_errcode_t 1110 internal_function 1111 re_node_set_merge (re_node_set *dest, const re_node_set *src) 1112 { 1113 Idx is, id, sbase, delta; 1114 if (src == NULL || src->nelem == 0) 1115 return REG_NOERROR; 1116 if (sizeof (Idx) < 3 1117 && ((Idx) (2 * src->nelem) < src->nelem 1118 || (Idx) (2 * src->nelem + dest->nelem) < dest->nelem)) 1119 return REG_ESPACE; 1120 if (dest->alloc < 2 * src->nelem + dest->nelem) 1121 { 1122 Idx new_alloc = src->nelem + dest->alloc; 1123 Idx *new_buffer; 1124 if (sizeof (Idx) < 4 && new_alloc < dest->alloc) 1125 return REG_ESPACE; 1126 new_buffer = re_x2realloc (dest->elems, Idx, &new_alloc); 1127 if (BE (new_buffer == NULL, 0)) 1128 return REG_ESPACE; 1129 dest->elems = new_buffer; 1130 dest->alloc = new_alloc; 1131 } 1132 1133 if (BE (dest->nelem == 0, 0)) 1134 { 1135 dest->nelem = src->nelem; 1136 memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]); 1137 return REG_NOERROR; 1138 } 1139 1140 /* Copy into the top of DEST the items of SRC that are not 1141 found in DEST. Maybe we could binary search in DEST? */ 1142 for (sbase = dest->nelem + 2 * src->nelem, 1143 is = src->nelem - 1, id = dest->nelem - 1; 1144 REG_VALID_INDEX (is) && REG_VALID_INDEX (id); ) 1145 { 1146 if (dest->elems[id] == src->elems[is]) 1147 is--, id--; 1148 else if (dest->elems[id] < src->elems[is]) 1149 dest->elems[--sbase] = src->elems[is--]; 1150 else /* if (dest->elems[id] > src->elems[is]) */ 1151 --id; 1152 } 1153 1154 if (REG_VALID_INDEX (is)) 1155 { 1156 /* If DEST is exhausted, the remaining items of SRC must be unique. */ 1157 sbase -= is + 1; 1158 memcpy (dest->elems + sbase, src->elems, 1159 (is + 1) * sizeof dest->elems[0]); 1160 } 1161 1162 id = dest->nelem - 1; 1163 is = dest->nelem + 2 * src->nelem - 1; 1164 delta = is - sbase + 1; 1165 if (delta == 0) 1166 return REG_NOERROR; 1167 1168 /* Now copy. When DELTA becomes zero, the remaining 1169 DEST elements are already in place. */ 1170 dest->nelem += delta; 1171 for (;;) 1172 { 1173 if (dest->elems[is] > dest->elems[id]) 1174 { 1175 /* Copy from the top. */ 1176 dest->elems[id + delta--] = dest->elems[is--]; 1177 if (delta == 0) 1178 break; 1179 } 1180 else 1181 { 1182 /* Slide from the bottom. */ 1183 dest->elems[id + delta] = dest->elems[id]; 1184 if (! REG_VALID_INDEX (--id)) 1185 { 1186 /* Copy remaining SRC elements. */ 1187 memcpy (dest->elems, dest->elems + sbase, 1188 delta * sizeof dest->elems[0]); 1189 break; 1190 } 1191 } 1192 } 1193 1194 return REG_NOERROR; 1195 } 1196 1197 /* Insert the new element ELEM to the re_node_set* SET. 1198 SET should not already have ELEM. 1199 Return true if successful. */ 1200 1201 static bool 1202 internal_function 1203 re_node_set_insert (re_node_set *set, Idx elem) 1204 { 1205 Idx idx; 1206 /* In case the set is empty. */ 1207 if (set->alloc == 0) 1208 return re_node_set_init_1 (set, elem) == REG_NOERROR; 1209 1210 if (BE (set->nelem, 0) == 0) 1211 { 1212 /* We already guaranteed above that set->alloc != 0. */ 1213 set->elems[0] = elem; 1214 ++set->nelem; 1215 return true; 1216 } 1217 1218 /* Realloc if we need. */ 1219 if (set->alloc == set->nelem) 1220 { 1221 Idx *new_elems = re_x2realloc (set->elems, Idx, &set->alloc); 1222 if (BE (new_elems == NULL, 0)) 1223 return false; 1224 set->elems = new_elems; 1225 } 1226 1227 /* Move the elements which follows the new element. Test the 1228 first element separately to skip a check in the inner loop. */ 1229 if (elem < set->elems[0]) 1230 { 1231 idx = 0; 1232 for (idx = set->nelem; idx > 0; idx--) 1233 set->elems[idx] = set->elems[idx - 1]; 1234 } 1235 else 1236 { 1237 for (idx = set->nelem; set->elems[idx - 1] > elem; idx--) 1238 set->elems[idx] = set->elems[idx - 1]; 1239 } 1240 1241 /* Insert the new element. */ 1242 set->elems[idx] = elem; 1243 ++set->nelem; 1244 return true; 1245 } 1246 1247 /* Insert the new element ELEM to the re_node_set* SET. 1248 SET should not already have any element greater than or equal to ELEM. 1249 Return true if successful. */ 1250 1251 static bool 1252 internal_function 1253 re_node_set_insert_last (re_node_set *set, Idx elem) 1254 { 1255 /* Realloc if we need. */ 1256 if (set->alloc == set->nelem) 1257 { 1258 Idx *new_elems; 1259 new_elems = re_x2realloc (set->elems, Idx, &set->alloc); 1260 if (BE (new_elems == NULL, 0)) 1261 return false; 1262 set->elems = new_elems; 1263 } 1264 1265 /* Insert the new element. */ 1266 set->elems[set->nelem++] = elem; 1267 return true; 1268 } 1269 1270 /* Compare two node sets SET1 and SET2. 1271 Return true if SET1 and SET2 are equivalent. */ 1272 1273 static bool 1274 internal_function __attribute ((pure)) 1275 re_node_set_compare (const re_node_set *set1, const re_node_set *set2) 1276 { 1277 Idx i; 1278 if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem) 1279 return false; 1280 for (i = set1->nelem ; REG_VALID_INDEX (--i) ; ) 1281 if (set1->elems[i] != set2->elems[i]) 1282 return false; 1283 return true; 1284 } 1285 1286 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise. */ 1287 1288 static Idx 1289 internal_function __attribute ((pure)) 1290 re_node_set_contains (const re_node_set *set, Idx elem) 1291 { 1292 __re_size_t idx, right, mid; 1293 if (! REG_VALID_NONZERO_INDEX (set->nelem)) 1294 return 0; 1295 1296 /* Binary search the element. */ 1297 idx = 0; 1298 right = set->nelem - 1; 1299 while (idx < right) 1300 { 1301 mid = (idx + right) / 2; 1302 if (set->elems[mid] < elem) 1303 idx = mid + 1; 1304 else 1305 right = mid; 1306 } 1307 return set->elems[idx] == elem ? idx + 1 : 0; 1308 } 1309 1310 static void 1311 internal_function 1312 re_node_set_remove_at (re_node_set *set, Idx idx) 1313 { 1314 if (idx < 0 || idx >= set->nelem) 1315 return; 1316 --set->nelem; 1317 for (; idx < set->nelem; idx++) 1318 set->elems[idx] = set->elems[idx + 1]; 1319 } 1320 1321 1323 /* Add the token TOKEN to dfa->nodes, and return the index of the token. 1324 Or return REG_MISSING if an error occurred. */ 1325 1326 static Idx 1327 internal_function 1328 re_dfa_add_node (re_dfa_t *dfa, re_token_t token) 1329 { 1330 int type = token.type; 1331 if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0)) 1332 { 1333 Idx new_nodes_alloc = dfa->nodes_alloc; 1334 Idx *new_nexts, *new_indices; 1335 re_node_set *new_edests, *new_eclosures; 1336 1337 re_token_t *new_nodes = re_x2realloc (dfa->nodes, re_token_t, 1338 &new_nodes_alloc); 1339 if (BE (new_nodes == NULL, 0)) 1340 return REG_MISSING; 1341 dfa->nodes = new_nodes; 1342 new_nexts = re_realloc (dfa->nexts, Idx, new_nodes_alloc); 1343 new_indices = re_realloc (dfa->org_indices, Idx, new_nodes_alloc); 1344 new_edests = re_xrealloc (dfa->edests, re_node_set, new_nodes_alloc); 1345 new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc); 1346 if (BE (new_nexts == NULL || new_indices == NULL 1347 || new_edests == NULL || new_eclosures == NULL, 0)) 1348 return REG_MISSING; 1349 dfa->nexts = new_nexts; 1350 dfa->org_indices = new_indices; 1351 dfa->edests = new_edests; 1352 dfa->eclosures = new_eclosures; 1353 dfa->nodes_alloc = new_nodes_alloc; 1354 } 1355 dfa->nodes[dfa->nodes_len] = token; 1356 dfa->nodes[dfa->nodes_len].constraint = 0; 1357 #ifdef RE_ENABLE_I18N 1358 dfa->nodes[dfa->nodes_len].accept_mb = 1359 (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET; 1360 #endif 1361 dfa->nexts[dfa->nodes_len] = REG_MISSING; 1362 re_node_set_init_empty (dfa->edests + dfa->nodes_len); 1363 re_node_set_init_empty (dfa->eclosures + dfa->nodes_len); 1364 return dfa->nodes_len++; 1365 } 1366 1367 static inline re_hashval_t 1368 internal_function 1369 calc_state_hash (const re_node_set *nodes, unsigned int context) 1370 { 1371 re_hashval_t hash = nodes->nelem + context; 1372 Idx i; 1373 for (i = 0 ; i < nodes->nelem ; i++) 1374 hash += nodes->elems[i]; 1375 return hash; 1376 } 1377 1378 /* Search for the state whose node_set is equivalent to NODES. 1379 Return the pointer to the state, if we found it in the DFA. 1380 Otherwise create the new one and return it. In case of an error 1381 return NULL and set the error code in ERR. 1382 Note: - We assume NULL as the invalid state, then it is possible that 1383 return value is NULL and ERR is REG_NOERROR. 1384 - We never return non-NULL value in case of any errors, it is for 1385 optimization. */ 1386 1387 static re_dfastate_t* 1388 internal_function 1389 re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) 1390 { 1391 re_hashval_t hash; 1392 re_dfastate_t *new_state; 1393 struct re_state_table_entry *spot; 1394 Idx i; 1395 #ifdef lint 1396 /* Suppress bogus uninitialized-variable warnings. */ 1397 *err = REG_NOERROR; 1398 #endif 1399 if (BE (nodes->nelem == 0, 0)) 1400 { 1401 *err = REG_NOERROR; 1402 return NULL; 1403 } 1404 hash = calc_state_hash (nodes, 0); 1405 spot = dfa->state_table + (hash & dfa->state_hash_mask); 1406 1407 for (i = 0 ; i < spot->num ; i++) 1408 { 1409 re_dfastate_t *state = spot->array[i]; 1410 if (hash != state->hash) 1411 continue; 1412 if (re_node_set_compare (&state->nodes, nodes)) 1413 return state; 1414 } 1415 1416 /* There are no appropriate state in the dfa, create the new one. */ 1417 new_state = create_ci_newstate (dfa, nodes, hash); 1418 if (BE (new_state != NULL, 1)) 1419 return new_state; 1420 else 1421 { 1422 *err = REG_ESPACE; 1423 return NULL; 1424 } 1425 } 1426 1427 /* Search for the state whose node_set is equivalent to NODES and 1428 whose context is equivalent to CONTEXT. 1429 Return the pointer to the state, if we found it in the DFA. 1430 Otherwise create the new one and return it. In case of an error 1431 return NULL and set the error code in ERR. 1432 Note: - We assume NULL as the invalid state, then it is possible that 1433 return value is NULL and ERR is REG_NOERROR. 1434 - We never return non-NULL value in case of any errors, it is for 1435 optimization. */ 1436 1437 static re_dfastate_t* 1438 internal_function 1439 re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, 1440 const re_node_set *nodes, unsigned int context) 1441 { 1442 re_hashval_t hash; 1443 re_dfastate_t *new_state; 1444 struct re_state_table_entry *spot; 1445 Idx i; 1446 #ifdef lint 1447 /* Suppress bogus uninitialized-variable warnings. */ 1448 *err = REG_NOERROR; 1449 #endif 1450 if (nodes->nelem == 0) 1451 { 1452 *err = REG_NOERROR; 1453 return NULL; 1454 } 1455 hash = calc_state_hash (nodes, context); 1456 spot = dfa->state_table + (hash & dfa->state_hash_mask); 1457 1458 for (i = 0 ; i < spot->num ; i++) 1459 { 1460 re_dfastate_t *state = spot->array[i]; 1461 if (state->hash == hash 1462 && state->context == context 1463 && re_node_set_compare (state->entrance_nodes, nodes)) 1464 return state; 1465 } 1466 /* There are no appropriate state in `dfa', create the new one. */ 1467 new_state = create_cd_newstate (dfa, nodes, context, hash); 1468 if (BE (new_state != NULL, 1)) 1469 return new_state; 1470 else 1471 { 1472 *err = REG_ESPACE; 1473 return NULL; 1474 } 1475 } 1476 1477 /* Finish initialization of the new state NEWSTATE, and using its hash value 1478 HASH put in the appropriate bucket of DFA's state table. Return value 1479 indicates the error code if failed. */ 1480 1481 static reg_errcode_t 1482 internal_function 1483 register_state (const re_dfa_t *dfa, re_dfastate_t *newstate, re_hashval_t hash) 1484 { 1485 struct re_state_table_entry *spot; 1486 reg_errcode_t err; 1487 Idx i; 1488 1489 newstate->hash = hash; 1490 err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem); 1491 if (BE (err != REG_NOERROR, 0)) 1492 return REG_ESPACE; 1493 for (i = 0; i < newstate->nodes.nelem; i++) 1494 { 1495 Idx elem = newstate->nodes.elems[i]; 1496 if (!IS_EPSILON_NODE (dfa->nodes[elem].type)) 1497 { 1498 bool ok = re_node_set_insert_last (&newstate->non_eps_nodes, elem); 1499 if (BE (! ok, 0)) 1500 return REG_ESPACE; 1501 } 1502 } 1503 1504 spot = dfa->state_table + (hash & dfa->state_hash_mask); 1505 if (BE (spot->alloc <= spot->num, 0)) 1506 { 1507 Idx new_alloc = spot->num; 1508 re_dfastate_t **new_array = re_x2realloc (spot->array, re_dfastate_t *, 1509 &new_alloc); 1510 if (BE (new_array == NULL, 0)) 1511 return REG_ESPACE; 1512 spot->array = new_array; 1513 spot->alloc = new_alloc; 1514 } 1515 spot->array[spot->num++] = newstate; 1516 return REG_NOERROR; 1517 } 1518 1519 /* Create the new state which is independ of contexts. 1520 Return the new state if succeeded, otherwise return NULL. */ 1521 1522 static re_dfastate_t * 1523 internal_function 1524 create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, 1525 re_hashval_t hash) 1526 { 1527 Idx i; 1528 reg_errcode_t err; 1529 re_dfastate_t *newstate; 1530 1531 newstate = re_calloc (re_dfastate_t, 1); 1532 if (BE (newstate == NULL, 0)) 1533 return NULL; 1534 err = re_node_set_init_copy (&newstate->nodes, nodes); 1535 if (BE (err != REG_NOERROR, 0)) 1536 { 1537 re_free (newstate); 1538 return NULL; 1539 } 1540 1541 newstate->entrance_nodes = &newstate->nodes; 1542 for (i = 0 ; i < nodes->nelem ; i++) 1543 { 1544 re_token_t *node = dfa->nodes + nodes->elems[i]; 1545 re_token_type_t type = node->type; 1546 if (type == CHARACTER && !node->constraint) 1547 continue; 1548 #ifdef RE_ENABLE_I18N 1549 newstate->accept_mb |= node->accept_mb; 1550 #endif /* RE_ENABLE_I18N */ 1551 1552 /* If the state has the halt node, the state is a halt state. */ 1553 if (type == END_OF_RE) 1554 newstate->halt = 1; 1555 else if (type == OP_BACK_REF) 1556 newstate->has_backref = 1; 1557 else if (type == ANCHOR || node->constraint) 1558 newstate->has_constraint = 1; 1559 } 1560 err = register_state (dfa, newstate, hash); 1561 if (BE (err != REG_NOERROR, 0)) 1562 { 1563 free_state (newstate); 1564 newstate = NULL; 1565 } 1566 return newstate; 1567 } 1568 1569 /* Create the new state which is depend on the context CONTEXT. 1570 Return the new state if succeeded, otherwise return NULL. */ 1571 1572 static re_dfastate_t * 1573 internal_function 1574 create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, 1575 unsigned int context, re_hashval_t hash) 1576 { 1577 Idx i, nctx_nodes = 0; 1578 reg_errcode_t err; 1579 re_dfastate_t *newstate; 1580 1581 newstate = re_calloc (re_dfastate_t, 1); 1582 if (BE (newstate == NULL, 0)) 1583 return NULL; 1584 err = re_node_set_init_copy (&newstate->nodes, nodes); 1585 if (BE (err != REG_NOERROR, 0)) 1586 { 1587 re_free (newstate); 1588 return NULL; 1589 } 1590 1591 newstate->context = context; 1592 newstate->entrance_nodes = &newstate->nodes; 1593 1594 for (i = 0 ; i < nodes->nelem ; i++) 1595 { 1596 unsigned int constraint = 0; 1597 re_token_t *node = dfa->nodes + nodes->elems[i]; 1598 re_token_type_t type = node->type; 1599 if (node->constraint) 1600 constraint = node->constraint; 1601 1602 if (type == CHARACTER && !constraint) 1603 continue; 1604 #ifdef RE_ENABLE_I18N 1605 newstate->accept_mb |= node->accept_mb; 1606 #endif /* RE_ENABLE_I18N */ 1607 1608 /* If the state has the halt node, the state is a halt state. */ 1609 if (type == END_OF_RE) 1610 newstate->halt = 1; 1611 else if (type == OP_BACK_REF) 1612 newstate->has_backref = 1; 1613 else if (type == ANCHOR) 1614 constraint = node->opr.ctx_type; 1615 1616 if (constraint) 1617 { 1618 if (newstate->entrance_nodes == &newstate->nodes) 1619 { 1620 newstate->entrance_nodes = re_malloc (re_node_set, 1); 1621 if (BE (newstate->entrance_nodes == NULL, 0)) 1622 { 1623 free_state (newstate); 1624 return NULL; 1625 } 1626 re_node_set_init_copy (newstate->entrance_nodes, nodes); 1627 nctx_nodes = 0; 1628 newstate->has_constraint = 1; 1629 } 1630 1631 if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context)) 1632 { 1633 re_node_set_remove_at (&newstate->nodes, i - nctx_nodes); 1634 ++nctx_nodes; 1635 } 1636 } 1637 } 1638 err = register_state (dfa, newstate, hash); 1639 if (BE (err != REG_NOERROR, 0)) 1640 { 1641 free_state (newstate); 1642 newstate = NULL; 1643 } 1644 return newstate; 1645 } 1646 1647 static void 1648 internal_function 1649 free_state (re_dfastate_t *state) 1650 { 1651 re_node_set_free (&state->non_eps_nodes); 1652 re_node_set_free (&state->inveclosure); 1653 if (state->entrance_nodes != &state->nodes) 1654 { 1655 re_node_set_free (state->entrance_nodes); 1656 re_free (state->entrance_nodes); 1657 } 1658 re_node_set_free (&state->nodes); 1659 re_free (state->word_trtable); 1660 re_free (state->trtable); 1661 re_free (state); 1662 } 1663
Indexes created Wed Jul 22 00:25:13 UTC 2026