/* Extended regular expression matching and search library.
- Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 Free Software
+ Foundation, Inc.
This file is part of the GNU C Library.
Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
static void re_string_construct_common (const char *str, Idx len,
re_string_t *pstr,
- REG_TRANSLATE_TYPE trans, bool icase,
+ RE_TRANSLATE_TYPE trans, bool icase,
const re_dfa_t *dfa) internal_function;
static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa,
const re_node_set *nodes,
static reg_errcode_t
internal_function
re_string_allocate (re_string_t *pstr, const char *str, Idx len, Idx init_len,
- REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)
+ RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)
{
reg_errcode_t ret;
Idx init_buf_len;
static reg_errcode_t
internal_function
re_string_construct (re_string_t *pstr, const char *str, Idx len,
- REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)
+ RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)
{
reg_errcode_t ret;
memset (pstr, '\0', sizeof (re_string_t));
#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;
static void
internal_function
re_string_construct_common (const char *str, Idx len, re_string_t *pstr,
- REG_TRANSLATE_TYPE trans, bool icase,
+ 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 REG_TRANSLATE_TYPE) trans;
+ pstr->trans = trans;
pstr->icase = icase;
pstr->mbs_allocated = (trans != NULL || icase);
pstr->mb_cur_max = dfa->mb_cur_max;
mbclen = mbrtowc (&wc,
((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
+ byte_idx), remain_len, &pstr->cur_state);
- if (BE ((size_t) (mbclen + 2) > 2, 1))
+ if (BE (mbclen < (size_t) -2, 1))
{
wchar_t wcu = wc;
if (iswlower (wc))
else
p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx;
mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state);
- if (BE ((size_t) (mbclen + 2) > 2, 1))
+ if (BE (mbclen < (size_t) -2, 1))
{
wchar_t wcu = wc;
if (iswlower (wc))
mbstate_t prev_st;
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;)
{
+ 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,
+ 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 */
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. */
+ Idx prev_valid_len = pstr->valid_len;
+
#ifdef RE_ENABLE_I18N
if (BE (pstr->offsets_needed, 0))
{
}
#endif
pstr->valid_len = 0;
- pstr->valid_raw_len = 0;
#ifdef RE_ENABLE_I18N
if (pstr->mb_cur_max > 1)
{
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;
- Idx mlen = raw + pstr->len - p;
- unsigned char buf[6];
- size_t mbclen;
-
- 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));
- 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 (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;
+ unsigned char buf[6];
+ size_t mbclen;
+
+ if (BE (pstr->trans != NULL, 0))
+ {
+ int i = mlen < 6 ? mlen : 6;
+ while (--i >= 0)
+ buf[i] = pstr->trans[p[i]];
+ }
+ /* 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)
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)
}
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;
dest->alloc = dest->nelem = 0;
return REG_ESPACE;
}
- memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]);
+ memcpy (dest->elems, src->elems, src->nelem * sizeof (Idx));
}
else
re_node_set_init_empty (dest);
}
/* Copy remaining SRC elements. */
- memcpy (dest->elems, dest->elems + sbase, delta * sizeof dest->elems[0]);
+ memcpy (dest->elems, dest->elems + sbase, delta * sizeof (Idx));
return REG_NOERROR;
}
if (i1 < src1->nelem)
{
memcpy (dest->elems + id, src1->elems + i1,
- (src1->nelem - i1) * sizeof dest->elems[0]);
+ (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 dest->elems[0]);
+ (src2->nelem - i2) * sizeof (Idx));
id += src2->nelem - i2;
}
dest->nelem = id;
if (BE (dest->nelem == 0, 0))
{
dest->nelem = src->nelem;
- memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]);
+ memcpy (dest->elems, src->elems, src->nelem * sizeof (Idx));
return REG_NOERROR;
}
{
/* If DEST is exhausted, the remaining items of SRC must be unique. */
sbase -= is + 1;
- memcpy (dest->elems + sbase, src->elems,
- (is + 1) * sizeof dest->elems[0]);
+ memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (Idx));
}
id = dest->nelem - 1;
{
/* Copy remaining SRC elements. */
memcpy (dest->elems, dest->elems + sbase,
- delta * sizeof dest->elems[0]);
+ delta * sizeof (Idx));
break;
}
}
Idx idx;
/* In case the set is empty. */
if (set->alloc == 0)
- return re_node_set_init_1 (set, elem) == REG_NOERROR;
+ return BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1);
if (BE (set->nelem, 0) == 0)
{
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))
{
- Idx new_nodes_alloc = dfa->nodes_alloc * 2;
+ 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 REG_MISSING;
dfa->nodes = new_nodes;
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] = REG_MISSING;
re_node_set_init_empty (dfa->edests + dfa->nodes_len);
- We never return non-NULL value in case of any errors, it is for
optimization. */
-static re_dfastate_t*
+static re_dfastate_t *
internal_function
-re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes)
+re_acquire_state (reg_errcode_t *err, const re_dfa_t *dfa,
+ const re_node_set *nodes)
{
re_hashval_t hash;
re_dfastate_t *new_state;
/* 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
- We never return non-NULL value in case of any errors, it is for
optimization. */
-static re_dfastate_t*
+static re_dfastate_t *
internal_function
-re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa,
+re_acquire_state_context (reg_errcode_t *err, const re_dfa_t *dfa,
const re_node_set *nodes, unsigned int context)
{
re_hashval_t hash;
}
/* 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
indicates the error code if failed. */
static reg_errcode_t
-internal_function
-register_state (const re_dfa_t *dfa, re_dfastate_t *newstate, re_hashval_t hash)
+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;
{
Idx elem = newstate->nodes.elems[i];
if (!IS_EPSILON_NODE (dfa->nodes[elem].type))
- {
- bool ok = re_node_set_insert_last (&newstate->non_eps_nodes, elem);
- if (BE (! ok, 0))
- return REG_ESPACE;
- }
+ 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);
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. */
reg_errcode_t err;
re_dfastate_t *newstate;
- newstate = re_calloc (re_dfastate_t, 1);
+ newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
if (BE (newstate == NULL, 0))
return NULL;
err = re_node_set_init_copy (&newstate->nodes, nodes);
reg_errcode_t err;
re_dfastate_t *newstate;
- newstate = re_calloc (re_dfastate_t, 1);
+ newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
if (BE (newstate == NULL, 0))
return NULL;
err = re_node_set_init_copy (&newstate->nodes, 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;
newstate->halt = 1;
else if (type == OP_BACK_REF)
newstate->has_backref = 1;
- else if (type == ANCHOR)
- constraint = node->opr.ctx_type;
if (constraint)
{
}
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);
-}
projects / gnulib.git / blobdiff