diff options
Diffstat (limited to 'posix')
-rw-r--r-- | posix/confstr.c | 12 | ||||
-rw-r--r-- | posix/regcomp.c | 34 | ||||
-rw-r--r-- | posix/regex_internal.h | 12 | ||||
-rw-r--r-- | posix/regexec.c | 99 |
4 files changed, 62 insertions, 95 deletions
diff --git a/posix/confstr.c b/posix/confstr.c index da929c25df..185b02fd8a 100644 --- a/posix/confstr.c +++ b/posix/confstr.c @@ -113,7 +113,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_ILP32_OFF32_CFLAGS: #ifdef __ILP32_OFF32_CFLAGS # if _POSIX_V6_ILP32_OFF32 == -1 -# error __ILP32_OFF32_CFLAGS should not be defined +# error "__ILP32_OFF32_CFLAGS should not be defined" # elif !defined _POSIX_V6_ILP32_OFF32 if (__sysconf (_SC_V6_ILP32_OFF32) < 0) break; @@ -127,7 +127,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_ILP32_OFFBIG_CFLAGS: #ifdef __ILP32_OFFBIG_CFLAGS # if _POSIX_V6_ILP32_OFFBIG == -1 -# error __ILP32_OFFBIG_CFLAGS should not be defined +# error "__ILP32_OFFBIG_CFLAGS should not be defined" # elif !defined _POSIX_V6_ILP32_OFFBIG if (__sysconf (_SC_V6_ILP32_OFFBIG) < 0) break; @@ -141,7 +141,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_LP64_OFF64_CFLAGS: #ifdef __LP64_OFF64_CFLAGS # if _POSIX_V6_LP64_OFF64 == -1 -# error __LP64_OFF64_CFLAGS should not be defined +# error "__LP64_OFF64_CFLAGS should not be defined" # elif !defined _POSIX_V6_LP64_OFF64 if (__sysconf (_SC_V6_LP64_OFF64) < 0) break; @@ -155,7 +155,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_ILP32_OFF32_LDFLAGS: #ifdef __ILP32_OFF32_LDFLAGS # if _POSIX_V6_ILP32_OFF32 == -1 -# error __ILP32_OFF32_LDFLAGS should not be defined +# error "__ILP32_OFF32_LDFLAGS should not be defined" # elif !defined _POSIX_V6_ILP32_OFF32 if (__sysconf (_SC_V6_ILP32_OFF32) < 0) break; @@ -169,7 +169,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_ILP32_OFFBIG_LDFLAGS: #ifdef __ILP32_OFFBIG_LDFLAGS # if _POSIX_V6_ILP32_OFFBIG == -1 -# error __ILP32_OFFBIG_LDFLAGS should not be defined +# error "__ILP32_OFFBIG_LDFLAGS should not be defined" # elif !defined _POSIX_V6_ILP32_OFFBIG if (__sysconf (_SC_V6_ILP32_OFFBIG) < 0) break; @@ -183,7 +183,7 @@ confstr (name, buf, len) case _CS_POSIX_V6_LP64_OFF64_LDFLAGS: #ifdef __LP64_OFF64_LDFLAGS # if _POSIX_V6_LP64_OFF64 == -1 -# error __LP64_OFF64_LDFLAGS should not be defined +# error "__LP64_OFF64_LDFLAGS should not be defined" # elif !defined _POSIX_V6_LP64_OFF64 if (__sysconf (_SC_V6_LP64_OFF64) < 0) break; diff --git a/posix/regcomp.c b/posix/regcomp.c index 675f816f60..5de5bf725a 100644 --- a/posix/regcomp.c +++ b/posix/regcomp.c @@ -596,8 +596,6 @@ free_dfa_content (re_dfa_t *dfa) { int i, j; - re_free (dfa->subexps); - if (dfa->nodes) for (i = 0; i < dfa->nodes_len; ++i) { @@ -884,9 +882,6 @@ init_dfa (dfa, pat_len) dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size); dfa->state_hash_mask = table_size - 1; - dfa->subexps_alloc = 1; - dfa->subexps = re_malloc (re_subexp_t, dfa->subexps_alloc); - dfa->mb_cur_max = MB_CUR_MAX; #ifdef _LIBC if (dfa->mb_cur_max == 6 @@ -950,8 +945,7 @@ init_dfa (dfa, pat_len) } #endif - if (BE (dfa->nodes == NULL || dfa->state_table == NULL - || dfa->subexps == NULL, 0)) + if (BE (dfa->nodes == NULL || dfa->state_table == NULL, 0)) return REG_ESPACE; return REG_NOERROR; } @@ -1028,7 +1022,7 @@ create_initial_state (dfa) re_token_t *clexp_node; clexp_node = dfa->nodes + init_nodes.elems[clexp_idx]; if (clexp_node->type == OP_CLOSE_SUBEXP - && clexp_node->opr.idx + 1 == dfa->nodes[node_idx].opr.idx) + && clexp_node->opr.idx == dfa->nodes[node_idx].opr.idx) break; } if (clexp_idx == init_nodes.nelem) @@ -1837,7 +1831,7 @@ peek_token (token, input, syntax) if (!(syntax & RE_NO_BK_REFS)) { token->type = OP_BACK_REF; - token->opr.idx = c2 - '0'; + token->opr.idx = c2 - '1'; } break; case '<': @@ -2295,13 +2289,12 @@ parse_expression (regexp, preg, token, syntax, nest, err) return NULL; break; case OP_BACK_REF: - if (BE (preg->re_nsub < token->opr.idx - || dfa->subexps[token->opr.idx - 1].end == -1, 0)) + if (!BE (dfa->completed_bkref_map & (1 << token->opr.idx), 1)) { *err = REG_ESUBREG; return NULL; } - dfa->used_bkref_map |= 1 << (token->opr.idx - 1); + dfa->used_bkref_map |= 1 << token->opr.idx; tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { @@ -2472,21 +2465,6 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) bin_tree_t *tree, *left_par, *right_par; size_t cur_nsub; cur_nsub = preg->re_nsub++; - if (BE (dfa->subexps_alloc < preg->re_nsub, 0)) - { - re_subexp_t *new_array; - dfa->subexps_alloc *= 2; - new_array = re_realloc (dfa->subexps, re_subexp_t, dfa->subexps_alloc); - if (BE (new_array == NULL, 0)) - { - dfa->subexps_alloc /= 2; - *err = REG_ESPACE; - return NULL; - } - dfa->subexps = new_array; - } - dfa->subexps[cur_nsub].start = dfa->nodes_len; - dfa->subexps[cur_nsub].end = -1; left_par = re_dfa_add_tree_node (dfa, NULL, NULL, token); if (BE (left_par == NULL, 0)) @@ -2512,7 +2490,7 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) return NULL; } right_par = re_dfa_add_tree_node (dfa, NULL, NULL, token); - dfa->subexps[cur_nsub].end = dfa->nodes_len; + dfa->completed_bkref_map |= 1 << cur_nsub; tree = ((tree == NULL) ? right_par : create_tree (dfa, tree, right_par, CONCAT, 0)); tree = create_tree (dfa, left_par, tree, CONCAT, 0); diff --git a/posix/regex_internal.h b/posix/regex_internal.h index 703d409eb8..1345067a89 100644 --- a/posix/regex_internal.h +++ b/posix/regex_internal.h @@ -496,13 +496,6 @@ struct re_dfastate_t }; typedef struct re_dfastate_t re_dfastate_t; -typedef struct -{ - /* start <= node < end */ - int start; - int end; -} re_subexp_t; - struct re_state_table_entry { int num; @@ -607,7 +600,6 @@ struct re_fail_stack_t struct re_dfa_t { - re_subexp_t *subexps; re_token_t *nodes; int nodes_alloc; int nodes_len; @@ -627,13 +619,15 @@ struct re_dfa_t int str_tree_storage_idx; /* number of subexpressions `re_nsub' is in regex_t. */ - int subexps_alloc; unsigned int state_hash_mask; int states_alloc; int init_node; int nbackref; /* The number of backreference in this dfa. */ + /* Bitmap expressing which backreference is used. */ unsigned int used_bkref_map; + unsigned int completed_bkref_map; + unsigned int has_plural_match : 1; /* If this dfa has "multibyte node", which is a backreference or a node which can accept multibyte character or multi character diff --git a/posix/regexec.c b/posix/regexec.c index 5877adeb55..22b806439b 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -1260,7 +1260,7 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs) #endif /* RE_ENABLE_I18N */ if (type == OP_BACK_REF) { - int subexp_idx = dfa->nodes[node].opr.idx; + int subexp_idx = dfa->nodes[node].opr.idx + 1; naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so; if (fs != NULL) { @@ -1853,7 +1853,7 @@ check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx) int subexp_idx; struct re_backref_cache_entry *ent; ent = mctx->bkref_ents + limits->elems[lim_idx]; - subexp_idx = dfa->nodes[ent->node].opr.idx - 1; + subexp_idx = dfa->nodes[ent->node].opr.idx; dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx], subexp_idx, dst_node, dst_idx, @@ -1891,49 +1891,48 @@ check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx) switch (dfa->nodes[node].type) { case OP_BACK_REF: - { - struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx; - do - { - int dst, cpos; - - if (ent->node != node) - continue; - - if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map) - && (ent->eps_reachable_subexps_map - & (1 << (subexp_idx - 1))) == 0) - continue; + if (bkref_idx != -1) + { + struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx; + do + { + int dst, cpos; - /* Recurse trying to reach the OP_OPEN_SUBEXP and - OP_CLOSE_SUBEXP cases below. But, if the - destination node is the same node as the source - node, don't recurse because it would cause an - infinite loop: a regex that exhibits this behavior - is ()\1*\1* */ - dst = dfa->edests[node].elems[0]; - if (dst == from_node) - { - if (boundaries & 1) - return -1; - else /* if (boundaries & 2) */ - return 0; - } + if (ent->node != node) + continue; - cpos = check_dst_limits_calc_pos_1 (mctx, boundaries, - subexp_idx, dst, bkref_idx); + if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map) + && !(ent->eps_reachable_subexps_map & (1 << subexp_idx))) + continue; - if (cpos == -1 /* && (boundaries & 1) */) - return -1; + /* Recurse trying to reach the OP_OPEN_SUBEXP and + OP_CLOSE_SUBEXP cases below. But, if the + destination node is the same node as the source + node, don't recurse because it would cause an + infinite loop: a regex that exhibits this behavior + is ()\1*\1* */ + dst = dfa->edests[node].elems[0]; + if (dst == from_node) + { + if (boundaries & 1) + return -1; + else /* if (boundaries & 2) */ + return 0; + } - if (cpos == 0 && (boundaries & 2)) - return 0; + cpos = + check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, + dst, bkref_idx); + if (cpos == -1 /* && (boundaries & 1) */) + return -1; + if (cpos == 0 && (boundaries & 2)) + return 0; - ent->eps_reachable_subexps_map &= ~(1 << (subexp_idx - 1)); - } - while (ent++->more); - break; - } + ent->eps_reachable_subexps_map &= ~(1 << subexp_idx); + } + while (ent++->more); + } + break; case OP_OPEN_SUBEXP: if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx) @@ -2003,7 +2002,7 @@ check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx) if (str_idx <= ent->subexp_from || ent->str_idx < str_idx) continue; /* This is unrelated limitation. */ - subexp_idx = dfa->nodes[ent->node].opr.idx - 1; + subexp_idx = dfa->nodes[ent->node].opr.idx; if (ent->subexp_to == str_idx) { int ops_node = -1; @@ -2060,16 +2059,12 @@ check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx) { if (subexp_idx != dfa->nodes[node].opr.idx) continue; - if ((type == OP_CLOSE_SUBEXP && ent->subexp_to != str_idx) - || (type == OP_OPEN_SUBEXP)) - { - /* It is against this limitation. - Remove it form the current sifted state. */ - err = sub_epsilon_src_nodes (dfa, node, dest_nodes, - candidates); - if (BE (err != REG_NOERROR, 0)) - return err; - } + /* It is against this limitation. + Remove it form the current sifted state. */ + err = sub_epsilon_src_nodes (dfa, node, dest_nodes, + candidates); + if (BE (err != REG_NOERROR, 0)) + return err; } } } @@ -2656,7 +2651,7 @@ get_subexp (mctx, bkref_node, bkref_str_idx) while (entry++->more); } - subexp_num = dfa->nodes[bkref_node].opr.idx - 1; + subexp_num = dfa->nodes[bkref_node].opr.idx; /* For each sub expression */ for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx) |