/* 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 <isamu@yamato.ibm.com>.
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
- int n) internal_function;
+ Idx n) internal_function;
static void match_ctx_clean (re_match_context_t *mctx) internal_function;
static void match_ctx_free (re_match_context_t *cache) internal_function;
-static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
- int str_idx, int from, int to)
+static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
+ Idx str_idx, Idx from, Idx to)
internal_function;
-static int search_cur_bkref_entry (re_match_context_t *mctx, int str_idx)
+static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
internal_function;
-static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
- int str_idx) internal_function;
+static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
+ Idx str_idx) internal_function;
static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
- int node, int str_idx)
+ Idx node, Idx str_idx)
internal_function;
static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
- re_dfastate_t **limited_sts, int last_node,
- int last_str_idx)
+ re_dfastate_t **limited_sts, Idx last_node,
+ Idx last_str_idx)
internal_function;
static reg_errcode_t re_search_internal (const regex_t *preg,
- const char *string, int length,
- int start, int range, int stop,
+ const char *string, Idx length,
+ Idx start, Idx last_start, Idx stop,
size_t nmatch, regmatch_t pmatch[],
int eflags) internal_function;
-static int re_search_2_stub (struct re_pattern_buffer *bufp,
- const char *string1, int length1,
- const char *string2, int length2,
- int start, int range, struct re_registers *regs,
- int stop, int ret_len) internal_function;
-static int re_search_stub (struct re_pattern_buffer *bufp,
- const char *string, int length, int start,
- int range, int stop, struct re_registers *regs,
- int ret_len) internal_function;
-static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
- int nregs, int regs_allocated) internal_function;
-static inline re_dfastate_t *acquire_init_state_context
- (reg_errcode_t *err, const re_match_context_t *mctx, int idx)
- __attribute ((always_inline)) internal_function;
-static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
+static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
+ const char *string1, Idx length1,
+ const char *string2, Idx length2,
+ Idx start, regoff_t range,
+ struct re_registers *regs,
+ Idx stop, bool ret_len) internal_function;
+static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
+ const char *string, Idx length, Idx start,
+ regoff_t range, Idx stop,
+ struct re_registers *regs,
+ bool ret_len) internal_function;
+static unsigned int re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
+ Idx nregs, int regs_allocated)
internal_function;
-static int check_matching (re_match_context_t *mctx, int fl_longest_match,
- int *p_match_first)
+static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
internal_function;
-static int check_halt_node_context (const re_dfa_t *dfa, int node,
- unsigned int context) internal_function;
-static int check_halt_state_context (const re_match_context_t *mctx,
- const re_dfastate_t *state, int idx)
+static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
+ Idx *p_match_first) internal_function;
+static Idx check_halt_state_context (const re_match_context_t *mctx,
+ const re_dfastate_t *state, Idx idx)
internal_function;
-static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch,
- regmatch_t *prev_idx_match, int cur_node,
- int cur_idx, int nmatch) internal_function;
-static int proceed_next_node (const re_match_context_t *mctx,
- int nregs, regmatch_t *regs,
- int *pidx, int node, re_node_set *eps_via_nodes,
- struct re_fail_stack_t *fs) internal_function;
+static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
+ regmatch_t *prev_idx_match, Idx cur_node,
+ Idx cur_idx, Idx nmatch) internal_function;
static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
- int str_idx, int dest_node, int nregs,
+ Idx str_idx, Idx dest_node, Idx nregs,
regmatch_t *regs,
- re_node_set *eps_via_nodes) internal_function;
-static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
- regmatch_t *regs, re_node_set *eps_via_nodes) internal_function;
+ re_node_set *eps_via_nodes)
+ internal_function;
static reg_errcode_t set_regs (const regex_t *preg,
const re_match_context_t *mctx,
size_t nmatch, regmatch_t *pmatch,
- int fl_backtrack) internal_function;
-static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) internal_function;
+ bool fl_backtrack) internal_function;
+static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
+ internal_function;
#ifdef RE_ENABLE_I18N
static int sift_states_iter_mb (const re_match_context_t *mctx,
re_sift_context_t *sctx,
- int node_idx, int str_idx, int max_str_idx) internal_function;
+ Idx node_idx, Idx str_idx, Idx max_str_idx)
+ internal_function;
#endif /* RE_ENABLE_I18N */
-static reg_errcode_t sift_states_backward (re_match_context_t *mctx,
- re_sift_context_t *sctx) internal_function;
-static reg_errcode_t build_sifted_states (re_match_context_t *mctx,
- re_sift_context_t *sctx, int str_idx,
- re_node_set *cur_dest) internal_function;
-static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx,
+static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
+ re_sift_context_t *sctx)
+ internal_function;
+static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
+ re_sift_context_t *sctx, Idx str_idx,
+ re_node_set *cur_dest)
+ internal_function;
+static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
re_sift_context_t *sctx,
- int str_idx,
- re_node_set *dest_nodes) internal_function;
-static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
- re_node_set *dest_nodes,
- const re_node_set *candidates) internal_function;
-static reg_errcode_t sub_epsilon_src_nodes (re_dfa_t *dfa, int node,
+ Idx str_idx,
+ re_node_set *dest_nodes)
+ internal_function;
+static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
re_node_set *dest_nodes,
- const re_node_set *and_nodes) internal_function;
-static int check_dst_limits (re_match_context_t *mctx, re_node_set *limits,
- int dst_node, int dst_idx, int src_node,
- int src_idx) internal_function;
-static int check_dst_limits_calc_pos_1 (re_match_context_t *mctx,
- int boundaries, int subexp_idx,
- int from_node, int bkref_idx) internal_function;
-static int check_dst_limits_calc_pos (re_match_context_t *mctx,
- int limit, int subexp_idx,
- int node, int str_idx,
- int bkref_idx) internal_function;
-static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
+ const re_node_set *candidates)
+ internal_function;
+static bool check_dst_limits (const re_match_context_t *mctx,
+ const re_node_set *limits,
+ Idx dst_node, Idx dst_idx, Idx src_node,
+ Idx src_idx) internal_function;
+static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
+ int boundaries, Idx subexp_idx,
+ Idx from_node, Idx bkref_idx)
+ internal_function;
+static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
+ Idx limit, Idx subexp_idx,
+ Idx node, Idx str_idx,
+ Idx bkref_idx) internal_function;
+static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
re_node_set *dest_nodes,
const re_node_set *candidates,
re_node_set *limits,
struct re_backref_cache_entry *bkref_ents,
- int str_idx) internal_function;
-static reg_errcode_t sift_states_bkref (re_match_context_t *mctx,
+ Idx str_idx) internal_function;
+static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
re_sift_context_t *sctx,
- int str_idx, const re_node_set *candidates) internal_function;
-static reg_errcode_t clean_state_log_if_needed (re_match_context_t *mctx,
- int next_state_log_idx) internal_function;
-static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
- re_dfastate_t **src, int num) internal_function;
+ Idx str_idx, const re_node_set *candidates)
+ internal_function;
+static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
+ re_dfastate_t **dst,
+ re_dfastate_t **src, Idx num)
+ internal_function;
static re_dfastate_t *find_recover_state (reg_errcode_t *err,
re_match_context_t *mctx) internal_function;
static re_dfastate_t *transit_state (reg_errcode_t *err,
re_dfastate_t *state) internal_function;
static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
re_match_context_t *mctx,
- re_dfastate_t *next_state) internal_function;
+ re_dfastate_t *next_state)
+ internal_function;
static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
re_node_set *cur_nodes,
- int str_idx) internal_function;
+ Idx str_idx) internal_function;
#if 0
static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
re_match_context_t *mctx,
- re_dfastate_t *pstate) internal_function;
+ re_dfastate_t *pstate)
+ internal_function;
#endif
#ifdef RE_ENABLE_I18N
static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
- re_dfastate_t *pstate) internal_function;
+ re_dfastate_t *pstate)
+ internal_function;
#endif /* RE_ENABLE_I18N */
static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
- const re_node_set *nodes) internal_function;
+ const re_node_set *nodes)
+ internal_function;
static reg_errcode_t get_subexp (re_match_context_t *mctx,
- int bkref_node, int bkref_str_idx) internal_function;
+ Idx bkref_node, Idx bkref_str_idx)
+ internal_function;
static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
const re_sub_match_top_t *sub_top,
re_sub_match_last_t *sub_last,
- int bkref_node, int bkref_str) internal_function;
-static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
- int subexp_idx, int type) internal_function;
+ Idx bkref_node, Idx bkref_str)
+ internal_function;
+static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
+ Idx subexp_idx, int type) internal_function;
static reg_errcode_t check_arrival (re_match_context_t *mctx,
- state_array_t *path, int top_node,
- int top_str, int last_node, int last_str,
+ state_array_t *path, Idx top_node,
+ Idx top_str, Idx last_node, Idx last_str,
int type) internal_function;
static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
- int str_idx,
+ Idx str_idx,
re_node_set *cur_nodes,
- re_node_set *next_nodes) internal_function;
-static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
+ re_node_set *next_nodes)
+ internal_function;
+static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
re_node_set *cur_nodes,
- int ex_subexp, int type) internal_function;
-static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
+ Idx ex_subexp, int type)
+ internal_function;
+static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
re_node_set *dst_nodes,
- int target, int ex_subexp,
+ Idx target, Idx ex_subexp,
int type) internal_function;
static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
- re_node_set *cur_nodes, int cur_str,
- int subexp_num, int type) internal_function;
-static int build_trtable (re_dfa_t *dfa,
- re_dfastate_t *state) internal_function;
+ re_node_set *cur_nodes, Idx cur_str,
+ Idx subexp_num, int type)
+ internal_function;
+static bool build_trtable (const re_dfa_t *dfa,
+ re_dfastate_t *state) internal_function;
#ifdef RE_ENABLE_I18N
-static int check_node_accept_bytes (re_dfa_t *dfa, int node_idx,
- const re_string_t *input, int idx) internal_function;
+static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
+ const re_string_t *input, Idx idx)
+ internal_function;
# ifdef _LIBC
static unsigned int find_collation_sequence_value (const unsigned char *mbs,
- size_t name_len) internal_function;
+ size_t name_len)
+ internal_function;
# endif /* _LIBC */
#endif /* RE_ENABLE_I18N */
-static int group_nodes_into_DFAstates (re_dfa_t *dfa,
+static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
const re_dfastate_t *state,
re_node_set *states_node,
- bitset *states_ch) internal_function;
-static int check_node_accept (const re_match_context_t *mctx,
- const re_token_t *node, int idx) internal_function;
-static reg_errcode_t extend_buffers (re_match_context_t *mctx) internal_function;
+ bitset_t *states_ch) internal_function;
+static bool check_node_accept (const re_match_context_t *mctx,
+ const re_token_t *node, Idx idx)
+ internal_function;
+static reg_errcode_t extend_buffers (re_match_context_t *mctx)
+ internal_function;
\f
/* Entry point for POSIX code. */
We return 0 if we find a match and REG_NOMATCH if not. */
int
-regexec (const regex_t *__restrict preg, const char *__restrict string,
- size_t nmatch, regmatch_t pmatch[], int eflags)
+regexec (preg, string, nmatch, pmatch, eflags)
+ const regex_t *_Restrict_ preg;
+ const char *_Restrict_ string;
+ size_t nmatch;
+ regmatch_t pmatch[_Restrict_arr_];
+ int eflags;
{
reg_errcode_t err;
- int start, length;
- re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
+ Idx start, length;
+#ifdef _LIBC
+ re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+#endif
if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
return REG_BADPAT;
__libc_lock_lock (dfa->lock);
if (preg->no_sub)
- err = re_search_internal (preg, string, length, start, length - start,
+ err = re_search_internal (preg, string, length, start, length,
length, 0, NULL, eflags);
else
- err = re_search_internal (preg, string, length, start, length - start,
+ err = re_search_internal (preg, string, length, start, length,
length, nmatch, pmatch, eflags);
__libc_lock_unlock (dfa->lock);
return err != REG_NOERROR;
int
attribute_compat_text_section
-__compat_regexec (const regex_t *__restrict preg,
- const char *__restrict string, size_t nmatch,
+__compat_regexec (const regex_t *_Restrict_ preg,
+ const char *_Restrict_ string, size_t nmatch,
regmatch_t pmatch[], int eflags)
{
return regexec (preg, string, nmatch, pmatch,
concerned.
If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
- and all groups is stroed in REGS. (For the "_2" variants, the offsets are
+ and all groups is stored in REGS. (For the "_2" variants, the offsets are
computed relative to the concatenation, not relative to the individual
strings.)
return the position of the start of the match. Return value -1 means no
match was found and -2 indicates an internal error. */
-int
-re_match (struct re_pattern_buffer *bufp, const char *string,
- int length, int start, struct re_registers *regs)
+regoff_t
+re_match (bufp, string, length, start, regs)
+ struct re_pattern_buffer *bufp;
+ const char *string;
+ Idx length, start;
+ struct re_registers *regs;
{
- return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
+ return re_search_stub (bufp, string, length, start, 0, length, regs, true);
}
#ifdef _LIBC
weak_alias (__re_match, re_match)
#endif
-int
-re_search (struct re_pattern_buffer *bufp, const char *string,
- int length, int start, int range, struct re_registers *regs)
+regoff_t
+re_search (bufp, string, length, start, range, regs)
+ struct re_pattern_buffer *bufp;
+ const char *string;
+ Idx length, start;
+ regoff_t range;
+ struct re_registers *regs;
{
- return re_search_stub (bufp, string, length, start, range, length, regs, 0);
+ return re_search_stub (bufp, string, length, start, range, length, regs,
+ false);
}
#ifdef _LIBC
weak_alias (__re_search, re_search)
#endif
-int
-re_match_2 (struct re_pattern_buffer *bufp,
- const char *string1, int length1,
- const char *string2, int length2,
- int start, struct re_registers *regs, int stop)
+regoff_t
+re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
+ struct re_pattern_buffer *bufp;
+ const char *string1, *string2;
+ Idx length1, length2, start, stop;
+ struct re_registers *regs;
{
return re_search_2_stub (bufp, string1, length1, string2, length2,
- start, 0, regs, stop, 1);
+ start, 0, regs, stop, true);
}
#ifdef _LIBC
weak_alias (__re_match_2, re_match_2)
#endif
-int
-re_search_2 (struct re_pattern_buffer *bufp,
- const char *string1, int length1,
- const char *string2, int length2,
- int start, int range, struct re_registers *regs, int stop)
+regoff_t
+re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
+ struct re_pattern_buffer *bufp;
+ const char *string1, *string2;
+ Idx length1, length2, start, stop;
+ regoff_t range;
+ struct re_registers *regs;
{
return re_search_2_stub (bufp, string1, length1, string2, length2,
- start, range, regs, stop, 0);
+ start, range, regs, stop, false);
}
#ifdef _LIBC
weak_alias (__re_search_2, re_search_2)
#endif
-static int
+static regoff_t
internal_function
re_search_2_stub (struct re_pattern_buffer *bufp,
- const char *string1, int length1,
- const char *string2, int length2,
- int start, int range, struct re_registers *regs, int stop,
- int ret_len)
+ const char *string1, Idx length1,
+ const char *string2, Idx length2,
+ Idx start, regoff_t range, struct re_registers *regs,
+ Idx stop, bool ret_len)
{
const char *str;
- int rval;
- int len = length1 + length2;
- int free_str = 0;
+ regoff_t rval;
+ Idx len = length1 + length2;
+ char *s = NULL;
- if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
+ if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
return -2;
/* Concatenate the strings. */
if (length2 > 0)
if (length1 > 0)
{
- char *s = re_malloc (char, len);
+ s = re_malloc (char, len);
if (BE (s == NULL, 0))
return -2;
+#ifdef _LIBC
+ memcpy (__mempcpy (s, string1, length1), string2, length2);
+#else
memcpy (s, string1, length1);
memcpy (s + length1, string2, length2);
+#endif
str = s;
- free_str = 1;
}
else
str = string2;
rval = re_search_stub (bufp, str, len, start, range, stop, regs,
ret_len);
- if (free_str)
- re_free ((char *) str);
+ re_free (s);
return rval;
}
/* The parameters have the same meaning as those of re_search.
Additional parameters:
- If RET_LEN is nonzero the length of the match is returned (re_match style);
+ If RET_LEN is true the length of the match is returned (re_match style);
otherwise the position of the match is returned. */
-static int
+static regoff_t
internal_function
re_search_stub (struct re_pattern_buffer *bufp,
- const char *string, int length,
- int start, int range, int stop, struct re_registers *regs,
- int ret_len)
+ const char *string, Idx length,
+ Idx start, regoff_t range, Idx stop, struct re_registers *regs,
+ bool ret_len)
{
reg_errcode_t result;
regmatch_t *pmatch;
- int nregs, rval;
+ Idx nregs;
+ regoff_t rval;
int eflags = 0;
- re_dfa_t *dfa = (re_dfa_t *)bufp->buffer;
+#ifdef _LIBC
+ re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
+#endif
+ Idx last_start = start + range;
/* Check for out-of-range. */
if (BE (start < 0 || start > length, 0))
return -1;
- if (BE (start + range > length, 0))
- range = length - start;
- else if (BE (start + range < 0, 0))
- range = -start;
+ if (BE (length < last_start || (0 <= range && last_start < start), 0))
+ last_start = length;
+ else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
+ last_start = 0;
__libc_lock_lock (dfa->lock);
eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
/* Compile fastmap if we haven't yet. */
- if (range > 0 && bufp->fastmap != NULL && !bufp->fastmap_accurate)
+ if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
re_compile_fastmap (bufp);
if (BE (bufp->no_sub, 0))
/* We need at least 1 register. */
if (regs == NULL)
nregs = 1;
- else if (BE (bufp->regs_allocated == REGS_FIXED &&
- regs->num_regs < bufp->re_nsub + 1, 0))
+ else if (BE (bufp->regs_allocated == REGS_FIXED
+ && regs->num_regs <= bufp->re_nsub, 0))
{
nregs = regs->num_regs;
if (BE (nregs < 1, 0))
goto out;
}
- result = re_search_internal (bufp, string, length, start, range, stop,
+ result = re_search_internal (bufp, string, length, start, last_start, stop,
nregs, pmatch, eflags);
rval = 0;
return rval;
}
-static unsigned
+static unsigned int
internal_function
-re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, int nregs,
+re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
int regs_allocated)
{
int rval = REGS_REALLOCATE;
- int i;
- int need_regs = nregs + 1;
+ Idx i;
+ Idx need_regs = nregs + 1;
/* We need one extra element beyond `num_regs' for the `-1' marker GNU code
uses. */
if (regs_allocated == REGS_UNALLOCATED)
{ /* No. So allocate them with malloc. */
regs->start = re_malloc (regoff_t, need_regs);
- regs->end = re_malloc (regoff_t, need_regs);
- if (BE (regs->start == NULL, 0) || BE (regs->end == NULL, 0))
+ if (BE (regs->start == NULL, 0))
return REGS_UNALLOCATED;
+ regs->end = re_malloc (regoff_t, need_regs);
+ if (BE (regs->end == NULL, 0))
+ {
+ re_free (regs->start);
+ return REGS_UNALLOCATED;
+ }
regs->num_regs = need_regs;
}
else if (regs_allocated == REGS_REALLOCATE)
if (BE (need_regs > regs->num_regs, 0))
{
regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
- regoff_t *new_end = re_realloc (regs->end, regoff_t, need_regs);
- if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
+ regoff_t *new_end;
+ if (BE (new_start == NULL, 0))
return REGS_UNALLOCATED;
+ new_end = re_realloc (regs->end, regoff_t, need_regs);
+ if (BE (new_end == NULL, 0))
+ {
+ re_free (new_start);
+ return REGS_UNALLOCATED;
+ }
regs->start = new_start;
regs->end = new_end;
regs->num_regs = need_regs;
freeing the old data. */
void
-re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
- unsigned int num_regs, regoff_t *starts, regoff_t *ends)
+re_set_registers (bufp, regs, num_regs, starts, ends)
+ struct re_pattern_buffer *bufp;
+ struct re_registers *regs;
+ __re_size_t num_regs;
+ regoff_t *starts, *ends;
{
if (num_regs)
{
{
bufp->regs_allocated = REGS_UNALLOCATED;
regs->num_regs = 0;
- regs->start = regs->end = (regoff_t *) 0;
+ regs->start = regs->end = NULL;
}
}
#ifdef _LIBC
/* Searches for a compiled pattern PREG in the string STRING, whose
length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
- mingings with regexec. START, and RANGE have the same meanings
- with re_search.
+ meaning as with regexec. LAST_START is START + RANGE, where
+ START and RANGE have the same meaning as with re_search.
Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
otherwise return the error code.
Note: We assume front end functions already check ranges.
- (START + RANGE >= 0 && START + RANGE <= LENGTH) */
+ (0 <= LAST_START && LAST_START <= LENGTH) */
static reg_errcode_t
-internal_function
+internal_function __attribute_warn_unused_result__
re_search_internal (const regex_t *preg,
- const char *string, int length,
- int start, int range, int stop,
+ const char *string, Idx length,
+ Idx start, Idx last_start, Idx stop,
size_t nmatch, regmatch_t pmatch[],
int eflags)
{
reg_errcode_t err;
- re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
- int left_lim, right_lim, incr;
- int fl_longest_match, match_first, match_kind, match_last = -1;
- int extra_nmatch;
- int sb, ch;
+ const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
+ Idx left_lim, right_lim;
+ int incr;
+ bool fl_longest_match;
+ int match_kind;
+ Idx match_first;
+ Idx match_last = REG_MISSING;
+ Idx extra_nmatch;
+ bool sb;
+ int ch;
#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
re_match_context_t mctx = { .dfa = dfa };
#else
re_match_context_t mctx;
#endif
- char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
- && range && !preg->can_be_null) ? preg->fastmap : NULL;
- unsigned RE_TRANSLATE_TYPE t = (unsigned RE_TRANSLATE_TYPE) preg->translate;
+ char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
+ && start != last_start && !preg->can_be_null)
+ ? preg->fastmap : NULL);
+ RE_TRANSLATE_TYPE t = preg->translate;
#if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
memset (&mctx, '\0', sizeof (re_match_context_t));
#ifdef DEBUG
/* We assume front-end functions already check them. */
- assert (start + range >= 0 && start + range <= length);
+ assert (0 <= last_start && last_start <= length);
#endif
/* If initial states with non-begbuf contexts have no elements,
&& (dfa->init_state_nl->nodes.nelem == 0
|| !preg->newline_anchor))
{
- if (start != 0 && start + range != 0)
+ if (start != 0 && last_start != 0)
return REG_NOMATCH;
- start = range = 0;
+ start = last_start = 0;
}
/* We must check the longest matching, if nmatch > 0. */
fl_longest_match = (nmatch != 0 || dfa->nbackref);
err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
- preg->translate, preg->syntax & RE_ICASE, dfa);
+ preg->translate, (preg->syntax & RE_ICASE) != 0,
+ dfa);
if (BE (err != REG_NOERROR, 0))
goto free_return;
mctx.input.stop = stop;
multi character collating element. */
if (nmatch > 1 || dfa->has_mb_node)
{
+ /* Avoid overflow. */
+ if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
+ {
+ err = REG_ESPACE;
+ goto free_return;
+ }
+
mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
if (BE (mctx.state_log == NULL, 0))
{
: CONTEXT_NEWLINE | CONTEXT_BEGBUF;
/* Check incrementally whether of not the input string match. */
- incr = (range < 0) ? -1 : 1;
- left_lim = (range < 0) ? start + range : start;
- right_lim = (range < 0) ? start : start + range;
+ incr = (last_start < start) ? -1 : 1;
+ left_lim = (last_start < start) ? last_start : start;
+ right_lim = (last_start < start) ? start : last_start;
sb = dfa->mb_cur_max == 1;
match_kind =
(fastmap
? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
- | (range >= 0 ? 2 : 0)
+ | (start <= last_start ? 2 : 0)
| (t != NULL ? 1 : 0))
: 8);
{
/* If MATCH_FIRST is out of the valid range, reconstruct the
buffers. */
- unsigned int offset = match_first - mctx.input.raw_mbs_idx;
- if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
+ __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
+ if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
{
err = re_string_reconstruct (&mctx.input, match_first,
eflags);
break;
match_first += incr;
if (match_first < left_lim || match_first > right_lim)
- {
- err = REG_NOMATCH;
- goto free_return;
- }
+ {
+ err = REG_NOMATCH;
+ goto free_return;
+ }
}
break;
}
/* We assume that the matching starts from 0. */
mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
match_last = check_matching (&mctx, fl_longest_match,
- range >= 0 ? &match_first : NULL);
- if (match_last != -1)
+ start <= last_start ? &match_first : NULL);
+ if (match_last != REG_MISSING)
{
- if (BE (match_last == -2, 0))
+ if (BE (match_last == REG_ERROR, 0))
{
err = REG_ESPACE;
goto free_return;
break;
if (BE (err != REG_NOMATCH, 0))
goto free_return;
- match_last = -1;
+ match_last = REG_MISSING;
}
else
break; /* We found a match. */
}
#ifdef DEBUG
- assert (match_last != -1);
+ assert (match_last != REG_MISSING);
assert (err == REG_NOERROR);
#endif
/* Set pmatch[] if we need. */
if (nmatch > 0)
{
- int reg_idx;
+ Idx reg_idx;
/* Initialize registers. */
for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
/* Set the points where matching start/end. */
pmatch[0].rm_so = 0;
pmatch[0].rm_eo = mctx.match_last;
+ /* FIXME: This function should fail if mctx.match_last exceeds
+ the maximum possible regoff_t value. We need a new error
+ code REG_OVERFLOW. */
if (!preg->no_sub && nmatch > 1)
{
#ifdef RE_ENABLE_I18N
if (BE (mctx.input.offsets_needed != 0, 0))
{
- if (pmatch[reg_idx].rm_so == mctx.input.valid_len)
- pmatch[reg_idx].rm_so += mctx.input.valid_raw_len - mctx.input.valid_len;
- else
- pmatch[reg_idx].rm_so = mctx.input.offsets[pmatch[reg_idx].rm_so];
- if (pmatch[reg_idx].rm_eo == mctx.input.valid_len)
- pmatch[reg_idx].rm_eo += mctx.input.valid_raw_len - mctx.input.valid_len;
- else
- pmatch[reg_idx].rm_eo = mctx.input.offsets[pmatch[reg_idx].rm_eo];
+ pmatch[reg_idx].rm_so =
+ (pmatch[reg_idx].rm_so == mctx.input.valid_len
+ ? mctx.input.valid_raw_len
+ : mctx.input.offsets[pmatch[reg_idx].rm_so]);
+ pmatch[reg_idx].rm_eo =
+ (pmatch[reg_idx].rm_eo == mctx.input.valid_len
+ ? mctx.input.valid_raw_len
+ : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
}
#else
assert (mctx.input.offsets_needed == 0);
}
if (dfa->subexp_map)
- for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
- if (dfa->subexp_map[reg_idx] != reg_idx)
- {
- pmatch[reg_idx + 1].rm_so
- = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
- pmatch[reg_idx + 1].rm_eo
- = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
- }
+ for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
+ if (dfa->subexp_map[reg_idx] != reg_idx)
+ {
+ pmatch[reg_idx + 1].rm_so
+ = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
+ pmatch[reg_idx + 1].rm_eo
+ = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
+ }
}
free_return:
}
static reg_errcode_t
-internal_function
+internal_function __attribute_warn_unused_result__
prune_impossible_nodes (re_match_context_t *mctx)
{
- re_dfa_t *const dfa = mctx->dfa;
- int halt_node, match_last;
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx halt_node, match_last;
reg_errcode_t ret;
re_dfastate_t **sifted_states;
re_dfastate_t **lim_states = NULL;
#endif
match_last = mctx->match_last;
halt_node = mctx->last_node;
+
+ /* Avoid overflow. */
+ if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
+ return REG_ESPACE;
+
sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
if (BE (sifted_states == NULL, 0))
{
do
{
--match_last;
- if (match_last < 0)
+ if (! REG_VALID_INDEX (match_last))
{
ret = REG_NOMATCH;
goto free_return;
re_node_set_free (&sctx.limits);
if (BE (ret != REG_NOERROR, 0))
goto free_return;
+ if (sifted_states[0] == NULL)
+ {
+ ret = REG_NOMATCH;
+ goto free_return;
+ }
}
re_free (mctx->state_log);
mctx->state_log = sifted_states;
since initial states may have constraints like "\<", "^", etc.. */
static inline re_dfastate_t *
-internal_function
+__attribute ((always_inline)) internal_function
acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
- int idx)
+ Idx idx)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
if (dfa->init_state->has_constraint)
{
unsigned int context;
}
/* Check whether the regular expression match input string INPUT or not,
- and return the index where the matching end, return -1 if not match,
- or return -2 in case of an error.
+ and return the index where the matching end. Return REG_MISSING if
+ there is no match, and return REG_ERROR in case of an error.
FL_LONGEST_MATCH means we want the POSIX longest matching.
If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
next place where we may want to try matching.
Note that the matcher assume that the maching starts from the current
index of the buffer. */
-static int
-internal_function
-check_matching (re_match_context_t *mctx, int fl_longest_match,
- int *p_match_first)
+static Idx
+internal_function __attribute_warn_unused_result__
+check_matching (re_match_context_t *mctx, bool fl_longest_match,
+ Idx *p_match_first)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
- int match = 0;
- int match_last = -1;
- int cur_str_idx = re_string_cur_idx (&mctx->input);
+ Idx match = 0;
+ Idx match_last = REG_MISSING;
+ Idx cur_str_idx = re_string_cur_idx (&mctx->input);
re_dfastate_t *cur_state;
- int at_init_state = p_match_first != NULL;
- int next_start_idx = cur_str_idx;
+ bool at_init_state = p_match_first != NULL;
+ Idx next_start_idx = cur_str_idx;
err = REG_NOERROR;
cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
if (BE (cur_state == NULL, 0))
{
assert (err == REG_ESPACE);
- return -2;
+ return REG_ERROR;
}
if (mctx->state_log != NULL)
later. E.g. Processing back references. */
if (BE (dfa->nbackref, 0))
{
- at_init_state = 0;
+ at_init_state = false;
err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
if (BE (err != REG_NOERROR, 0))
return err;
{
err = transit_state_bkref (mctx, &cur_state->nodes);
if (BE (err != REG_NOERROR, 0))
- return err;
+ return err;
}
}
}
while (!re_string_eoi (&mctx->input))
{
re_dfastate_t *old_state = cur_state;
- int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
+ Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
if (BE (next_char_idx >= mctx->input.bufs_len, 0)
- || (BE (next_char_idx >= mctx->input.valid_len, 0)
- && mctx->input.valid_len < mctx->input.len))
- {
- err = extend_buffers (mctx);
- if (BE (err != REG_NOERROR, 0))
+ || (BE (next_char_idx >= mctx->input.valid_len, 0)
+ && mctx->input.valid_len < mctx->input.len))
+ {
+ err = extend_buffers (mctx);
+ if (BE (err != REG_NOERROR, 0))
{
assert (err == REG_ESPACE);
- return -2;
+ return REG_ERROR;
}
- }
+ }
cur_state = transit_state (&err, mctx, cur_state);
if (mctx->state_log != NULL)
state using the state log, if available and if we have not
already found a valid (even if not the longest) match. */
if (BE (err != REG_NOERROR, 0))
- return -2;
+ return REG_ERROR;
if (mctx->state_log == NULL
|| (match && !fl_longest_match)
if (old_state == cur_state)
next_start_idx = next_char_idx;
else
- at_init_state = 0;
+ at_init_state = false;
}
if (cur_state->halt)
/* Check NODE match the current context. */
-static int
+static bool
internal_function
-check_halt_node_context (const re_dfa_t *dfa, int node, unsigned int context)
+check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
{
re_token_type_t type = dfa->nodes[node].type;
unsigned int constraint = dfa->nodes[node].constraint;
if (type != END_OF_RE)
- return 0;
+ return false;
if (!constraint)
- return 1;
+ return true;
if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
- return 0;
- return 1;
+ return false;
+ return true;
}
/* Check the halt state STATE match the current context.
Return 0 if not match, if the node, STATE has, is a halt node and
match the context, return the node. */
-static int
+static Idx
internal_function
check_halt_state_context (const re_match_context_t *mctx,
- const re_dfastate_t *state, int idx)
+ const re_dfastate_t *state, Idx idx)
{
- int i;
+ Idx i;
unsigned int context;
#ifdef DEBUG
assert (state->halt);
/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
corresponding to the DFA).
- Return the destination node, and update EPS_VIA_NODES, return -1 in case
- of errors. */
+ Return the destination node, and update EPS_VIA_NODES;
+ return REG_MISSING in case of errors. */
-static int
+static Idx
internal_function
-proceed_next_node (const re_match_context_t *mctx,
- int nregs, regmatch_t *regs, int *pidx, int node,
- re_node_set *eps_via_nodes, struct re_fail_stack_t *fs)
+proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
+ Idx *pidx, Idx node, re_node_set *eps_via_nodes,
+ struct re_fail_stack_t *fs)
{
- re_dfa_t *const dfa = mctx->dfa;
- int i, err;
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx i;
+ bool ok;
if (IS_EPSILON_NODE (dfa->nodes[node].type))
{
re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
re_node_set *edests = &dfa->edests[node];
- int dest_node;
- err = re_node_set_insert (eps_via_nodes, node);
- if (BE (err < 0, 0))
- return -2;
- /* Pick up a valid destination, or return -1 if none is found. */
- for (dest_node = -1, i = 0; i < edests->nelem; ++i)
+ Idx dest_node;
+ ok = re_node_set_insert (eps_via_nodes, node);
+ if (BE (! ok, 0))
+ return REG_ERROR;
+ /* Pick up a valid destination, or return REG_MISSING if none
+ is found. */
+ for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
{
- int candidate = edests->elems[i];
+ Idx candidate = edests->elems[i];
if (!re_node_set_contains (cur_nodes, candidate))
continue;
- if (dest_node == -1)
+ if (dest_node == REG_MISSING)
dest_node = candidate;
- else
+ else
{
/* In order to avoid infinite loop like "(a*)*", return the second
- epsilon-transition if the first was already considered. */
+ epsilon-transition if the first was already considered. */
if (re_node_set_contains (eps_via_nodes, dest_node))
- return candidate;
+ return candidate;
/* Otherwise, push the second epsilon-transition on the fail stack. */
else if (fs != NULL
&& push_fail_stack (fs, *pidx, candidate, nregs, regs,
- eps_via_nodes))
- return -2;
+ eps_via_nodes))
+ return REG_ERROR;
/* We know we are going to exit. */
break;
}
else
{
- int naccepted = 0;
+ Idx naccepted = 0;
re_token_type_t type = dfa->nodes[node].type;
#ifdef RE_ENABLE_I18N
#endif /* RE_ENABLE_I18N */
if (type == OP_BACK_REF)
{
- int subexp_idx = dfa->nodes[node].opr.idx + 1;
+ Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
if (fs != NULL)
{
if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
- return -1;
+ return REG_MISSING;
else if (naccepted)
{
char *buf = (char *) re_string_get_buffer (&mctx->input);
if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
naccepted) != 0)
- return -1;
+ return REG_MISSING;
}
}
if (naccepted == 0)
{
- int dest_node;
- err = re_node_set_insert (eps_via_nodes, node);
- if (BE (err < 0, 0))
- return -2;
+ Idx dest_node;
+ ok = re_node_set_insert (eps_via_nodes, node);
+ if (BE (! ok, 0))
+ return REG_ERROR;
dest_node = dfa->edests[node].elems[0];
if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
dest_node))
if (naccepted != 0
|| check_node_accept (mctx, dfa->nodes + node, *pidx))
{
- int dest_node = dfa->nexts[node];
+ Idx dest_node = dfa->nexts[node];
*pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
|| !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
dest_node)))
- return -1;
+ return REG_MISSING;
re_node_set_empty (eps_via_nodes);
return dest_node;
}
}
- return -1;
+ return REG_MISSING;
}
static reg_errcode_t
-internal_function
-push_fail_stack (struct re_fail_stack_t *fs, int str_idx, int dest_node,
- int nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
+internal_function __attribute_warn_unused_result__
+push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
+ Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
{
reg_errcode_t err;
- int num = fs->num++;
+ Idx num = fs->num++;
if (fs->num == fs->alloc)
{
struct re_fail_stack_ent_t *new_array;
return err;
}
-static int
+static Idx
internal_function
-pop_fail_stack (struct re_fail_stack_t *fs, int *pidx,
- int nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
+pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
+ regmatch_t *regs, re_node_set *eps_via_nodes)
{
- int num = --fs->num;
- assert (num >= 0);
+ Idx num = --fs->num;
+ assert (REG_VALID_INDEX (num));
*pidx = fs->stack[num].idx;
memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
re_node_set_free (eps_via_nodes);
pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
static reg_errcode_t
-internal_function
-set_regs (const regex_t *preg, const re_match_context_t *mctx,
- size_t nmatch, regmatch_t *pmatch, int fl_backtrack)
+internal_function __attribute_warn_unused_result__
+set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
+ regmatch_t *pmatch, bool fl_backtrack)
{
- re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
- int idx, cur_node;
+ const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
+ Idx idx, cur_node;
re_node_set eps_via_nodes;
struct re_fail_stack_t *fs;
struct re_fail_stack_t fs_body = { 0, 2, NULL };
regmatch_t *prev_idx_match;
+ bool prev_idx_match_malloced = false;
#ifdef DEBUG
assert (nmatch > 1);
cur_node = dfa->init_node;
re_node_set_init_empty (&eps_via_nodes);
- prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * nmatch);
+ if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
+ prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
+ else
+ {
+ prev_idx_match = re_malloc (regmatch_t, nmatch);
+ if (prev_idx_match == NULL)
+ {
+ free_fail_stack_return (fs);
+ return REG_ESPACE;
+ }
+ prev_idx_match_malloced = true;
+ }
memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
{
- int reg_idx;
+ Idx reg_idx;
if (fs)
{
for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
if (reg_idx == nmatch)
{
re_node_set_free (&eps_via_nodes);
+ if (prev_idx_match_malloced)
+ re_free (prev_idx_match);
return free_fail_stack_return (fs);
}
cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
else
{
re_node_set_free (&eps_via_nodes);
+ if (prev_idx_match_malloced)
+ re_free (prev_idx_match);
return REG_NOERROR;
}
}
cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
&eps_via_nodes, fs);
- if (BE (cur_node < 0, 0))
+ if (BE (! REG_VALID_INDEX (cur_node), 0))
{
- if (BE (cur_node == -2, 0))
+ if (BE (cur_node == REG_ERROR, 0))
{
re_node_set_free (&eps_via_nodes);
+ if (prev_idx_match_malloced)
+ re_free (prev_idx_match);
free_fail_stack_return (fs);
return REG_ESPACE;
}
else
{
re_node_set_free (&eps_via_nodes);
+ if (prev_idx_match_malloced)
+ re_free (prev_idx_match);
return REG_NOMATCH;
}
}
}
re_node_set_free (&eps_via_nodes);
+ if (prev_idx_match_malloced)
+ re_free (prev_idx_match);
return free_fail_stack_return (fs);
}
{
if (fs)
{
- int fs_idx;
+ Idx fs_idx;
for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
{
re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
static void
internal_function
-update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
- int cur_node, int cur_idx, int nmatch)
+update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
+ regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
{
int type = dfa->nodes[cur_node].type;
if (type == OP_OPEN_SUBEXP)
{
- int reg_num = dfa->nodes[cur_node].opr.idx + 1;
+ Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
/* We are at the first node of this sub expression. */
if (reg_num < nmatch)
}
else if (type == OP_CLOSE_SUBEXP)
{
- int reg_num = dfa->nodes[cur_node].opr.idx + 1;
+ Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
if (reg_num < nmatch)
{
/* We are at the last node of this sub expression. */
static reg_errcode_t
internal_function
-sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
+sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
{
reg_errcode_t err;
int null_cnt = 0;
- int str_idx = sctx->last_str_idx;
+ Idx str_idx = sctx->last_str_idx;
re_node_set cur_dest;
#ifdef DEBUG
if (mctx->state_log[str_idx])
{
err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
- if (BE (err != REG_NOERROR, 0))
+ if (BE (err != REG_NOERROR, 0))
goto free_return;
}
}
static reg_errcode_t
-internal_function
-build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
- int str_idx, re_node_set *cur_dest)
+internal_function __attribute_warn_unused_result__
+build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
+ Idx str_idx, re_node_set *cur_dest)
{
- re_dfa_t *const dfa = mctx->dfa;
- re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
- int i;
+ const re_dfa_t *const dfa = mctx->dfa;
+ const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
+ Idx i;
/* Then build the next sifted state.
We build the next sifted state on `cur_dest', and update
(with the epsilon nodes pre-filtered out). */
for (i = 0; i < cur_src->nelem; i++)
{
- int prev_node = cur_src->elems[i];
+ Idx prev_node = cur_src->elems[i];
int naccepted = 0;
- int ret;
+ bool ok;
#ifdef DEBUG
re_token_type_t type = dfa->nodes[prev_node].type;
if (sctx->limits.nelem)
{
- int to_idx = str_idx + naccepted;
+ Idx to_idx = str_idx + naccepted;
if (check_dst_limits (mctx, &sctx->limits,
dfa->nexts[prev_node], to_idx,
prev_node, str_idx))
continue;
}
- ret = re_node_set_insert (cur_dest, prev_node);
- if (BE (ret == -1, 0))
+ ok = re_node_set_insert (cur_dest, prev_node);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
static reg_errcode_t
internal_function
-clean_state_log_if_needed (re_match_context_t *mctx, int next_state_log_idx)
+clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
{
- int top = mctx->state_log_top;
+ Idx top = mctx->state_log_top;
if (next_state_log_idx >= mctx->input.bufs_len
|| (next_state_log_idx >= mctx->input.valid_len
static reg_errcode_t
internal_function
-merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
- int num)
+merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
+ re_dfastate_t **src, Idx num)
{
- int st_idx;
+ Idx st_idx;
reg_errcode_t err;
for (st_idx = 0; st_idx < num; ++st_idx)
{
static reg_errcode_t
internal_function
-update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
- int str_idx, re_node_set *dest_nodes)
+update_cur_sifted_state (const re_match_context_t *mctx,
+ re_sift_context_t *sctx, Idx str_idx,
+ re_node_set *dest_nodes)
{
- re_dfa_t *const dfa = mctx->dfa;
- reg_errcode_t err;
+ const re_dfa_t *const dfa = mctx->dfa;
+ reg_errcode_t err = REG_NOERROR;
const re_node_set *candidates;
candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
: &mctx->state_log[str_idx]->nodes);
}
static reg_errcode_t
-internal_function
-add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
+internal_function __attribute_warn_unused_result__
+add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
const re_node_set *candidates)
{
reg_errcode_t err = REG_NOERROR;
- int i;
+ Idx i;
re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
if (BE (err != REG_NOERROR, 0))
{
err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
if (BE (err != REG_NOERROR, 0))
- return REG_ESPACE;
+ return REG_ESPACE;
for (i = 0; i < dest_nodes->nelem; i++)
- re_node_set_merge (&state->inveclosure,
- dfa->inveclosures + dest_nodes->elems[i]);
+ {
+ err = re_node_set_merge (&state->inveclosure,
+ dfa->inveclosures + dest_nodes->elems[i]);
+ if (BE (err != REG_NOERROR, 0))
+ return REG_ESPACE;
+ }
}
return re_node_set_add_intersect (dest_nodes, candidates,
&state->inveclosure);
static reg_errcode_t
internal_function
-sub_epsilon_src_nodes (re_dfa_t *dfa, int node, re_node_set *dest_nodes,
+sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
const re_node_set *candidates)
{
- int ecl_idx;
+ Idx ecl_idx;
reg_errcode_t err;
re_node_set *inv_eclosure = dfa->inveclosures + node;
re_node_set except_nodes;
re_node_set_init_empty (&except_nodes);
for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
{
- int cur_node = inv_eclosure->elems[ecl_idx];
+ Idx cur_node = inv_eclosure->elems[ecl_idx];
if (cur_node == node)
continue;
if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
{
- int edst1 = dfa->edests[cur_node].elems[0];
- int edst2 = ((dfa->edests[cur_node].nelem > 1)
- ? dfa->edests[cur_node].elems[1] : -1);
+ Idx edst1 = dfa->edests[cur_node].elems[0];
+ Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
+ ? dfa->edests[cur_node].elems[1] : REG_MISSING);
if ((!re_node_set_contains (inv_eclosure, edst1)
&& re_node_set_contains (dest_nodes, edst1))
- || (edst2 > 0
+ || (REG_VALID_NONZERO_INDEX (edst2)
&& !re_node_set_contains (inv_eclosure, edst2)
&& re_node_set_contains (dest_nodes, edst2)))
{
}
for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
{
- int cur_node = inv_eclosure->elems[ecl_idx];
+ Idx cur_node = inv_eclosure->elems[ecl_idx];
if (!re_node_set_contains (&except_nodes, cur_node))
{
- int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
+ Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
re_node_set_remove_at (dest_nodes, idx);
}
}
return REG_NOERROR;
}
-static int
+static bool
internal_function
-check_dst_limits (re_match_context_t *mctx, re_node_set *limits,
- int dst_node, int dst_idx, int src_node, int src_idx)
+check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
+ Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
{
- re_dfa_t *const dfa = mctx->dfa;
- int lim_idx, src_pos, dst_pos;
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx lim_idx, src_pos, dst_pos;
- int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
- int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
+ Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
+ Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
{
- int subexp_idx;
+ Idx subexp_idx;
struct re_backref_cache_entry *ent;
ent = mctx->bkref_ents + limits->elems[lim_idx];
subexp_idx = dfa->nodes[ent->node].opr.idx;
if (src_pos == dst_pos)
continue; /* This is unrelated limitation. */
else
- return 1;
+ return true;
}
- return 0;
+ return false;
}
static int
internal_function
-check_dst_limits_calc_pos_1 (re_match_context_t *mctx, int boundaries,
- int subexp_idx, int from_node, int bkref_idx)
+check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
+ Idx subexp_idx, Idx from_node, Idx bkref_idx)
{
- re_dfa_t *const dfa = mctx->dfa;
- re_node_set *eclosures = dfa->eclosures + from_node;
- int node_idx;
+ const re_dfa_t *const dfa = mctx->dfa;
+ const re_node_set *eclosures = dfa->eclosures + from_node;
+ Idx node_idx;
/* Else, we are on the boundary: examine the nodes on the epsilon
closure. */
for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
{
- int node = eclosures->elems[node_idx];
+ Idx node = eclosures->elems[node_idx];
switch (dfa->nodes[node].type)
{
case OP_BACK_REF:
- if (bkref_idx != -1)
+ if (bkref_idx != REG_MISSING)
{
struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
do
- {
- int dst, cpos;
+ {
+ Idx dst;
+ int cpos;
if (ent->node != node)
continue;
- if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map)
- && !(ent->eps_reachable_subexps_map & (1 << subexp_idx)))
+ if (subexp_idx < BITSET_WORD_BITS
+ && !(ent->eps_reachable_subexps_map
+ & ((bitset_word_t) 1 << subexp_idx)))
continue;
/* Recurse trying to reach the OP_OPEN_SUBEXP and
if (dst == from_node)
{
if (boundaries & 1)
- return -1;
+ return -1;
else /* if (boundaries & 2) */
- return 0;
+ return 0;
}
cpos =
if (cpos == 0 && (boundaries & 2))
return 0;
- ent->eps_reachable_subexps_map &= ~(1 << subexp_idx);
- }
+ if (subexp_idx < BITSET_WORD_BITS)
+ ent->eps_reachable_subexps_map
+ &= ~((bitset_word_t) 1 << subexp_idx);
+ }
while (ent++->more);
}
break;
static int
internal_function
-check_dst_limits_calc_pos (re_match_context_t *mctx, int limit, int subexp_idx,
- int from_node, int str_idx, int bkref_idx)
+check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
+ Idx subexp_idx, Idx from_node, Idx str_idx,
+ Idx bkref_idx)
{
struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
int boundaries;
static reg_errcode_t
internal_function
-check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
+check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
const re_node_set *candidates, re_node_set *limits,
- struct re_backref_cache_entry *bkref_ents, int str_idx)
+ struct re_backref_cache_entry *bkref_ents, Idx str_idx)
{
reg_errcode_t err;
- int node_idx, lim_idx;
+ Idx node_idx, lim_idx;
for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
{
- int subexp_idx;
+ Idx subexp_idx;
struct re_backref_cache_entry *ent;
ent = bkref_ents + limits->elems[lim_idx];
subexp_idx = dfa->nodes[ent->node].opr.idx;
if (ent->subexp_to == str_idx)
{
- int ops_node = -1;
- int cls_node = -1;
+ Idx ops_node = REG_MISSING;
+ Idx cls_node = REG_MISSING;
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
{
- int node = dest_nodes->elems[node_idx];
+ Idx node = dest_nodes->elems[node_idx];
re_token_type_t type = dfa->nodes[node].type;
if (type == OP_OPEN_SUBEXP
&& subexp_idx == dfa->nodes[node].opr.idx)
/* Check the limitation of the open subexpression. */
/* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
- if (ops_node >= 0)
+ if (REG_VALID_INDEX (ops_node))
{
err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
candidates);
}
/* Check the limitation of the close subexpression. */
- if (cls_node >= 0)
+ if (REG_VALID_INDEX (cls_node))
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
{
- int node = dest_nodes->elems[node_idx];
+ Idx node = dest_nodes->elems[node_idx];
if (!re_node_set_contains (dfa->inveclosures + node,
cls_node)
&& !re_node_set_contains (dfa->eclosures + node,
{
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
{
- int node = dest_nodes->elems[node_idx];
+ Idx node = dest_nodes->elems[node_idx];
re_token_type_t type = dfa->nodes[node].type;
if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
{
}
static reg_errcode_t
-internal_function
-sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
- int str_idx, const re_node_set *candidates)
+internal_function __attribute_warn_unused_result__
+sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
+ Idx str_idx, const re_node_set *candidates)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
- int node_idx, node;
+ Idx node_idx, node;
re_sift_context_t local_sctx;
- int first_idx = search_cur_bkref_entry (mctx, str_idx);
+ Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
- if (first_idx == -1)
+ if (first_idx == REG_MISSING)
return REG_NOERROR;
local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
{
- int enabled_idx;
+ Idx enabled_idx;
re_token_type_t type;
struct re_backref_cache_entry *entry;
node = candidates->elems[node_idx];
enabled_idx = first_idx;
do
{
- int subexp_len, to_idx, dst_node;
+ Idx subexp_len;
+ Idx to_idx;
+ Idx dst_node;
+ bool ok;
re_dfastate_t *cur_state;
if (entry->node != node)
}
local_sctx.last_node = node;
local_sctx.last_str_idx = str_idx;
- err = re_node_set_insert (&local_sctx.limits, enabled_idx);
- if (BE (err < 0, 0))
+ ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
+ if (BE (! ok, 0))
{
err = REG_ESPACE;
goto free_return;
re_node_set_remove (&local_sctx.limits, enabled_idx);
/* mctx->bkref_ents may have changed, reload the pointer. */
- entry = mctx->bkref_ents + enabled_idx;
+ entry = mctx->bkref_ents + enabled_idx;
}
while (enabled_idx++, entry++->more);
}
static int
internal_function
sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
- int node_idx, int str_idx, int max_str_idx)
+ Idx node_idx, Idx str_idx, Idx max_str_idx)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
int naccepted;
/* Check the node can accept `multi byte'. */
naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
update the destination of STATE_LOG. */
static re_dfastate_t *
-internal_function
+internal_function __attribute_warn_unused_result__
transit_state (reg_errcode_t *err, re_match_context_t *mctx,
re_dfastate_t *state)
{
trtable = state->word_trtable;
if (BE (trtable != NULL, 1))
- {
+ {
unsigned int context;
context
= re_string_context_at (&mctx->input,
}
/* Update the state_log if we need */
-re_dfastate_t *
+static re_dfastate_t *
internal_function
merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
re_dfastate_t *next_state)
{
- re_dfa_t *const dfa = mctx->dfa;
- int cur_idx = re_string_cur_idx (&mctx->input);
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx cur_idx = re_string_cur_idx (&mctx->input);
if (cur_idx > mctx->state_log_top)
{
unsigned int context;
re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
/* If (state_log[cur_idx] != 0), it implies that cur_idx is
- the destination of a multibyte char/collating element/
- back reference. Then the next state is the union set of
- these destinations and the results of the transition table. */
+ the destination of a multibyte char/collating element/
+ back reference. Then the next state is the union set of
+ these destinations and the results of the transition table. */
pstate = mctx->state_log[cur_idx];
log_nodes = pstate->entrance_nodes;
if (next_state != NULL)
- {
- table_nodes = next_state->entrance_nodes;
- *err = re_node_set_init_union (&next_nodes, table_nodes,
+ {
+ table_nodes = next_state->entrance_nodes;
+ *err = re_node_set_init_union (&next_nodes, table_nodes,
log_nodes);
- if (BE (*err != REG_NOERROR, 0))
+ if (BE (*err != REG_NOERROR, 0))
return NULL;
- }
+ }
else
- next_nodes = *log_nodes;
+ next_nodes = *log_nodes;
/* Note: We already add the nodes of the initial state,
then we don't need to add them here. */
re_string_cur_idx (&mctx->input) - 1,
mctx->eflags);
next_state = mctx->state_log[cur_idx]
- = re_acquire_state_context (err, dfa, &next_nodes, context);
+ = re_acquire_state_context (err, dfa, &next_nodes, context);
/* We don't need to check errors here, since the return value of
- this function is next_state and ERR is already set. */
+ this function is next_state and ERR is already set. */
if (table_nodes != NULL)
- re_node_set_free (&next_nodes);
+ re_node_set_free (&next_nodes);
}
if (BE (dfa->nbackref, 0) && next_state != NULL)
internal_function
find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
{
- re_dfastate_t *cur_state = NULL;
+ re_dfastate_t *cur_state;
do
{
- int max = mctx->state_log_top;
- int cur_str_idx = re_string_cur_idx (&mctx->input);
+ Idx max = mctx->state_log_top;
+ Idx cur_str_idx = re_string_cur_idx (&mctx->input);
do
{
- if (++cur_str_idx > max)
- return NULL;
- re_string_skip_bytes (&mctx->input, 1);
+ if (++cur_str_idx > max)
+ return NULL;
+ re_string_skip_bytes (&mctx->input, 1);
}
while (mctx->state_log[cur_str_idx] == NULL);
cur_state = merge_state_with_log (err, mctx, NULL);
}
- while (err == REG_NOERROR && cur_state == NULL);
+ while (*err == REG_NOERROR && cur_state == NULL);
return cur_state;
}
static reg_errcode_t
internal_function
check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
- int str_idx)
+ Idx str_idx)
{
- re_dfa_t *const dfa = mctx->dfa;
- int node_idx;
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx node_idx;
reg_errcode_t err;
/* TODO: This isn't efficient.
E.g. RE: (a){2} */
for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
{
- int node = cur_nodes->elems[node_idx];
+ Idx node = cur_nodes->elems[node_idx];
if (dfa->nodes[node].type == OP_OPEN_SUBEXP
- && dfa->nodes[node].opr.idx < (8 * sizeof (dfa->used_bkref_map))
- && dfa->used_bkref_map & (1 << dfa->nodes[node].opr.idx))
+ && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
+ && (dfa->used_bkref_map
+ & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
{
err = match_ctx_add_subtop (mctx, node, str_idx);
if (BE (err != REG_NOERROR, 0))
accepting the current input byte. */
static re_dfastate_t *
-transit_state_sb (err, mctx, state)
- reg_errcode_t *err;
- re_match_context_t *mctx;
- re_dfastate_t *state;
+transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
+ re_dfastate_t *state)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
re_node_set next_nodes;
re_dfastate_t *next_state;
- int node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
+ Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
unsigned int context;
*err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
return NULL;
for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
{
- int cur_node = state->nodes.elems[node_cnt];
+ Idx cur_node = state->nodes.elems[node_cnt];
if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
{
*err = re_node_set_merge (&next_nodes,
internal_function
transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
- int i;
+ Idx i;
for (i = 0; i < pstate->nodes.nelem; ++i)
{
re_node_set dest_nodes, *new_nodes;
- int cur_node_idx = pstate->nodes.elems[i];
- int naccepted, dest_idx;
+ Idx cur_node_idx = pstate->nodes.elems[i];
+ int naccepted;
+ Idx dest_idx;
unsigned int context;
re_dfastate_t *dest_state;
if (!dfa->nodes[cur_node_idx].accept_mb)
- continue;
+ continue;
if (dfa->nodes[cur_node_idx].constraint)
{
if (BE (err != REG_NOERROR, 0))
return err;
#ifdef DEBUG
- assert (dfa->nexts[cur_node_idx] != -1);
+ assert (dfa->nexts[cur_node_idx] != REG_MISSING);
#endif
new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
if (BE (err != REG_NOERROR, 0))
return err;
}
- context = re_string_context_at (&mctx->input, dest_idx - 1, mctx->eflags);
+ context = re_string_context_at (&mctx->input, dest_idx - 1,
+ mctx->eflags);
mctx->state_log[dest_idx]
= re_acquire_state_context (&err, dfa, &dest_nodes, context);
if (dest_state != NULL)
internal_function
transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
- int i;
- int cur_str_idx = re_string_cur_idx (&mctx->input);
+ Idx i;
+ Idx cur_str_idx = re_string_cur_idx (&mctx->input);
for (i = 0; i < nodes->nelem; ++i)
{
- int dest_str_idx, prev_nelem, bkc_idx;
- int node_idx = nodes->elems[i];
+ Idx dest_str_idx, prev_nelem, bkc_idx;
+ Idx node_idx = nodes->elems[i];
unsigned int context;
const re_token_t *node = dfa->nodes + node_idx;
re_node_set *new_dest_nodes;
/* And add the epsilon closures (which is `new_dest_nodes') of
the backreference to appropriate state_log. */
#ifdef DEBUG
- assert (dfa->nexts[node_idx] != -1);
+ assert (dfa->nexts[node_idx] != REG_MISSING);
#endif
for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
{
- int subexp_len;
+ Idx subexp_len;
re_dfastate_t *dest_state;
struct re_backref_cache_entry *bkref_ent;
bkref_ent = mctx->bkref_ents + bkc_idx;
delay these checking for prune_impossible_nodes(). */
static reg_errcode_t
-internal_function
-get_subexp (re_match_context_t *mctx, int bkref_node, int bkref_str_idx)
+internal_function __attribute_warn_unused_result__
+get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
{
- re_dfa_t *const dfa = mctx->dfa;
- int subexp_num, sub_top_idx;
+ const re_dfa_t *const dfa = mctx->dfa;
+ Idx subexp_num, sub_top_idx;
const char *buf = (const char *) re_string_get_buffer (&mctx->input);
/* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
- int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
- if (cache_idx != -1)
+ Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
+ if (cache_idx != REG_MISSING)
{
- const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
+ const struct re_backref_cache_entry *entry
+ = mctx->bkref_ents + cache_idx;
do
- if (entry->node == bkref_node)
+ if (entry->node == bkref_node)
return REG_NOERROR; /* We already checked it. */
while (entry++->more);
}
reg_errcode_t err;
re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
re_sub_match_last_t *sub_last;
- int sub_last_idx, sl_str, bkref_str_off;
+ Idx sub_last_idx, sl_str, bkref_str_off;
if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
continue; /* It isn't related. */
evaluated. */
for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
{
- int sl_str_diff;
+ regoff_t sl_str_diff;
sub_last = sub_top->lasts[sub_last_idx];
sl_str_diff = sub_last->str_idx - sl_str;
/* The matched string by the sub expression match with the substring
buf = (const char *) re_string_get_buffer (&mctx->input);
}
if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
- break; /* We don't need to search this sub expression any more. */
+ /* We don't need to search this sub expression any more. */
+ break;
}
bkref_str_off += sl_str_diff;
sl_str += sl_str_diff;
/* Then, search for the other last nodes of the sub expression. */
for (; sl_str <= bkref_str_idx; ++sl_str)
{
- int cls_node, sl_str_off;
+ Idx cls_node;
+ regoff_t sl_str_off;
const re_node_set *nodes;
sl_str_off = sl_str - sub_top->str_idx;
/* The matched string by the sub expression match with the substring
continue;
/* Does this state have a ')' of the sub expression? */
nodes = &mctx->state_log[sl_str]->nodes;
- cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
- if (cls_node == -1)
+ cls_node = find_subexp_node (dfa, nodes, subexp_num,
+ OP_CLOSE_SUBEXP);
+ if (cls_node == REG_MISSING)
continue; /* No. */
if (sub_top->path == NULL)
{
/* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
in the current context? */
err = check_arrival (mctx, sub_top->path, sub_top->node,
- sub_top->str_idx, cls_node, sl_str, OP_CLOSE_SUBEXP);
+ sub_top->str_idx, cls_node, sl_str,
+ OP_CLOSE_SUBEXP);
if (err == REG_NOMATCH)
continue;
if (BE (err != REG_NOERROR, 0))
static reg_errcode_t
internal_function
get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
- re_sub_match_last_t *sub_last, int bkref_node, int bkref_str)
+ re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
{
reg_errcode_t err;
- int to_idx;
+ Idx to_idx;
/* Can the subexpression arrive the back reference? */
err = check_arrival (mctx, &sub_last->path, sub_last->node,
- sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
+ sub_last->str_idx, bkref_node, bkref_str,
+ OP_OPEN_SUBEXP);
if (err != REG_NOERROR)
return err;
err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
nodes.
E.g. RE: (a){2} */
-static int
+static Idx
internal_function
find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
- int subexp_idx, int type)
+ Idx subexp_idx, int type)
{
- int cls_idx;
+ Idx cls_idx;
for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
{
- int cls_node = nodes->elems[cls_idx];
+ Idx cls_node = nodes->elems[cls_idx];
const re_token_t *node = dfa->nodes + cls_node;
if (node->type == type
&& node->opr.idx == subexp_idx)
return cls_node;
}
- return -1;
+ return REG_MISSING;
}
/* Check whether the node TOP_NODE at TOP_STR can arrive to the node
Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
static reg_errcode_t
-internal_function
-check_arrival (re_match_context_t *mctx, state_array_t *path,
- int top_node, int top_str, int last_node, int last_str,
- int type)
+internal_function __attribute_warn_unused_result__
+check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
+ Idx top_str, Idx last_node, Idx last_str, int type)
{
- re_dfa_t *const dfa = mctx->dfa;
- reg_errcode_t err;
- int subexp_num, backup_cur_idx, str_idx, null_cnt;
+ const re_dfa_t *const dfa = mctx->dfa;
+ reg_errcode_t err = REG_NOERROR;
+ Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
re_dfastate_t *cur_state = NULL;
re_node_set *cur_nodes, next_nodes;
re_dfastate_t **backup_state_log;
if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
{
re_dfastate_t **new_array;
- int old_alloc = path->alloc;
- path->alloc += last_str + mctx->max_mb_elem_len + 1;
- new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
- if (new_array == NULL)
- {
- path->alloc = old_alloc;
- return REG_ESPACE;
- }
+ Idx old_alloc = path->alloc;
+ Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
+ if (BE (new_alloc < old_alloc, 0)
+ || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
+ return REG_ESPACE;
+ new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
+ if (BE (new_array == NULL, 0))
+ return REG_ESPACE;
path->array = new_array;
+ path->alloc = new_alloc;
memset (new_array + old_alloc, '\0',
sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
}
- str_idx = path->next_idx == 0 ? top_str : path->next_idx;
+ str_idx = path->next_idx ? path->next_idx : top_str;
/* Temporary modify MCTX. */
backup_state_log = mctx->state_log;
if (cur_state && cur_state->has_backref)
{
err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
- if (BE ( err != REG_NOERROR, 0))
+ if (BE (err != REG_NOERROR, 0))
return err;
}
else
{
err = expand_bkref_cache (mctx, &next_nodes, str_idx,
subexp_num, type);
- if (BE ( err != REG_NOERROR, 0))
+ if (BE (err != REG_NOERROR, 0))
{
re_node_set_free (&next_nodes);
return err;
if (cur_state)
{
err = check_arrival_add_next_nodes (mctx, str_idx,
- &cur_state->non_eps_nodes, &next_nodes);
+ &cur_state->non_eps_nodes,
+ &next_nodes);
if (BE (err != REG_NOERROR, 0))
{
re_node_set_free (&next_nodes);
}
err = expand_bkref_cache (mctx, &next_nodes, str_idx,
subexp_num, type);
- if (BE ( err != REG_NOERROR, 0))
+ if (BE (err != REG_NOERROR, 0))
{
re_node_set_free (&next_nodes);
return err;
Can't we unify them? */
static reg_errcode_t
-internal_function
-check_arrival_add_next_nodes (re_match_context_t *mctx, int str_idx,
- re_node_set *cur_nodes,
- re_node_set *next_nodes)
+internal_function __attribute_warn_unused_result__
+check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
+ re_node_set *cur_nodes, re_node_set *next_nodes)
{
- re_dfa_t *const dfa = mctx->dfa;
- int result;
- int cur_idx;
- reg_errcode_t err;
+ const re_dfa_t *const dfa = mctx->dfa;
+ bool ok;
+ Idx cur_idx;
+#ifdef RE_ENABLE_I18N
+ reg_errcode_t err = REG_NOERROR;
+#endif
re_node_set union_set;
re_node_set_init_empty (&union_set);
for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
{
int naccepted = 0;
- int cur_node = cur_nodes->elems[cur_idx];
+ Idx cur_node = cur_nodes->elems[cur_idx];
#ifdef DEBUG
re_token_type_t type = dfa->nodes[cur_node].type;
assert (!IS_EPSILON_NODE (type));
if (naccepted > 1)
{
re_dfastate_t *dest_state;
- int next_node = dfa->nexts[cur_node];
- int next_idx = str_idx + naccepted;
+ Idx next_node = dfa->nexts[cur_node];
+ Idx next_idx = str_idx + naccepted;
dest_state = mctx->state_log[next_idx];
re_node_set_empty (&union_set);
if (dest_state)
return err;
}
}
- result = re_node_set_insert (&union_set, next_node);
- if (BE (result < 0, 0))
+ ok = re_node_set_insert (&union_set, next_node);
+ if (BE (! ok, 0))
{
re_node_set_free (&union_set);
return REG_ESPACE;
if (naccepted
|| check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
{
- result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
- if (BE (result < 0, 0))
+ ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
+ if (BE (! ok, 0))
{
re_node_set_free (&union_set);
return REG_ESPACE;
static reg_errcode_t
internal_function
-check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
- int ex_subexp, int type)
+check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
+ Idx ex_subexp, int type)
{
reg_errcode_t err;
- int idx, outside_node;
+ Idx idx, outside_node;
re_node_set new_nodes;
#ifdef DEBUG
assert (cur_nodes->nelem);
for (idx = 0; idx < cur_nodes->nelem; ++idx)
{
- int cur_node = cur_nodes->elems[idx];
- re_node_set *eclosure = dfa->eclosures + cur_node;
+ Idx cur_node = cur_nodes->elems[idx];
+ const re_node_set *eclosure = dfa->eclosures + cur_node;
outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
- if (outside_node == -1)
+ if (outside_node == REG_MISSING)
{
/* There are no problematic nodes, just merge them. */
err = re_node_set_merge (&new_nodes, eclosure);
problematic append it to DST_NODES. */
static reg_errcode_t
-internal_function
-check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
- int target, int ex_subexp, int type)
+internal_function __attribute_warn_unused_result__
+check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
+ Idx target, Idx ex_subexp, int type)
{
- int cur_node;
+ Idx cur_node;
for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
{
- int err;
+ bool ok;
if (dfa->nodes[cur_node].type == type
&& dfa->nodes[cur_node].opr.idx == ex_subexp)
{
if (type == OP_CLOSE_SUBEXP)
{
- err = re_node_set_insert (dst_nodes, cur_node);
- if (BE (err == -1, 0))
+ ok = re_node_set_insert (dst_nodes, cur_node);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
break;
}
- err = re_node_set_insert (dst_nodes, cur_node);
- if (BE (err == -1, 0))
+ ok = re_node_set_insert (dst_nodes, cur_node);
+ if (BE (! ok, 0))
return REG_ESPACE;
if (dfa->edests[cur_node].nelem == 0)
break;
if (dfa->edests[cur_node].nelem == 2)
{
+ reg_errcode_t err;
err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
dfa->edests[cur_node].elems[1],
ex_subexp, type);
in MCTX->BKREF_ENTS. */
static reg_errcode_t
-internal_function
+internal_function __attribute_warn_unused_result__
expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
- int cur_str, int subexp_num, int type)
+ Idx cur_str, Idx subexp_num, int type)
{
- re_dfa_t *const dfa = mctx->dfa;
+ const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
- int cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
+ Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
struct re_backref_cache_entry *ent;
- if (cache_idx_start == -1)
+ if (cache_idx_start == REG_MISSING)
return REG_NOERROR;
restart:
ent = mctx->bkref_ents + cache_idx_start;
do
{
- int to_idx, next_node;
+ Idx to_idx, next_node;
/* Is this entry ENT is appropriate? */
if (!re_node_set_contains (cur_nodes, ent->node))
next_node = dfa->nexts[ent->node];
if (mctx->state_log[to_idx])
{
- int ret;
+ bool ok;
if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
next_node))
continue;
err = re_node_set_init_copy (&union_set,
&mctx->state_log[to_idx]->nodes);
- ret = re_node_set_insert (&union_set, next_node);
- if (BE (err != REG_NOERROR || ret < 0, 0))
+ ok = re_node_set_insert (&union_set, next_node);
+ if (BE (err != REG_NOERROR || ! ok, 0))
{
re_node_set_free (&union_set);
err = err != REG_NOERROR ? err : REG_ESPACE;
}
/* Build transition table for the state.
- Return 1 if succeeded, otherwise return NULL. */
+ Return true if successful. */
-static int
+static bool
internal_function
-build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
+build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
{
reg_errcode_t err;
- int i, j, ch, need_word_trtable = 0;
- unsigned int elem, mask;
- int dests_node_malloced = 0, dest_states_malloced = 0;
- int ndests; /* Number of the destination states from `state'. */
+ Idx i, j;
+ int ch;
+ bool need_word_trtable = false;
+ bitset_word_t elem, mask;
+ bool dests_node_malloced = false;
+ bool dest_states_malloced = false;
+ Idx ndests; /* Number of the destination states from `state'. */
re_dfastate_t **trtable;
re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
re_node_set follows, *dests_node;
- bitset *dests_ch;
- bitset acceptable;
+ bitset_t *dests_ch;
+ bitset_t acceptable;
+
+ struct dests_alloc
+ {
+ re_node_set dests_node[SBC_MAX];
+ bitset_t dests_ch[SBC_MAX];
+ } *dests_alloc;
/* We build DFA states which corresponds to the destination nodes
from `state'. `dests_node[i]' represents the nodes which i-th
destination state contains, and `dests_ch[i]' represents the
characters which i-th destination state accepts. */
-#ifdef _LIBC
- if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX))
- dests_node = (re_node_set *)
- alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
+ if (__libc_use_alloca (sizeof (struct dests_alloc)))
+ dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
else
-#endif
{
- dests_node = (re_node_set *)
- malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
- if (BE (dests_node == NULL, 0))
- return 0;
- dests_node_malloced = 1;
+ dests_alloc = re_malloc (struct dests_alloc, 1);
+ if (BE (dests_alloc == NULL, 0))
+ return false;
+ dests_node_malloced = true;
}
- dests_ch = (bitset *) (dests_node + SBC_MAX);
+ dests_node = dests_alloc->dests_node;
+ dests_ch = dests_alloc->dests_ch;
/* Initialize transiton table. */
state->word_trtable = state->trtable = NULL;
/* At first, group all nodes belonging to `state' into several
destinations. */
ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
- if (BE (ndests <= 0, 0))
+ if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
{
if (dests_node_malloced)
- free (dests_node);
- /* Return 0 in case of an error, 1 otherwise. */
+ free (dests_alloc);
if (ndests == 0)
{
state->trtable = (re_dfastate_t **)
calloc (sizeof (re_dfastate_t *), SBC_MAX);
- return 1;
+ if (BE (state->trtable == NULL, 0))
+ return false;
+ return true;
}
- return 0;
+ return false;
}
err = re_node_set_alloc (&follows, ndests + 1);
if (BE (err != REG_NOERROR, 0))
goto out_free;
-#ifdef _LIBC
- if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
+ /* Avoid arithmetic overflow in size calculation. */
+ if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
+ / (3 * sizeof (re_dfastate_t *)))
+ < ndests),
+ 0))
+ goto out_free;
+
+ if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
+ ndests * 3 * sizeof (re_dfastate_t *)))
dest_states = (re_dfastate_t **)
alloca (ndests * 3 * sizeof (re_dfastate_t *));
else
-#endif
{
dest_states = (re_dfastate_t **)
malloc (ndests * 3 * sizeof (re_dfastate_t *));
for (i = 0; i < ndests; ++i)
re_node_set_free (dests_node + i);
if (dests_node_malloced)
- free (dests_node);
- return 0;
+ free (dests_alloc);
+ return false;
}
- dest_states_malloced = 1;
+ dest_states_malloced = true;
}
dest_states_word = dest_states + ndests;
dest_states_nl = dest_states_word + ndests;
/* Then build the states for all destinations. */
for (i = 0; i < ndests; ++i)
{
- int next_node;
+ Idx next_node;
re_node_set_empty (&follows);
/* Merge the follows of this destination states. */
for (j = 0; j < dests_node[i].nelem; ++j)
{
next_node = dfa->nexts[dests_node[i].elems[j]];
- if (next_node != -1)
+ if (next_node != REG_MISSING)
{
err = re_node_set_merge (&follows, dfa->eclosures + next_node);
if (BE (err != REG_NOERROR, 0))
goto out_free;
if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
- need_word_trtable = 1;
+ need_word_trtable = true;
dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
CONTEXT_NEWLINE);
if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
goto out_free;
- }
+ }
else
{
dest_states_word[i] = dest_states[i];
goto out_free;
/* For all characters ch...: */
- for (i = 0; i < BITSET_UINTS; ++i)
- for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
+ for (i = 0; i < BITSET_WORDS; ++i)
+ for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
elem;
mask <<= 1, elem >>= 1, ++ch)
if (BE (elem & 1, 0))
goto out_free;
/* For all characters ch...: */
- for (i = 0; i < BITSET_UINTS; ++i)
- for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
+ for (i = 0; i < BITSET_WORDS; ++i)
+ for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
elem;
mask <<= 1, elem >>= 1, ++ch)
if (BE (elem & 1, 0))
re_node_set_free (dests_node + i);
if (dests_node_malloced)
- free (dests_node);
+ free (dests_alloc);
- return 1;
+ return true;
}
/* Group all nodes belonging to STATE into several destinations.
to DESTS_NODE[i] and set the characters accepted by the destination
to DEST_CH[i]. This function return the number of destinations. */
-static int
+static Idx
internal_function
-group_nodes_into_DFAstates (re_dfa_t *dfa, const re_dfastate_t *state,
- re_node_set *dests_node, bitset *dests_ch)
+group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
+ re_node_set *dests_node, bitset_t *dests_ch)
{
reg_errcode_t err;
- int result;
- int i, j, k;
- int ndests; /* Number of the destinations from `state'. */
- bitset accepts; /* Characters a node can accept. */
+ bool ok;
+ Idx i, j, k;
+ Idx ndests; /* Number of the destinations from `state'. */
+ bitset_t accepts; /* Characters a node can accept. */
const re_node_set *cur_nodes = &state->nodes;
bitset_empty (accepts);
ndests = 0;
}
#ifdef RE_ENABLE_I18N
else if (type == OP_UTF8_PERIOD)
- {
- memset (accepts, 255, sizeof (unsigned int) * BITSET_UINTS / 2);
+ {
+ if (ASCII_CHARS % BITSET_WORD_BITS == 0)
+ memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
+ else
+ bitset_merge (accepts, utf8_sb_map);
if (!(dfa->syntax & RE_DOT_NEWLINE))
bitset_clear (accepts, '\n');
if (dfa->syntax & RE_DOT_NOT_NULL)
bitset_clear (accepts, '\0');
- }
+ }
#endif
else
continue;
{
if (constraint & NEXT_NEWLINE_CONSTRAINT)
{
- int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
+ bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
bitset_empty (accepts);
if (accepts_newline)
bitset_set (accepts, NEWLINE_CHAR);
if (constraint & NEXT_WORD_CONSTRAINT)
{
- unsigned int any_set = 0;
+ bitset_word_t any_set = 0;
if (type == CHARACTER && !node->word_char)
{
bitset_empty (accepts);
}
#ifdef RE_ENABLE_I18N
if (dfa->mb_cur_max > 1)
- for (j = 0; j < BITSET_UINTS; ++j)
+ for (j = 0; j < BITSET_WORDS; ++j)
any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
else
#endif
- for (j = 0; j < BITSET_UINTS; ++j)
+ for (j = 0; j < BITSET_WORDS; ++j)
any_set |= (accepts[j] &= dfa->word_char[j]);
if (!any_set)
continue;
}
if (constraint & NEXT_NOTWORD_CONSTRAINT)
{
- unsigned int any_set = 0;
+ bitset_word_t any_set = 0;
if (type == CHARACTER && node->word_char)
{
bitset_empty (accepts);
}
#ifdef RE_ENABLE_I18N
if (dfa->mb_cur_max > 1)
- for (j = 0; j < BITSET_UINTS; ++j)
+ for (j = 0; j < BITSET_WORDS; ++j)
any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
else
#endif
- for (j = 0; j < BITSET_UINTS; ++j)
+ for (j = 0; j < BITSET_WORDS; ++j)
any_set |= (accepts[j] &= ~dfa->word_char[j]);
if (!any_set)
continue;
state. Above, we make sure that accepts is not empty. */
for (j = 0; j < ndests; ++j)
{
- bitset intersec; /* Intersection sets, see below. */
- bitset remains;
+ bitset_t intersec; /* Intersection sets, see below. */
+ bitset_t remains;
/* Flags, see below. */
- int has_intersec, not_subset, not_consumed;
+ bitset_word_t has_intersec, not_subset, not_consumed;
/* Optimization, skip if this state doesn't accept the character. */
if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
/* Enumerate the intersection set of this state and `accepts'. */
has_intersec = 0;
- for (k = 0; k < BITSET_UINTS; ++k)
+ for (k = 0; k < BITSET_WORDS; ++k)
has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
/* And skip if the intersection set is empty. */
if (!has_intersec)
/* Then check if this state is a subset of `accepts'. */
not_subset = not_consumed = 0;
- for (k = 0; k < BITSET_UINTS; ++k)
+ for (k = 0; k < BITSET_WORDS; ++k)
{
not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
}
/* Put the position in the current group. */
- result = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
- if (BE (result < 0, 0))
+ ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
+ if (BE (! ok, 0))
goto error_return;
/* If all characters are consumed, go to next node. */
error_return:
for (j = 0; j < ndests; ++j)
re_node_set_free (dests_node + j);
- return -1;
+ return REG_MISSING;
}
#ifdef RE_ENABLE_I18N
static int
internal_function
-check_node_accept_bytes (re_dfa_t *dfa, int node_idx,
- const re_string_t *input, int str_idx)
+check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
+ const re_string_t *input, Idx str_idx)
{
const re_token_t *node = dfa->nodes + node_idx;
int char_len, elem_len;
- int i;
+ Idx i;
if (BE (node->type == OP_UTF8_PERIOD, 0))
{
if (node->type == OP_PERIOD)
{
if (char_len <= 1)
- return 0;
+ return 0;
/* FIXME: I don't think this if is needed, as both '\n'
and '\0' are char_len == 1. */
/* '.' accepts any one character except the following two cases. */
# ifdef _LIBC
const unsigned char *pin
= ((const unsigned char *) re_string_get_buffer (input) + str_idx);
- int j;
+ Idx j;
uint32_t nrules;
# endif /* _LIBC */
int match_len = 0;
_NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
indirect = (const int32_t *)
_NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
- idx = findidx (&cp);
+ int32_t idx = findidx (&cp);
if (idx > 0)
for (i = 0; i < cset->nequiv_classes; ++i)
{
int32_t equiv_class_idx = cset->equiv_classes[i];
- size_t weight_len = weights[idx];
- if (weight_len == weights[equiv_class_idx])
+ size_t weight_len = weights[idx & 0xffffff];
+ if (weight_len == weights[equiv_class_idx & 0xffffff]
+ && (idx >> 24) == (equiv_class_idx >> 24))
{
- int cnt = 0;
+ Idx cnt = 0;
+
+ idx &= 0xffffff;
+ equiv_class_idx &= 0xffffff;
+
while (cnt <= weight_len
&& (weights[equiv_class_idx + 1 + cnt]
== weights[idx + 1 + cnt]))
# endif /* _LIBC */
{
/* match with range expression? */
-#if __GNUC__ >= 2
+#if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
#else
wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
# ifdef _LIBC
static unsigned int
-find_collation_sequence_value (mbs, mbs_len)
- const unsigned char *mbs;
- size_t mbs_len;
+internal_function
+find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
{
uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
if (nrules == 0)
for (idx = 0; idx < extrasize;)
{
- int mbs_cnt, found = 0;
+ int mbs_cnt;
+ bool found = false;
int32_t elem_mbs_len;
/* Skip the name of collating element name. */
idx = idx + extra[idx] + 1;
break;
if (mbs_cnt == elem_mbs_len)
/* Found the entry. */
- found = 1;
+ found = true;
}
/* Skip the byte sequence of the collating element. */
idx += elem_mbs_len;
/* Check whether the node accepts the byte which is IDX-th
byte of the INPUT. */
-static int
+static bool
internal_function
check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
- int idx)
+ Idx idx)
{
unsigned char ch;
ch = re_string_byte_at (&mctx->input, idx);
{
case CHARACTER:
if (node->opr.c != ch)
- return 0;
+ return false;
break;
case SIMPLE_BRACKET:
if (!bitset_contain (node->opr.sbcset, ch))
- return 0;
+ return false;
break;
#ifdef RE_ENABLE_I18N
case OP_UTF8_PERIOD:
- if (ch >= 0x80)
- return 0;
+ if (ch >= ASCII_CHARS)
+ return false;
/* FALLTHROUGH */
#endif
case OP_PERIOD:
if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
|| (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
- return 0;
+ return false;
break;
default:
- return 0;
+ return false;
}
if (node->constraint)
unsigned int context = re_string_context_at (&mctx->input, idx,
mctx->eflags);
if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
- return 0;
+ return false;
}
- return 1;
+ return true;
}
/* Extend the buffers, if the buffers have run out. */
static reg_errcode_t
-internal_function
+internal_function __attribute_warn_unused_result__
extend_buffers (re_match_context_t *mctx)
{
reg_errcode_t ret;
re_string_t *pstr = &mctx->input;
+ /* Avoid overflow. */
+ if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
+ return REG_ESPACE;
+
/* Double the lengthes of the buffers. */
ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
if (BE (ret != REG_NOERROR, 0))
/* Initialize MCTX. */
static reg_errcode_t
-internal_function
-match_ctx_init (re_match_context_t *mctx, int eflags, int n)
+internal_function __attribute_warn_unused_result__
+match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
{
mctx->eflags = eflags;
- mctx->match_last = -1;
+ mctx->match_last = REG_MISSING;
if (n > 0)
{
+ /* Avoid overflow. */
+ size_t max_object_size =
+ MAX (sizeof (struct re_backref_cache_entry),
+ sizeof (re_sub_match_top_t *));
+ if (BE (SIZE_MAX / max_object_size < n, 0))
+ return REG_ESPACE;
+
mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
internal_function
match_ctx_clean (re_match_context_t *mctx)
{
- int st_idx;
+ Idx st_idx;
for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
{
- int sl_idx;
+ Idx sl_idx;
re_sub_match_top_t *top = mctx->sub_tops[st_idx];
for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
{
*/
static reg_errcode_t
-internal_function
-match_ctx_add_entry (re_match_context_t *mctx, int node, int str_idx,
- int from, int to)
+internal_function __attribute_warn_unused_result__
+match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
+ Idx to)
{
if (mctx->nbkref_ents >= mctx->abkref_ents)
{
A backreference does not epsilon-transition unless it is empty, so set
to all zeros if FROM != TO. */
mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
- = (from == to ? ~0 : 0);
+ = (from == to ? -1 : 0);
mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
if (mctx->max_mb_elem_len < to - from)
return REG_NOERROR;
}
-/* Search for the first entry which has the same str_idx, or -1 if none is
+/* Return the first entry with the same str_idx, or REG_MISSING if none is
found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
-static int
+static Idx
internal_function
-search_cur_bkref_entry (re_match_context_t *mctx, int str_idx)
+search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
{
- int left, right, mid, last;
+ Idx left, right, mid, last;
last = right = mctx->nbkref_ents;
for (left = 0; left < right;)
{
if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
return left;
else
- return -1;
+ return REG_MISSING;
}
/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
at STR_IDX. */
static reg_errcode_t
-internal_function
-match_ctx_add_subtop (re_match_context_t *mctx, int node, int str_idx)
+internal_function __attribute_warn_unused_result__
+match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
{
#ifdef DEBUG
assert (mctx->sub_tops != NULL);
#endif
if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
{
- int new_asub_tops = mctx->asub_tops * 2;
+ Idx new_asub_tops = mctx->asub_tops * 2;
re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
re_sub_match_top_t *,
new_asub_tops);
static re_sub_match_last_t *
internal_function
-match_ctx_add_sublast (re_sub_match_top_t *subtop, int node, int str_idx)
+match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
{
re_sub_match_last_t *new_entry;
if (BE (subtop->nlasts == subtop->alasts, 0))
{
- int new_alasts = 2 * subtop->alasts + 1;
+ Idx new_alasts = 2 * subtop->alasts + 1;
re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
re_sub_match_last_t *,
new_alasts);
static void
internal_function
-sift_ctx_init (re_sift_context_t *sctx,
- re_dfastate_t **sifted_sts,
- re_dfastate_t **limited_sts,
- int last_node, int last_str_idx)
+sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
+ re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
{
sctx->sifted_states = sifted_sts;
sctx->limited_states = limited_sts;
projects / gnulib.git / blobdiff