X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fregex_internal.c;h=26c5dc60ba642e6c37d20f3829efeb8d7ce5deb6;hb=56d6664559f449af25f0d331457b014b02324d65;hp=385de6ffc2111cf2d9e357071b4bfe05e2ad3c42;hpb=576ad3853e771fde0041056dcdbffb6702db7dc0;p=gnulib.git diff --git a/lib/regex_internal.c b/lib/regex_internal.c index 385de6ffc..26c5dc60b 100644 --- a/lib/regex_internal.c +++ b/lib/regex_internal.c @@ -1,5 +1,5 @@ /* Extended regular expression matching and search library. - Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2002-2011 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Isamu Hasegawa . @@ -17,17 +17,17 @@ with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -static void re_string_construct_common (const char *str, int len, +static void re_string_construct_common (const char *str, Idx len, re_string_t *pstr, - RE_TRANSLATE_TYPE trans, int icase, + RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) internal_function; -static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa, +static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, - unsigned int hash) internal_function; -static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa, + re_hashval_t hash) internal_function; +static re_dfastate_t *create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, unsigned int context, - unsigned int hash) internal_function; + re_hashval_t hash) internal_function; /* Functions for string operation. */ @@ -35,12 +35,12 @@ static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa, re_string_reconstruct before using the object. */ static reg_errcode_t -internal_function -re_string_allocate (re_string_t *pstr, const char *str, int len, int init_len, - RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) +internal_function __attribute_warn_unused_result__ +re_string_allocate (re_string_t *pstr, const char *str, Idx len, Idx init_len, + RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { reg_errcode_t ret; - int init_buf_len; + Idx init_buf_len; /* Ensure at least one character fits into the buffers. */ if (init_len < dfa->mb_cur_max) @@ -63,9 +63,9 @@ re_string_allocate (re_string_t *pstr, const char *str, int len, int init_len, /* This function allocate the buffers, and initialize them. */ static reg_errcode_t -internal_function -re_string_construct (re_string_t *pstr, const char *str, int len, - RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) +internal_function __attribute_warn_unused_result__ +re_string_construct (re_string_t *pstr, const char *str, Idx len, + RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { reg_errcode_t ret; memset (pstr, '\0', sizeof (re_string_t)); @@ -126,19 +126,26 @@ re_string_construct (re_string_t *pstr, const char *str, int len, /* Helper functions for re_string_allocate, and re_string_construct. */ static reg_errcode_t -internal_function -re_string_realloc_buffers (re_string_t *pstr, int new_buf_len) +internal_function __attribute_warn_unused_result__ +re_string_realloc_buffers (re_string_t *pstr, Idx new_buf_len) { #ifdef RE_ENABLE_I18N if (pstr->mb_cur_max > 1) { - wint_t *new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len); + wint_t *new_wcs; + + /* Avoid overflow. */ + size_t max_object_size = MAX (sizeof (wint_t), sizeof (Idx)); + if (BE (SIZE_MAX / max_object_size < new_buf_len, 0)) + return REG_ESPACE; + + new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len); if (BE (new_wcs == NULL, 0)) return REG_ESPACE; pstr->wcs = new_wcs; if (pstr->offsets != NULL) { - int *new_offsets = re_realloc (pstr->offsets, int, new_buf_len); + Idx *new_offsets = re_realloc (pstr->offsets, Idx, new_buf_len); if (BE (new_offsets == NULL, 0)) return REG_ESPACE; pstr->offsets = new_offsets; @@ -160,15 +167,15 @@ re_string_realloc_buffers (re_string_t *pstr, int new_buf_len) static void internal_function -re_string_construct_common (const char *str, int len, re_string_t *pstr, - RE_TRANSLATE_TYPE trans, int icase, +re_string_construct_common (const char *str, Idx len, re_string_t *pstr, + RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { pstr->raw_mbs = (const unsigned char *) str; pstr->len = len; pstr->raw_len = len; - pstr->trans = (unsigned RE_TRANSLATE_TYPE) trans; - pstr->icase = icase ? 1 : 0; + pstr->trans = trans; + pstr->icase = icase; pstr->mbs_allocated = (trans != NULL || icase); pstr->mb_cur_max = dfa->mb_cur_max; pstr->is_utf8 = dfa->is_utf8; @@ -201,7 +208,7 @@ build_wcs_buffer (re_string_t *pstr) unsigned char buf[64]; #endif mbstate_t prev_st; - int byte_idx, end_idx, remain_len; + Idx byte_idx, end_idx, remain_len; size_t mbclen; /* Build the buffers from pstr->valid_len to either pstr->len or @@ -228,7 +235,7 @@ build_wcs_buffer (re_string_t *pstr) } else p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx; - mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state); + mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state); if (BE (mbclen == (size_t) -2, 0)) { /* The buffer doesn't have enough space, finish to build. */ @@ -258,12 +265,12 @@ build_wcs_buffer (re_string_t *pstr) /* Build wide character buffer PSTR->WCS like build_wcs_buffer, but for REG_ICASE. */ -static int -internal_function +static reg_errcode_t +internal_function __attribute_warn_unused_result__ build_wcs_upper_buffer (re_string_t *pstr) { mbstate_t prev_st; - int src_idx, byte_idx, end_idx, remain_len; + Idx src_idx, byte_idx, end_idx, remain_len; size_t mbclen; #ifdef _LIBC char buf[MB_LEN_MAX]; @@ -298,10 +305,10 @@ build_wcs_upper_buffer (re_string_t *pstr) remain_len = end_idx - byte_idx; prev_st = pstr->cur_state; - mbclen = mbrtowc (&wc, - ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx - + byte_idx), remain_len, &pstr->cur_state); - if (BE (mbclen + 2 > 2, 1)) + mbclen = __mbrtowc (&wc, + ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx + + byte_idx), remain_len, &pstr->cur_state); + if (BE (mbclen < (size_t) -2, 1)) { wchar_t wcu = wc; if (iswlower (wc)) @@ -368,8 +375,8 @@ build_wcs_upper_buffer (re_string_t *pstr) } else p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx; - mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state); - if (BE (mbclen + 2 > 2, 1)) + mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state); + if (BE (mbclen < (size_t) -2, 1)) { wchar_t wcu = wc; if (iswlower (wc)) @@ -392,7 +399,7 @@ build_wcs_upper_buffer (re_string_t *pstr) if (pstr->offsets == NULL) { - pstr->offsets = re_malloc (int, pstr->bufs_len); + pstr->offsets = re_malloc (Idx, pstr->bufs_len); if (pstr->offsets == NULL) return REG_ESPACE; @@ -422,8 +429,8 @@ build_wcs_upper_buffer (re_string_t *pstr) src_idx += mbclen; continue; } - else - memcpy (pstr->mbs + byte_idx, p, mbclen); + else + memcpy (pstr->mbs + byte_idx, p, mbclen); } else memcpy (pstr->mbs + byte_idx, p, mbclen); @@ -474,34 +481,41 @@ build_wcs_upper_buffer (re_string_t *pstr) /* Skip characters until the index becomes greater than NEW_RAW_IDX. Return the index. */ -static int +static Idx internal_function -re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc) +re_string_skip_chars (re_string_t *pstr, Idx new_raw_idx, wint_t *last_wc) { mbstate_t prev_st; - int rawbuf_idx; + Idx rawbuf_idx; size_t mbclen; - wchar_t wc = 0; + wint_t wc = WEOF; /* Skip the characters which are not necessary to check. */ for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len; rawbuf_idx < new_raw_idx;) { - int remain_len; + wchar_t wc2; + Idx remain_len; remain_len = pstr->len - rawbuf_idx; prev_st = pstr->cur_state; - mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx, - remain_len, &pstr->cur_state); + mbclen = __mbrtowc (&wc2, (const char *) pstr->raw_mbs + rawbuf_idx, + remain_len, &pstr->cur_state); if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0)) { - /* We treat these cases as a singlebyte character. */ + /* We treat these cases as a single byte character. */ + if (mbclen == 0 || remain_len == 0) + wc = L'\0'; + else + wc = *(unsigned char *) (pstr->raw_mbs + rawbuf_idx); mbclen = 1; pstr->cur_state = prev_st; } + else + wc = wc2; /* Then proceed the next character. */ rawbuf_idx += mbclen; } - *last_wc = (wint_t) wc; + *last_wc = wc; return rawbuf_idx; } #endif /* RE_ENABLE_I18N */ @@ -513,7 +527,7 @@ static void internal_function build_upper_buffer (re_string_t *pstr) { - int char_idx, end_idx; + Idx char_idx, end_idx; end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx) @@ -536,7 +550,7 @@ static void internal_function re_string_translate_buffer (re_string_t *pstr) { - int buf_idx, end_idx; + Idx buf_idx, end_idx; end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx) @@ -554,11 +568,14 @@ re_string_translate_buffer (re_string_t *pstr) convert to upper case in case of REG_ICASE, apply translation. */ static reg_errcode_t -internal_function -re_string_reconstruct (re_string_t *pstr, int idx, int eflags) +internal_function __attribute_warn_unused_result__ +re_string_reconstruct (re_string_t *pstr, Idx idx, int eflags) { - int offset = idx - pstr->raw_mbs_idx; - if (BE (offset < 0, 0)) + Idx offset; + + if (BE (pstr->raw_mbs_idx <= idx, 0)) + offset = idx - pstr->raw_mbs_idx; + else { /* Reset buffer. */ #ifdef RE_ENABLE_I18N @@ -580,35 +597,99 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) if (BE (offset != 0, 1)) { - /* Are the characters which are already checked remain? */ - if (BE (offset < pstr->valid_raw_len, 1) -#ifdef RE_ENABLE_I18N - /* Handling this would enlarge the code too much. - Accept a slowdown in that case. */ - && pstr->offsets_needed == 0 -#endif - ) + /* Should the already checked characters be kept? */ + if (BE (offset < pstr->valid_raw_len, 1)) { /* Yes, move them to the front of the buffer. */ - pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags); #ifdef RE_ENABLE_I18N - if (pstr->mb_cur_max > 1) - memmove (pstr->wcs, pstr->wcs + offset, - (pstr->valid_len - offset) * sizeof (wint_t)); + if (BE (pstr->offsets_needed, 0)) + { + Idx low = 0, high = pstr->valid_len, mid; + do + { + mid = (high + low) / 2; + if (pstr->offsets[mid] > offset) + high = mid; + else if (pstr->offsets[mid] < offset) + low = mid + 1; + else + break; + } + while (low < high); + if (pstr->offsets[mid] < offset) + ++mid; + pstr->tip_context = re_string_context_at (pstr, mid - 1, + eflags); + /* This can be quite complicated, so handle specially + only the common and easy case where the character with + different length representation of lower and upper + case is present at or after offset. */ + if (pstr->valid_len > offset + && mid == offset && pstr->offsets[mid] == offset) + { + memmove (pstr->wcs, pstr->wcs + offset, + (pstr->valid_len - offset) * sizeof (wint_t)); + memmove (pstr->mbs, pstr->mbs + offset, pstr->valid_len - offset); + pstr->valid_len -= offset; + pstr->valid_raw_len -= offset; + for (low = 0; low < pstr->valid_len; low++) + pstr->offsets[low] = pstr->offsets[low + offset] - offset; + } + else + { + /* Otherwise, just find out how long the partial multibyte + character at offset is and fill it with WEOF/255. */ + pstr->len = pstr->raw_len - idx + offset; + pstr->stop = pstr->raw_stop - idx + offset; + pstr->offsets_needed = 0; + while (mid > 0 && pstr->offsets[mid - 1] == offset) + --mid; + while (mid < pstr->valid_len) + if (pstr->wcs[mid] != WEOF) + break; + else + ++mid; + if (mid == pstr->valid_len) + pstr->valid_len = 0; + else + { + pstr->valid_len = pstr->offsets[mid] - offset; + if (pstr->valid_len) + { + for (low = 0; low < pstr->valid_len; ++low) + pstr->wcs[low] = WEOF; + memset (pstr->mbs, 255, pstr->valid_len); + } + } + pstr->valid_raw_len = pstr->valid_len; + } + } + else +#endif + { + pstr->tip_context = re_string_context_at (pstr, offset - 1, + eflags); +#ifdef RE_ENABLE_I18N + if (pstr->mb_cur_max > 1) + memmove (pstr->wcs, pstr->wcs + offset, + (pstr->valid_len - offset) * sizeof (wint_t)); #endif /* RE_ENABLE_I18N */ - if (BE (pstr->mbs_allocated, 0)) - memmove (pstr->mbs, pstr->mbs + offset, - pstr->valid_len - offset); - pstr->valid_len -= offset; - pstr->valid_raw_len -= offset; + if (BE (pstr->mbs_allocated, 0)) + memmove (pstr->mbs, pstr->mbs + offset, + pstr->valid_len - offset); + pstr->valid_len -= offset; + pstr->valid_raw_len -= offset; #if DEBUG - assert (pstr->valid_len > 0); + assert (pstr->valid_len > 0); #endif + } } else { - /* No, skip all characters until IDX. */ #ifdef RE_ENABLE_I18N + /* No, skip all characters until IDX. */ + Idx prev_valid_len = pstr->valid_len; + if (BE (pstr->offsets_needed, 0)) { pstr->len = pstr->raw_len - idx + offset; @@ -617,56 +698,80 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) } #endif pstr->valid_len = 0; - pstr->valid_raw_len = 0; #ifdef RE_ENABLE_I18N if (pstr->mb_cur_max > 1) { - int wcs_idx; + Idx wcs_idx; wint_t wc = WEOF; if (pstr->is_utf8) { - const unsigned char *raw, *p, *q, *end; + const unsigned char *raw, *p, *end; /* Special case UTF-8. Multi-byte chars start with any byte other than 0x80 - 0xbf. */ raw = pstr->raw_mbs + pstr->raw_mbs_idx; end = raw + (offset - pstr->mb_cur_max); - for (p = raw + offset - 1; p >= end; --p) - if ((*p & 0xc0) != 0x80) - { - mbstate_t cur_state; - wchar_t wc2; - int mlen = raw + pstr->len - p; - unsigned char buf[6]; - - q = p; - if (BE (pstr->trans != NULL, 0)) - { - int i = mlen < 6 ? mlen : 6; - while (--i >= 0) - buf[i] = pstr->trans[p[i]]; - q = buf; - } - /* XXX Don't use mbrtowc, we know which conversion - to use (UTF-8 -> UCS4). */ - memset (&cur_state, 0, sizeof (cur_state)); - mlen = (mbrtowc (&wc2, (const char *) p, mlen, - &cur_state) - - (raw + offset - p)); - if (mlen >= 0) - { - memset (&pstr->cur_state, '\0', - sizeof (mbstate_t)); - pstr->valid_len = mlen; - wc = wc2; - } - break; - } + if (end < pstr->raw_mbs) + end = pstr->raw_mbs; + p = raw + offset - 1; +#ifdef _LIBC + /* We know the wchar_t encoding is UCS4, so for the simple + case, ASCII characters, skip the conversion step. */ + if (isascii (*p) && BE (pstr->trans == NULL, 1)) + { + memset (&pstr->cur_state, '\0', sizeof (mbstate_t)); + /* pstr->valid_len = 0; */ + wc = (wchar_t) *p; + } + else +#endif + for (; p >= end; --p) + if ((*p & 0xc0) != 0x80) + { + mbstate_t cur_state; + wchar_t wc2; + Idx mlen = raw + pstr->len - p; + size_t mbclen; + +#if 0 /* dead code: buf is set but never used */ + unsigned char buf[6]; + if (BE (pstr->trans != NULL, 0)) + { + int i = mlen < 6 ? mlen : 6; + while (--i >= 0) + buf[i] = pstr->trans[p[i]]; + } +#endif + /* XXX Don't use mbrtowc, we know which conversion + to use (UTF-8 -> UCS4). */ + memset (&cur_state, 0, sizeof (cur_state)); + mbclen = __mbrtowc (&wc2, (const char *) p, mlen, + &cur_state); + if (raw + offset - p <= mbclen + && mbclen < (size_t) -2) + { + memset (&pstr->cur_state, '\0', + sizeof (mbstate_t)); + pstr->valid_len = mbclen - (raw + offset - p); + wc = wc2; + } + break; + } } if (wc == WEOF) pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx; + if (wc == WEOF) + pstr->tip_context + = re_string_context_at (pstr, prev_valid_len - 1, eflags); + else + pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0) + && IS_WIDE_WORD_CHAR (wc)) + ? CONTEXT_WORD + : ((IS_WIDE_NEWLINE (wc) + && pstr->newline_anchor) + ? CONTEXT_NEWLINE : 0)); if (BE (pstr->valid_len, 0)) { for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx) @@ -675,17 +780,12 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) memset (pstr->mbs, 255, pstr->valid_len); } pstr->valid_raw_len = pstr->valid_len; - pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0) - && IS_WIDE_WORD_CHAR (wc)) - ? CONTEXT_WORD - : ((IS_WIDE_NEWLINE (wc) - && pstr->newline_anchor) - ? CONTEXT_NEWLINE : 0)); } else #endif /* RE_ENABLE_I18N */ { int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1]; + pstr->valid_raw_len = 0; if (pstr->trans) c = pstr->trans[c]; pstr->tip_context = (bitset_contain (pstr->word_char, c) @@ -707,7 +807,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) { if (pstr->icase) { - int ret = build_wcs_upper_buffer (pstr); + reg_errcode_t ret = build_wcs_upper_buffer (pstr); if (BE (ret != REG_NOERROR, 0)) return ret; } @@ -716,25 +816,26 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) } else #endif /* RE_ENABLE_I18N */ - if (BE (pstr->mbs_allocated, 0)) - { - if (pstr->icase) - build_upper_buffer (pstr); - else if (pstr->trans != NULL) - re_string_translate_buffer (pstr); - } - else - pstr->valid_len = pstr->len; + if (BE (pstr->mbs_allocated, 0)) + { + if (pstr->icase) + build_upper_buffer (pstr); + else if (pstr->trans != NULL) + re_string_translate_buffer (pstr); + } + else + pstr->valid_len = pstr->len; pstr->cur_idx = 0; return REG_NOERROR; } static unsigned char -internal_function -re_string_peek_byte_case (const re_string_t *pstr, int idx) +internal_function __attribute ((pure)) +re_string_peek_byte_case (const re_string_t *pstr, Idx idx) { - int ch, off; + int ch; + Idx off; /* Handle the common (easiest) cases first. */ if (BE (!pstr->mbs_allocated, 1)) @@ -767,7 +868,7 @@ re_string_peek_byte_case (const re_string_t *pstr, int idx) } static unsigned char -internal_function +internal_function __attribute ((pure)) re_string_fetch_byte_case (re_string_t *pstr) { if (BE (!pstr->mbs_allocated, 1)) @@ -776,7 +877,8 @@ re_string_fetch_byte_case (re_string_t *pstr) #ifdef RE_ENABLE_I18N if (pstr->offsets_needed) { - int off, ch; + Idx off; + int ch; /* For tr_TR.UTF-8 [[:islower:]] there is [[: CAPITAL LETTER I WITH DOT lower:]] in mbs. Skip @@ -819,10 +921,10 @@ re_string_destruct (re_string_t *pstr) static unsigned int internal_function -re_string_context_at (const re_string_t *input, int idx, int eflags) +re_string_context_at (const re_string_t *input, Idx idx, int eflags) { int c; - if (BE (idx < 0, 0)) + if (BE (! REG_VALID_INDEX (idx), 0)) /* In this case, we use the value stored in input->tip_context, since we can't know the character in input->mbs[-1] here. */ return input->tip_context; @@ -833,15 +935,15 @@ re_string_context_at (const re_string_t *input, int idx, int eflags) if (input->mb_cur_max > 1) { wint_t wc; - int wc_idx = idx; + Idx wc_idx = idx; while(input->wcs[wc_idx] == WEOF) { #ifdef DEBUG /* It must not happen. */ - assert (wc_idx >= 0); + assert (REG_VALID_INDEX (wc_idx)); #endif --wc_idx; - if (wc_idx < 0) + if (! REG_VALID_INDEX (wc_idx)) return input->tip_context; } wc = input->wcs[wc_idx]; @@ -863,24 +965,24 @@ re_string_context_at (const re_string_t *input, int idx, int eflags) /* Functions for set operation. */ static reg_errcode_t -internal_function -re_node_set_alloc (re_node_set *set, int size) +internal_function __attribute_warn_unused_result__ +re_node_set_alloc (re_node_set *set, Idx size) { set->alloc = size; set->nelem = 0; - set->elems = re_malloc (int, size); + set->elems = re_malloc (Idx, size); if (BE (set->elems == NULL, 0)) return REG_ESPACE; return REG_NOERROR; } static reg_errcode_t -internal_function -re_node_set_init_1 (re_node_set *set, int elem) +internal_function __attribute_warn_unused_result__ +re_node_set_init_1 (re_node_set *set, Idx elem) { set->alloc = 1; set->nelem = 1; - set->elems = re_malloc (int, 1); + set->elems = re_malloc (Idx, 1); if (BE (set->elems == NULL, 0)) { set->alloc = set->nelem = 0; @@ -891,11 +993,11 @@ re_node_set_init_1 (re_node_set *set, int elem) } static reg_errcode_t -internal_function -re_node_set_init_2 (re_node_set *set, int elem1, int elem2) +internal_function __attribute_warn_unused_result__ +re_node_set_init_2 (re_node_set *set, Idx elem1, Idx elem2) { set->alloc = 2; - set->elems = re_malloc (int, 2); + set->elems = re_malloc (Idx, 2); if (BE (set->elems == NULL, 0)) return REG_ESPACE; if (elem1 == elem2) @@ -921,20 +1023,20 @@ re_node_set_init_2 (re_node_set *set, int elem1, int elem2) } static reg_errcode_t -internal_function +internal_function __attribute_warn_unused_result__ re_node_set_init_copy (re_node_set *dest, const re_node_set *src) { dest->nelem = src->nelem; if (src->nelem > 0) { dest->alloc = dest->nelem; - dest->elems = re_malloc (int, dest->alloc); + dest->elems = re_malloc (Idx, dest->alloc); if (BE (dest->elems == NULL, 0)) { dest->alloc = dest->nelem = 0; return REG_ESPACE; } - memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); + memcpy (dest->elems, src->elems, src->nelem * sizeof (Idx)); } else re_node_set_init_empty (dest); @@ -946,11 +1048,11 @@ re_node_set_init_copy (re_node_set *dest, const re_node_set *src) Note: We assume dest->elems is NULL, when dest->alloc is 0. */ static reg_errcode_t -internal_function +internal_function __attribute_warn_unused_result__ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, const re_node_set *src2) { - int i1, i2, is, id, delta, sbase; + Idx i1, i2, is, id, delta, sbase; if (src1->nelem == 0 || src2->nelem == 0) return REG_NOERROR; @@ -958,10 +1060,10 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, conservative estimate. */ if (src1->nelem + src2->nelem + dest->nelem > dest->alloc) { - int new_alloc = src1->nelem + src2->nelem + dest->alloc; - int *new_elems = re_realloc (dest->elems, int, new_alloc); + Idx new_alloc = src1->nelem + src2->nelem + dest->alloc; + Idx *new_elems = re_realloc (dest->elems, Idx, new_alloc); if (BE (new_elems == NULL, 0)) - return REG_ESPACE; + return REG_ESPACE; dest->elems = new_elems; dest->alloc = new_alloc; } @@ -977,25 +1079,25 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, if (src1->elems[i1] == src2->elems[i2]) { /* Try to find the item in DEST. Maybe we could binary search? */ - while (id >= 0 && dest->elems[id] > src1->elems[i1]) + while (REG_VALID_INDEX (id) && dest->elems[id] > src1->elems[i1]) --id; - if (id < 0 || dest->elems[id] != src1->elems[i1]) + if (! REG_VALID_INDEX (id) || dest->elems[id] != src1->elems[i1]) dest->elems[--sbase] = src1->elems[i1]; - if (--i1 < 0 || --i2 < 0) + if (! REG_VALID_INDEX (--i1) || ! REG_VALID_INDEX (--i2)) break; } /* Lower the highest of the two items. */ else if (src1->elems[i1] < src2->elems[i2]) { - if (--i2 < 0) + if (! REG_VALID_INDEX (--i2)) break; } else { - if (--i1 < 0) + if (! REG_VALID_INDEX (--i1)) break; } } @@ -1008,27 +1110,27 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, DEST elements are already in place; this is more or less the same loop that is in re_node_set_merge. */ dest->nelem += delta; - if (delta > 0 && id >= 0) + if (delta > 0 && REG_VALID_INDEX (id)) for (;;) { - if (dest->elems[is] > dest->elems[id]) - { - /* Copy from the top. */ - dest->elems[id + delta--] = dest->elems[is--]; - if (delta == 0) - break; - } - else - { - /* Slide from the bottom. */ - dest->elems[id + delta] = dest->elems[id]; - if (--id < 0) - break; - } + if (dest->elems[is] > dest->elems[id]) + { + /* Copy from the top. */ + dest->elems[id + delta--] = dest->elems[is--]; + if (delta == 0) + break; + } + else + { + /* Slide from the bottom. */ + dest->elems[id + delta] = dest->elems[id]; + if (! REG_VALID_INDEX (--id)) + break; + } } /* Copy remaining SRC elements. */ - memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int)); + memcpy (dest->elems, dest->elems + sbase, delta * sizeof (Idx)); return REG_NOERROR; } @@ -1037,15 +1139,15 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ static reg_errcode_t -internal_function +internal_function __attribute_warn_unused_result__ re_node_set_init_union (re_node_set *dest, const re_node_set *src1, const re_node_set *src2) { - int i1, i2, id; + Idx i1, i2, id; if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0) { dest->alloc = src1->nelem + src2->nelem; - dest->elems = re_malloc (int, dest->alloc); + dest->elems = re_malloc (Idx, dest->alloc); if (BE (dest->elems == NULL, 0)) return REG_ESPACE; } @@ -1073,13 +1175,13 @@ re_node_set_init_union (re_node_set *dest, const re_node_set *src1, if (i1 < src1->nelem) { memcpy (dest->elems + id, src1->elems + i1, - (src1->nelem - i1) * sizeof (int)); + (src1->nelem - i1) * sizeof (Idx)); id += src1->nelem - i1; } else if (i2 < src2->nelem) { memcpy (dest->elems + id, src2->elems + i2, - (src2->nelem - i2) * sizeof (int)); + (src2->nelem - i2) * sizeof (Idx)); id += src2->nelem - i2; } dest->nelem = id; @@ -1090,16 +1192,16 @@ re_node_set_init_union (re_node_set *dest, const re_node_set *src1, DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ static reg_errcode_t -internal_function +internal_function __attribute_warn_unused_result__ re_node_set_merge (re_node_set *dest, const re_node_set *src) { - int is, id, sbase, delta; + Idx is, id, sbase, delta; if (src == NULL || src->nelem == 0) return REG_NOERROR; if (dest->alloc < 2 * src->nelem + dest->nelem) { - int new_alloc = 2 * (src->nelem + dest->alloc); - int *new_buffer = re_realloc (dest->elems, int, new_alloc); + Idx new_alloc = 2 * (src->nelem + dest->alloc); + Idx *new_buffer = re_realloc (dest->elems, Idx, new_alloc); if (BE (new_buffer == NULL, 0)) return REG_ESPACE; dest->elems = new_buffer; @@ -1109,28 +1211,29 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) if (BE (dest->nelem == 0, 0)) { dest->nelem = src->nelem; - memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); + memcpy (dest->elems, src->elems, src->nelem * sizeof (Idx)); return REG_NOERROR; } /* Copy into the top of DEST the items of SRC that are not found in DEST. Maybe we could binary search in DEST? */ for (sbase = dest->nelem + 2 * src->nelem, - is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; ) + is = src->nelem - 1, id = dest->nelem - 1; + REG_VALID_INDEX (is) && REG_VALID_INDEX (id); ) { if (dest->elems[id] == src->elems[is]) - is--, id--; + is--, id--; else if (dest->elems[id] < src->elems[is]) - dest->elems[--sbase] = src->elems[is--]; + dest->elems[--sbase] = src->elems[is--]; else /* if (dest->elems[id] > src->elems[is]) */ - --id; + --id; } - if (is >= 0) + if (REG_VALID_INDEX (is)) { /* If DEST is exhausted, the remaining items of SRC must be unique. */ sbase -= is + 1; - memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int)); + memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (Idx)); } id = dest->nelem - 1; @@ -1145,21 +1248,21 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) for (;;) { if (dest->elems[is] > dest->elems[id]) - { + { /* Copy from the top. */ - dest->elems[id + delta--] = dest->elems[is--]; + dest->elems[id + delta--] = dest->elems[is--]; if (delta == 0) break; } else - { - /* Slide from the bottom. */ - dest->elems[id + delta] = dest->elems[id]; - if (--id < 0) + { + /* Slide from the bottom. */ + dest->elems[id + delta] = dest->elems[id]; + if (! REG_VALID_INDEX (--id)) { /* Copy remaining SRC elements. */ memcpy (dest->elems, dest->elems + sbase, - delta * sizeof (int)); + delta * sizeof (Idx)); break; } } @@ -1170,38 +1273,33 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) /* Insert the new element ELEM to the re_node_set* SET. SET should not already have ELEM. - return -1 if an error is occured, return 1 otherwise. */ + Return true if successful. */ -static int -internal_function -re_node_set_insert (re_node_set *set, int elem) +static bool +internal_function __attribute_warn_unused_result__ +re_node_set_insert (re_node_set *set, Idx elem) { - int idx; + Idx idx; /* In case the set is empty. */ if (set->alloc == 0) - { - if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1)) - return 1; - else - return -1; - } + return BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1); if (BE (set->nelem, 0) == 0) { /* We already guaranteed above that set->alloc != 0. */ set->elems[0] = elem; ++set->nelem; - return 1; + return true; } /* Realloc if we need. */ if (set->alloc == set->nelem) { - int *new_elems; + Idx *new_elems; set->alloc = set->alloc * 2; - new_elems = re_realloc (set->elems, int, set->alloc); + new_elems = re_realloc (set->elems, Idx, set->alloc); if (BE (new_elems == NULL, 0)) - return -1; + return false; set->elems = new_elems; } @@ -1211,68 +1309,68 @@ re_node_set_insert (re_node_set *set, int elem) { idx = 0; for (idx = set->nelem; idx > 0; idx--) - set->elems[idx] = set->elems[idx - 1]; + set->elems[idx] = set->elems[idx - 1]; } else { for (idx = set->nelem; set->elems[idx - 1] > elem; idx--) - set->elems[idx] = set->elems[idx - 1]; + set->elems[idx] = set->elems[idx - 1]; } /* Insert the new element. */ set->elems[idx] = elem; ++set->nelem; - return 1; + return true; } /* Insert the new element ELEM to the re_node_set* SET. SET should not already have any element greater than or equal to ELEM. - Return -1 if an error is occured, return 1 otherwise. */ + Return true if successful. */ -static int -internal_function -re_node_set_insert_last (re_node_set *set, int elem) +static bool +internal_function __attribute_warn_unused_result__ +re_node_set_insert_last (re_node_set *set, Idx elem) { /* Realloc if we need. */ if (set->alloc == set->nelem) { - int *new_elems; + Idx *new_elems; set->alloc = (set->alloc + 1) * 2; - new_elems = re_realloc (set->elems, int, set->alloc); + new_elems = re_realloc (set->elems, Idx, set->alloc); if (BE (new_elems == NULL, 0)) - return -1; + return false; set->elems = new_elems; } /* Insert the new element. */ set->elems[set->nelem++] = elem; - return 1; + return true; } /* Compare two node sets SET1 and SET2. - return 1 if SET1 and SET2 are equivalent, return 0 otherwise. */ + Return true if SET1 and SET2 are equivalent. */ -static int -internal_function +static bool +internal_function __attribute ((pure)) re_node_set_compare (const re_node_set *set1, const re_node_set *set2) { - int i; + Idx i; if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem) - return 0; - for (i = set1->nelem ; --i >= 0 ; ) + return false; + for (i = set1->nelem ; REG_VALID_INDEX (--i) ; ) if (set1->elems[i] != set2->elems[i]) - return 0; - return 1; + return false; + return true; } /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise. */ -static int -internal_function -re_node_set_contains (const re_node_set *set, int elem) +static Idx +internal_function __attribute ((pure)) +re_node_set_contains (const re_node_set *set, Idx elem) { - unsigned int idx, right, mid; - if (set->nelem <= 0) + __re_size_t idx, right, mid; + if (! REG_VALID_NONZERO_INDEX (set->nelem)) return 0; /* Binary search the element. */ @@ -1291,7 +1389,7 @@ re_node_set_contains (const re_node_set *set, int elem) static void internal_function -re_node_set_remove_at (re_node_set *set, int idx) +re_node_set_remove_at (re_node_set *set, Idx idx) { if (idx < 0 || idx >= set->nelem) return; @@ -1302,31 +1400,38 @@ re_node_set_remove_at (re_node_set *set, int idx) /* Add the token TOKEN to dfa->nodes, and return the index of the token. - Or return -1, if an error will be occured. */ + Or return REG_MISSING if an error occurred. */ -static int +static Idx internal_function re_dfa_add_node (re_dfa_t *dfa, re_token_t token) { - int type = token.type; if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0)) { - int new_nodes_alloc = dfa->nodes_alloc * 2; - int *new_nexts, *new_indices; + size_t new_nodes_alloc = dfa->nodes_alloc * 2; + Idx *new_nexts, *new_indices; re_node_set *new_edests, *new_eclosures; + re_token_t *new_nodes; + size_t max_object_size = + MAX (sizeof (re_token_t), + MAX (sizeof (re_node_set), + sizeof (Idx))); + + /* Avoid overflows. */ + if (BE (SIZE_MAX / 2 / max_object_size < dfa->nodes_alloc, 0)) + return REG_MISSING; - re_token_t *new_nodes = re_realloc (dfa->nodes, re_token_t, - new_nodes_alloc); + new_nodes = re_realloc (dfa->nodes, re_token_t, new_nodes_alloc); if (BE (new_nodes == NULL, 0)) - return -1; + return REG_MISSING; dfa->nodes = new_nodes; - new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc); - new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc); + new_nexts = re_realloc (dfa->nexts, Idx, new_nodes_alloc); + new_indices = re_realloc (dfa->org_indices, Idx, new_nodes_alloc); new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc); new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc); if (BE (new_nexts == NULL || new_indices == NULL || new_edests == NULL || new_eclosures == NULL, 0)) - return -1; + return REG_MISSING; dfa->nexts = new_nexts; dfa->org_indices = new_indices; dfa->edests = new_edests; @@ -1336,21 +1441,24 @@ re_dfa_add_node (re_dfa_t *dfa, re_token_t token) dfa->nodes[dfa->nodes_len] = token; dfa->nodes[dfa->nodes_len].constraint = 0; #ifdef RE_ENABLE_I18N + { + int type = token.type; dfa->nodes[dfa->nodes_len].accept_mb = (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET; + } #endif - dfa->nexts[dfa->nodes_len] = -1; + dfa->nexts[dfa->nodes_len] = REG_MISSING; re_node_set_init_empty (dfa->edests + dfa->nodes_len); re_node_set_init_empty (dfa->eclosures + dfa->nodes_len); return dfa->nodes_len++; } -static inline unsigned int +static inline re_hashval_t internal_function calc_state_hash (const re_node_set *nodes, unsigned int context) { - unsigned int hash = nodes->nelem + context; - int i; + re_hashval_t hash = nodes->nelem + context; + Idx i; for (i = 0 ; i < nodes->nelem ; i++) hash += nodes->elems[i]; return hash; @@ -1365,14 +1473,15 @@ calc_state_hash (const re_node_set *nodes, unsigned int context) - We never return non-NULL value in case of any errors, it is for optimization. */ -static re_dfastate_t* -internal_function -re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) +static re_dfastate_t * +internal_function __attribute_warn_unused_result__ +re_acquire_state (reg_errcode_t *err, const re_dfa_t *dfa, + const re_node_set *nodes) { - unsigned int hash; + re_hashval_t hash; re_dfastate_t *new_state; struct re_state_table_entry *spot; - int i; + Idx i; #ifdef lint /* Suppress bogus uninitialized-variable warnings. */ *err = REG_NOERROR; @@ -1396,13 +1505,10 @@ re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) /* There are no appropriate state in the dfa, create the new one. */ new_state = create_ci_newstate (dfa, nodes, hash); - if (BE (new_state != NULL, 1)) - return new_state; - else - { - *err = REG_ESPACE; - return NULL; - } + if (BE (new_state == NULL, 0)) + *err = REG_ESPACE; + + return new_state; } /* Search for the state whose node_set is equivalent to NODES and @@ -1415,15 +1521,15 @@ re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) - We never return non-NULL value in case of any errors, it is for optimization. */ -static re_dfastate_t* -internal_function -re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, +static re_dfastate_t * +internal_function __attribute_warn_unused_result__ +re_acquire_state_context (reg_errcode_t *err, const re_dfa_t *dfa, const re_node_set *nodes, unsigned int context) { - unsigned int hash; + re_hashval_t hash; re_dfastate_t *new_state; struct re_state_table_entry *spot; - int i; + Idx i; #ifdef lint /* Suppress bogus uninitialized-variable warnings. */ *err = REG_NOERROR; @@ -1446,13 +1552,10 @@ re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, } /* There are no appropriate state in `dfa', create the new one. */ new_state = create_cd_newstate (dfa, nodes, context, hash); - if (BE (new_state != NULL, 1)) - return new_state; - else - { - *err = REG_ESPACE; - return NULL; - } + if (BE (new_state == NULL, 0)) + *err = REG_ESPACE; + + return new_state; } /* Finish initialization of the new state NEWSTATE, and using its hash value @@ -1460,12 +1563,13 @@ re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, indicates the error code if failed. */ static reg_errcode_t -internal_function -register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) +__attribute_warn_unused_result__ +register_state (const re_dfa_t *dfa, re_dfastate_t *newstate, + re_hashval_t hash) { struct re_state_table_entry *spot; reg_errcode_t err; - int i; + Idx i; newstate->hash = hash; err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem); @@ -1473,15 +1577,16 @@ register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) return REG_ESPACE; for (i = 0; i < newstate->nodes.nelem; i++) { - int elem = newstate->nodes.elems[i]; + Idx elem = newstate->nodes.elems[i]; if (!IS_EPSILON_NODE (dfa->nodes[elem].type)) - re_node_set_insert_last (&newstate->non_eps_nodes, elem); + if (BE (! re_node_set_insert_last (&newstate->non_eps_nodes, elem), 0)) + return REG_ESPACE; } spot = dfa->state_table + (hash & dfa->state_hash_mask); if (BE (spot->alloc <= spot->num, 0)) { - int new_alloc = 2 * spot->num + 2; + Idx new_alloc = 2 * spot->num + 2; re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *, new_alloc); if (BE (new_array == NULL, 0)) @@ -1493,14 +1598,31 @@ register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) return REG_NOERROR; } +static void +free_state (re_dfastate_t *state) +{ + re_node_set_free (&state->non_eps_nodes); + re_node_set_free (&state->inveclosure); + if (state->entrance_nodes != &state->nodes) + { + re_node_set_free (state->entrance_nodes); + re_free (state->entrance_nodes); + } + re_node_set_free (&state->nodes); + re_free (state->word_trtable); + re_free (state->trtable); + re_free (state); +} + /* Create the new state which is independ of contexts. Return the new state if succeeded, otherwise return NULL. */ static re_dfastate_t * -internal_function -create_ci_newstate (re_dfa_t *dfa, const re_node_set *nodes, unsigned int hash) +internal_function __attribute_warn_unused_result__ +create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, + re_hashval_t hash) { - int i; + Idx i; reg_errcode_t err; re_dfastate_t *newstate; @@ -1546,11 +1668,11 @@ create_ci_newstate (re_dfa_t *dfa, const re_node_set *nodes, unsigned int hash) Return the new state if succeeded, otherwise return NULL. */ static re_dfastate_t * -internal_function -create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, - unsigned int context, unsigned int hash) +internal_function __attribute_warn_unused_result__ +create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, + unsigned int context, re_hashval_t hash) { - int i, nctx_nodes = 0; + Idx i, nctx_nodes = 0; reg_errcode_t err; re_dfastate_t *newstate; @@ -1569,11 +1691,9 @@ create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, for (i = 0 ; i < nodes->nelem ; i++) { - unsigned int constraint = 0; re_token_t *node = dfa->nodes + nodes->elems[i]; re_token_type_t type = node->type; - if (node->constraint) - constraint = node->constraint; + unsigned int constraint = node->constraint; if (type == CHARACTER && !constraint) continue; @@ -1586,8 +1706,6 @@ create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, newstate->halt = 1; else if (type == OP_BACK_REF) newstate->has_backref = 1; - else if (type == ANCHOR) - constraint = node->opr.ctx_type; if (constraint) { @@ -1599,7 +1717,9 @@ create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, free_state (newstate); return NULL; } - re_node_set_init_copy (newstate->entrance_nodes, nodes); + if (re_node_set_init_copy (newstate->entrance_nodes, nodes) + != REG_NOERROR) + return NULL; nctx_nodes = 0; newstate->has_constraint = 1; } @@ -1619,20 +1739,3 @@ create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, } return newstate; } - -static void -internal_function -free_state (re_dfastate_t *state) -{ - re_node_set_free (&state->non_eps_nodes); - re_node_set_free (&state->inveclosure); - if (state->entrance_nodes != &state->nodes) - { - re_node_set_free (state->entrance_nodes); - re_free (state->entrance_nodes); - } - re_node_set_free (&state->nodes); - re_free (state->word_trtable); - re_free (state->trtable); - re_free (state); -}