diff options
Diffstat (limited to 'posix')
| -rw-r--r-- | posix/regcomp.c | 2044 | ||||
| -rw-r--r-- | posix/regex_internal.h | 41 | ||||
| -rw-r--r-- | posix/regexec.c | 2718 |
3 files changed, 2403 insertions, 2400 deletions
diff --git a/posix/regcomp.c b/posix/regcomp.c index 03d5cfce14..c9c0d9eb37 100644 --- a/posix/regcomp.c +++ b/posix/regcomp.c @@ -69,10 +69,10 @@ #include "regex_internal.h" static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern, - int length, reg_syntax_t syntax); + int length, reg_syntax_t syntax); static void re_compile_fastmap_iter (regex_t *bufp, - const re_dfastate_t *init_state, - char *fastmap); + const re_dfastate_t *init_state, + char *fastmap); static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len); static reg_errcode_t init_word_char (re_dfa_t *dfa); #ifdef RE_ENABLE_I18N @@ -86,88 +86,88 @@ static void calc_first (re_dfa_t *dfa, bin_tree_t *node); static void calc_next (re_dfa_t *dfa, bin_tree_t *node); static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node); static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node, - int top_clone_node, int root_node, - unsigned int constraint); + int top_clone_node, int root_node, + unsigned int constraint); static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx, - unsigned int constraint); + unsigned int constraint); static reg_errcode_t calc_eclosure (re_dfa_t *dfa); static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, - int node, int root); + int node, int root); static void calc_inveclosure (re_dfa_t *dfa); static int fetch_number (re_string_t *input, re_token_t *token, - reg_syntax_t syntax); + reg_syntax_t syntax); static re_token_t fetch_token (re_string_t *input, reg_syntax_t syntax); static int peek_token (re_token_t *token, re_string_t *input, - reg_syntax_t syntax); + reg_syntax_t syntax); static int peek_token_bracket (re_token_t *token, re_string_t *input, - reg_syntax_t syntax); + reg_syntax_t syntax); static bin_tree_t *parse (re_string_t *regexp, regex_t *preg, - reg_syntax_t syntax, reg_errcode_t *err); + reg_syntax_t syntax, reg_errcode_t *err); static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg, - re_token_t *token, reg_syntax_t syntax, - int nest, reg_errcode_t *err); + re_token_t *token, reg_syntax_t syntax, + int nest, reg_errcode_t *err); static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg, - re_token_t *token, reg_syntax_t syntax, - int nest, reg_errcode_t *err); + re_token_t *token, reg_syntax_t syntax, + int nest, reg_errcode_t *err); static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg, - re_token_t *token, reg_syntax_t syntax, - int nest, reg_errcode_t *err); + re_token_t *token, reg_syntax_t syntax, + int nest, reg_errcode_t *err); static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg, - re_token_t *token, reg_syntax_t syntax, - int nest, reg_errcode_t *err); + re_token_t *token, reg_syntax_t syntax, + int nest, reg_errcode_t *err); static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp, - re_dfa_t *dfa, re_token_t *token, - reg_syntax_t syntax, reg_errcode_t *err); + re_dfa_t *dfa, re_token_t *token, + reg_syntax_t syntax, reg_errcode_t *err); static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, - re_token_t *token, reg_syntax_t syntax, - reg_errcode_t *err); + re_token_t *token, reg_syntax_t syntax, + reg_errcode_t *err); static reg_errcode_t parse_bracket_element (bracket_elem_t *elem, - re_string_t *regexp, - re_token_t *token, int token_len, - re_dfa_t *dfa, - reg_syntax_t syntax); + re_string_t *regexp, + re_token_t *token, int token_len, + re_dfa_t *dfa, + reg_syntax_t syntax); static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem, - re_string_t *regexp, - re_token_t *token); + re_string_t *regexp, + re_token_t *token); #ifndef _LIBC # ifdef RE_ENABLE_I18N static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset, - re_charset_t *mbcset, int *range_alloc, - bracket_elem_t *start_elem, - bracket_elem_t *end_elem); + re_charset_t *mbcset, int *range_alloc, + bracket_elem_t *start_elem, + bracket_elem_t *end_elem); static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset, - re_charset_t *mbcset, - int *coll_sym_alloc, - const unsigned char *name); + re_charset_t *mbcset, + int *coll_sym_alloc, + const unsigned char *name); # else /* not RE_ENABLE_I18N */ static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset, - bracket_elem_t *start_elem, - bracket_elem_t *end_elem); + bracket_elem_t *start_elem, + bracket_elem_t *end_elem); static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset, - const unsigned char *name); + const unsigned char *name); # endif /* not RE_ENABLE_I18N */ #endif /* not _LIBC */ #ifdef RE_ENABLE_I18N static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset, - re_charset_t *mbcset, - int *equiv_class_alloc, - const unsigned char *name); + re_charset_t *mbcset, + int *equiv_class_alloc, + const unsigned char *name); static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset, - re_charset_t *mbcset, - int *char_class_alloc, - const unsigned char *class_name, - reg_syntax_t syntax); + re_charset_t *mbcset, + int *char_class_alloc, + const unsigned char *class_name, + reg_syntax_t syntax); #else /* not RE_ENABLE_I18N */ static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset, - const unsigned char *name); + const unsigned char *name); static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset, - const unsigned char *class_name, - reg_syntax_t syntax); + const unsigned char *class_name, + reg_syntax_t syntax); #endif /* not RE_ENABLE_I18N */ static bin_tree_t *build_word_op (re_dfa_t *dfa, int not, reg_errcode_t *err); static void free_bin_tree (bin_tree_t *tree); static bin_tree_t *create_tree (bin_tree_t *left, bin_tree_t *right, - re_token_type_t type, int index); + re_token_type_t type, int index); static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa); /* This table gives an error message for each of the error codes listed @@ -363,60 +363,62 @@ re_compile_fastmap_iter (bufp, init_state, fastmap) if (type == CHARACTER) re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c); else if (type == SIMPLE_BRACKET) - { - int i, j, ch; - for (i = 0, ch = 0; i < BITSET_UINTS; ++i) - for (j = 0; j < UINT_BITS; ++j, ++ch) - if (dfa->nodes[node].opr.sbcset[i] & (1 << j)) - re_set_fastmap (fastmap, icase, ch); - } + { + int i, j, ch; + for (i = 0, ch = 0; i < BITSET_UINTS; ++i) + for (j = 0; j < UINT_BITS; ++j, ++ch) + if (dfa->nodes[node].opr.sbcset[i] & (1 << j)) + re_set_fastmap (fastmap, icase, ch); + } #ifdef RE_ENABLE_I18N else if (type == COMPLEX_BRACKET) - { - int i; - re_charset_t *cset = dfa->nodes[node].opr.mbcset; - if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes - || cset->nranges || cset->nchar_classes) - { + { + int i; + re_charset_t *cset = dfa->nodes[node].opr.mbcset; + if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes + || cset->nranges || cset->nchar_classes) + { # ifdef _LIBC - if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0) - { - /* In this case we want to catch the bytes which are - the first byte of any collation elements. - e.g. In da_DK, we want to catch 'a' since "aa" - is a valid collation element, and don't catch - 'b' since 'b' is the only collation element - which starts from 'b'. */ - int j, ch; - const int32_t *table = (const int32_t *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); - for (i = 0, ch = 0; i < BITSET_UINTS; ++i) - for (j = 0; j < UINT_BITS; ++j, ++ch) - if (table[ch] < 0) - re_set_fastmap (fastmap, icase, ch); - } + if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0) + { + /* In this case we want to catch the bytes which are + the first byte of any collation elements. + e.g. In da_DK, we want to catch 'a' since "aa" + is a valid collation element, and don't catch + 'b' since 'b' is the only collation element + which starts from 'b'. */ + int j, ch; + const int32_t *table = (const int32_t *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); + for (i = 0, ch = 0; i < BITSET_UINTS; ++i) + for (j = 0; j < UINT_BITS; ++j, ++ch) + if (table[ch] < 0) + re_set_fastmap (fastmap, icase, ch); + } # else - if (MB_CUR_MAX > 1) - for (i = 0; i < SBC_MAX; ++i) - if (__btowc (i) == WEOF) - re_set_fastmap (fastmap, icase, i); + if (MB_CUR_MAX > 1) + for (i = 0; i < SBC_MAX; ++i) + if (__btowc (i) == WEOF) + re_set_fastmap (fastmap, icase, i); # endif /* not _LIBC */ - } - for (i = 0; i < cset->nmbchars; ++i) - { - char buf[256]; - wctomb (buf, cset->mbchars[i]); - re_set_fastmap (fastmap, icase, *(unsigned char *) buf); - } - } + } + for (i = 0; i < cset->nmbchars; ++i) + { + char buf[256]; + mbstate_t state; + memset (&state, '\0', sizeof (state)); + __wcrtomb (buf, cset->mbchars[i], &state); + re_set_fastmap (fastmap, icase, *(unsigned char *) buf); + } + } #endif /* RE_ENABLE_I18N */ else if (type == END_OF_RE || type == OP_PERIOD) - { - memset (fastmap, '\1', sizeof (char) * SBC_MAX); - if (type == END_OF_RE) - bufp->can_be_null = 1; - return; - } + { + memset (fastmap, '\1', sizeof (char) * SBC_MAX); + if (type == END_OF_RE) + bufp->can_be_null = 1; + return; + } } } @@ -464,7 +466,7 @@ regcomp (preg, pattern, cflags) { reg_errcode_t ret; reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED - : RE_SYNTAX_POSIX_BASIC); + : RE_SYNTAX_POSIX_BASIC); preg->buffer = NULL; preg->allocated = 0; @@ -529,8 +531,8 @@ regerror (errcode, preg, errbuf, errbuf_size) size_t msg_size; if (BE (errcode < 0 - || errcode >= (int) (sizeof (__re_error_msgid_idx) - / sizeof (__re_error_msgid_idx[0])), 0)) + || errcode >= (int) (sizeof (__re_error_msgid_idx) + / sizeof (__re_error_msgid_idx[0])), 0)) /* Only error codes returned by the rest of the code should be passed to this routine. If we are given anything else, or if other regex code generates an invalid error code, then the program has a bug. @@ -544,16 +546,16 @@ regerror (errcode, preg, errbuf, errbuf_size) if (BE (errbuf_size != 0, 1)) { if (BE (msg_size > errbuf_size, 0)) - { + { #if defined HAVE_MEMPCPY || defined _LIBC *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0'; #else - memcpy (errbuf, msg, errbuf_size - 1); - errbuf[errbuf_size - 1] = 0; + memcpy (errbuf, msg, errbuf_size - 1); + errbuf[errbuf_size - 1] = 0; #endif - } + } else - memcpy (errbuf, msg, msg_size); + memcpy (errbuf, msg, msg_size); } return msg_size; @@ -756,7 +758,7 @@ re_compile_internal (preg, pattern, length, syntax) #endif err = re_string_construct (®exp, pattern, length, preg->translate, - syntax & RE_ICASE); + syntax & RE_ICASE); if (BE (err != REG_NOERROR, 0)) { re_free (dfa); @@ -823,7 +825,7 @@ init_dfa (dfa, pat_len) dfa->word_char = NULL; if (BE (dfa->nodes == NULL || dfa->state_table == NULL - || dfa->subexps == NULL, 0)) + || dfa->subexps == NULL, 0)) { /* We don't bother to free anything which was allocated. Very soon the process will go down anyway. */ @@ -850,7 +852,7 @@ init_word_char (dfa) for (i = 0, ch = 0; i < BITSET_UINTS; ++i) for (j = 0; j < UINT_BITS; ++j, ++ch) if (isalnum (ch) || ch == '_') - dfa->word_char[i] |= 1 << j; + dfa->word_char[i] |= 1 << j; return REG_NOERROR; } @@ -890,32 +892,32 @@ create_initial_state (dfa) if (dfa->nbackref > 0) for (i = 0; i < init_nodes.nelem; ++i) { - int node_idx = init_nodes.elems[i]; - re_token_type_t type = dfa->nodes[node_idx].type; - - int clexp_idx; - if (type != OP_BACK_REF) - continue; - for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx) - { - 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) - break; - } - if (clexp_idx == init_nodes.nelem) - continue; - - if (type == OP_BACK_REF) - { - int dest_idx = dfa->edests[node_idx].elems[0]; - if (!re_node_set_contains (&init_nodes, dest_idx)) - { - re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx); - i = 0; - } - } + int node_idx = init_nodes.elems[i]; + re_token_type_t type = dfa->nodes[node_idx].type; + + int clexp_idx; + if (type != OP_BACK_REF) + continue; + for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx) + { + 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) + break; + } + if (clexp_idx == init_nodes.nelem) + continue; + + if (type == OP_BACK_REF) + { + int dest_idx = dfa->edests[node_idx].elems[0]; + if (!re_node_set_contains (&init_nodes, dest_idx)) + { + re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx); + i = 0; + } + } } /* It must be the first time to invoke acquire_state. */ @@ -926,16 +928,16 @@ create_initial_state (dfa) if (dfa->init_state->has_constraint) { dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes, - CONTEXT_WORD); + CONTEXT_WORD); dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes, - CONTEXT_NEWLINE); + CONTEXT_NEWLINE); dfa->init_state_begbuf = re_acquire_state_context (&err, dfa, - &init_nodes, - CONTEXT_NEWLINE - | CONTEXT_BEGBUF); + &init_nodes, + CONTEXT_NEWLINE + | CONTEXT_BEGBUF); if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL - || dfa->init_state_begbuf == NULL, 0)) - return err; + || dfa->init_state_begbuf == NULL, 0)) + return err; } else dfa->init_state_word = dfa->init_state_nl @@ -961,7 +963,7 @@ analyze (dfa) dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc); dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc); if (BE (dfa->nexts == NULL || dfa->edests == NULL - || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0)) + || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0)) return REG_ESPACE; /* Initialize them. */ for (i = 0; i < dfa->nodes_len; ++i) @@ -1003,14 +1005,14 @@ analyze_tree (dfa, node) { ret = analyze_tree (dfa, node->left); if (BE (ret != REG_NOERROR, 0)) - return ret; + return ret; } /* Calculate "first" etc. for the right child. */ if (node->right != NULL) { ret = analyze_tree (dfa, node->right); if (BE (ret != REG_NOERROR, 0)) - return ret; + return ret; } return REG_NOERROR; } @@ -1062,7 +1064,7 @@ calc_first (dfa, node) assert (node->left != NULL); #endif if (node->left->first == -1) - calc_first (dfa, node->left); + calc_first (dfa, node->left); node->first = node->left->first; break; case OP_ALT: @@ -1074,7 +1076,7 @@ calc_first (dfa, node) assert (node->left != NULL); #endif if (node->left->first == -1) - calc_first (dfa, node->left); + calc_first (dfa, node->left); node->first = node->left->first; break; } @@ -1094,7 +1096,7 @@ calc_next (dfa, node) node->next = -1; idx = node->node_idx; if (node->type == 0) - dfa->nexts[idx] = node->next; + dfa->nexts[idx] = node->next; return; } @@ -1109,16 +1111,16 @@ calc_next (dfa, node) break; case CONCAT: if (parent->left == node) - { - if (parent->right->first == -1) - calc_first (dfa, parent->right); - node->next = parent->right->first; - break; - } + { + if (parent->right->first == -1) + calc_first (dfa, parent->right); + node->next = parent->right->first; + break; + } /* else fall through */ default: if (parent->next == -1) - calc_next (dfa, parent); + calc_next (dfa, parent); node->next = parent->next; break; } @@ -1139,50 +1141,50 @@ calc_epsdest (dfa, node) if (node->type == 0) { if (dfa->nodes[idx].type == OP_DUP_ASTERISK - || dfa->nodes[idx].type == OP_DUP_PLUS - || dfa->nodes[idx].type == OP_DUP_QUESTION) - { - if (node->left->first == -1) - calc_first (dfa, node->left); - if (node->next == -1) - calc_next (dfa, node); - re_node_set_init_2 (dfa->edests + idx, node->left->first, - node->next); - } + || dfa->nodes[idx].type == OP_DUP_PLUS + || dfa->nodes[idx].type == OP_DUP_QUESTION) + { + if (node->left->first == -1) + calc_first (dfa, node->left); + if (node->next == -1) + calc_next (dfa, node); + re_node_set_init_2 (dfa->edests + idx, node->left->first, + node->next); + } else if (dfa->nodes[idx].type == OP_ALT) - { - int left, right; - if (node->left != NULL) - { - if (node->left->first == -1) - calc_first (dfa, node->left); - left = node->left->first; - } - else - { - if (node->next == -1) - calc_next (dfa, node); - left = node->next; - } - if (node->right != NULL) - { - if (node->right->first == -1) - calc_first (dfa, node->right); - right = node->right->first; - } - else - { - if (node->next == -1) - calc_next (dfa, node); - right = node->next; - } - re_node_set_init_2 (dfa->edests + idx, left, right); - } + { + int left, right; + if (node->left != NULL) + { + if (node->left->first == -1) + calc_first (dfa, node->left); + left = node->left->first; + } + else + { + if (node->next == -1) + calc_next (dfa, node); + left = node->next; + } + if (node->right != NULL) + { + if (node->right->first == -1) + calc_first (dfa, node->right); + right = node->right->first; + } + else + { + if (node->next == -1) + calc_next (dfa, node); + right = node->next; + } + re_node_set_init_2 (dfa->edests + idx, left, right); + } else if (dfa->nodes[idx].type == ANCHOR - || dfa->nodes[idx].type == OP_OPEN_SUBEXP - || dfa->nodes[idx].type == OP_CLOSE_SUBEXP - || dfa->nodes[idx].type == OP_BACK_REF) - re_node_set_init_1 (dfa->edests + idx, node->next); + || dfa->nodes[idx].type == OP_OPEN_SUBEXP + || dfa->nodes[idx].type == OP_CLOSE_SUBEXP + || dfa->nodes[idx].type == OP_BACK_REF) + re_node_set_init_1 (dfa->edests + idx, node->next); } } @@ -1192,7 +1194,7 @@ calc_epsdest (dfa, node) static reg_errcode_t duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node, - init_constraint) + init_constraint) re_dfa_t *dfa; int top_org_node, top_clone_node, root_node; unsigned int init_constraint; @@ -1204,84 +1206,84 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node, { int org_dest, clone_dest; if (dfa->nodes[org_node].type == OP_BACK_REF) - { + { /* If the back reference epsilon-transit, its destination must also have the constraint. Then duplicate the epsilon closure of the destination of the back reference, and store it in edests of the back reference. */ - org_dest = dfa->nexts[org_node]; - re_node_set_empty (dfa->edests + clone_node); - err = duplicate_node (&clone_dest, dfa, org_dest, constraint); - if (BE (err != REG_NOERROR, 0)) - return err; - dfa->nexts[clone_node] = dfa->nexts[org_node]; - ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - } + org_dest = dfa->nexts[org_node]; + re_node_set_empty (dfa->edests + clone_node); + err = duplicate_node (&clone_dest, dfa, org_dest, constraint); + if (BE (err != REG_NOERROR, 0)) + return err; + dfa->nexts[clone_node] = dfa->nexts[org_node]; + ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + } else if (dfa->edests[org_node].nelem == 0) - { + { /* In case of the node can't epsilon-transit, don't duplicate the destination and store the original destination as the destination of the node. */ - dfa->nexts[clone_node] = dfa->nexts[org_node]; - break; - } + dfa->nexts[clone_node] = dfa->nexts[org_node]; + break; + } else if (dfa->edests[org_node].nelem == 1) - { + { /* In case of the node can epsilon-transit, and it has only one destination. */ - org_dest = dfa->edests[org_node].elems[0]; - re_node_set_empty (dfa->edests + clone_node); - if (dfa->nodes[org_node].type == ANCHOR) - { + org_dest = dfa->edests[org_node].elems[0]; + re_node_set_empty (dfa->edests + clone_node); + if (dfa->nodes[org_node].type == ANCHOR) + { /* In case of the node has another constraint, append it. */ - if (org_node == root_node && clone_node != org_node) - { + if (org_node == root_node && clone_node != org_node) + { /* ...but if the node is root_node itself, it means the epsilon closure have a loop, then tie it to the destination of the root_node. */ - ret = re_node_set_insert (dfa->edests + clone_node, - org_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - break; - } - constraint |= dfa->nodes[org_node].opr.ctx_type; - } - err = duplicate_node (&clone_dest, dfa, org_dest, constraint); - if (BE (err != REG_NOERROR, 0)) - return err; - ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - } + ret = re_node_set_insert (dfa->edests + clone_node, + org_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + break; + } + constraint |= dfa->nodes[org_node].opr.ctx_type; + } + err = duplicate_node (&clone_dest, dfa, org_dest, constraint); + if (BE (err != REG_NOERROR, 0)) + return err; + ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + } else /* dfa->edests[org_node].nelem == 2 */ - { + { /* In case of the node can epsilon-transit, and it has two destinations. */ - org_dest = dfa->edests[org_node].elems[0]; - re_node_set_empty (dfa->edests + clone_node); - err = duplicate_node (&clone_dest, dfa, org_dest, constraint); - if (BE (err != REG_NOERROR, 0)) - return err; - ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - - err = duplicate_node_closure (dfa, org_dest, clone_dest, root_node, - constraint); - if (BE (err != REG_NOERROR, 0)) - return err; - - org_dest = dfa->edests[org_node].elems[1]; - err = duplicate_node (&clone_dest, dfa, org_dest, constraint); - if (BE (err != REG_NOERROR, 0)) - return err; - ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - } + org_dest = dfa->edests[org_node].elems[0]; + re_node_set_empty (dfa->edests + clone_node); + err = duplicate_node (&clone_dest, dfa, org_dest, constraint); + if (BE (err != REG_NOERROR, 0)) + return err; + ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + + err = duplicate_node_closure (dfa, org_dest, clone_dest, root_node, + constraint); + if (BE (err != REG_NOERROR, 0)) + return err; + + org_dest = dfa->edests[org_node].elems[1]; + err = duplicate_node (&clone_dest, dfa, org_dest, constraint); + if (BE (err != REG_NOERROR, 0)) + return err; + ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + } org_node = org_dest; clone_node = clone_dest; } @@ -1325,10 +1327,10 @@ calc_inveclosure (dfa) for (src = 0; src < dfa->nodes_len; ++src) { for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx) - { - dest = dfa->eclosures[src].elems[idx]; - re_node_set_insert (dfa->inveclosures + dest, src); - } + { + dest = dfa->eclosures[src].elems[idx]; + re_node_set_insert (dfa->inveclosures + dest, src); + } } } @@ -1349,29 +1351,29 @@ calc_eclosure (dfa) reg_errcode_t err; re_node_set eclosure_elem; if (node_idx == dfa->nodes_len) - { - if (!incomplete) - break; - incomplete = 0; - node_idx = 0; - } + { + if (!incomplete) + break; + incomplete = 0; + node_idx = 0; + } #ifdef DEBUG assert (dfa->eclosures[node_idx].nelem != -1); #endif /* If we have already calculated, skip it. */ if (dfa->eclosures[node_idx].nelem != 0) - continue; + continue; /* Calculate epsilon closure of `node_idx'. */ err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1); if (BE (err != REG_NOERROR, 0)) - return err; + return err; if (dfa->eclosures[node_idx].nelem == 0) - { - incomplete = 1; - re_node_set_free (&eclosure_elem); - } + { + incomplete = 1; + re_node_set_free (&eclosure_elem); + } } return REG_NOERROR; } @@ -1398,7 +1400,7 @@ calc_eclosure_iter (new_set, dfa, node, root) dfa->eclosures[node].nelem = -1; constraint = ((dfa->nodes[node].type == ANCHOR) - ? dfa->nodes[node].opr.ctx_type : 0); + ? dfa->nodes[node].opr.ctx_type : 0); /* If the current node has constraints, duplicate all nodes. Since they must inherit the constraints. */ if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated) @@ -1407,41 +1409,41 @@ calc_eclosure_iter (new_set, dfa, node, root) org_node = cur_node = node; err = duplicate_node_closure (dfa, node, node, node, constraint); if (BE (err != REG_NOERROR, 0)) - return err; + return err; } /* Expand each epsilon destination nodes. */ if (IS_EPSILON_NODE(dfa->nodes[node].type)) for (i = 0; i < dfa->edests[node].nelem; ++i) { - re_node_set eclosure_elem; - int edest = dfa->edests[node].elems[i]; - /* If calculating the epsilon closure of `edest' is in progress, - return intermediate result. */ - if (dfa->eclosures[edest].nelem == -1) - { - incomplete = 1; - continue; - } - /* If we haven't calculated the epsilon closure of `edest' yet, - calculate now. Otherwise use calculated epsilon closure. */ - if (dfa->eclosures[edest].nelem == 0) - { - err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0); - if (BE (err != REG_NOERROR, 0)) - return err; - } - else - eclosure_elem = dfa->eclosures[edest]; - /* Merge the epsilon closure of `edest'. */ - re_node_set_merge (&eclosure, &eclosure_elem); - /* If the epsilon closure of `edest' is incomplete, - the epsilon closure of this node is also incomplete. */ - if (dfa->eclosures[edest].nelem == 0) - { - incomplete = 1; - re_node_set_free (&eclosure_elem); - } + re_node_set eclosure_elem; + int edest = dfa->edests[node].elems[i]; + /* If calculating the epsilon closure of `edest' is in progress, + return intermediate result. */ + if (dfa->eclosures[edest].nelem == -1) + { + incomplete = 1; + continue; + } + /* If we haven't calculated the epsilon closure of `edest' yet, + calculate now. Otherwise use calculated epsilon closure. */ + if (dfa->eclosures[edest].nelem == 0) + { + err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0); + if (BE (err != REG_NOERROR, 0)) + return err; + } + else + eclosure_elem = dfa->eclosures[edest]; + /* Merge the epsilon closure of `edest'. */ + re_node_set_merge (&eclosure, &eclosure_elem); + /* If the epsilon closure of `edest' is incomplete, + the epsilon closure of this node is also incomplete. */ + if (dfa->eclosures[edest].nelem == 0) + { + incomplete = 1; + re_node_set_free (&eclosure_elem); + } } /* Epsilon closures include itself. */ @@ -1505,105 +1507,105 @@ peek_token (token, input, syntax) { unsigned char c2; if (re_string_cur_idx (input) + 1 >= re_string_length (input)) - { - token->type = BACK_SLASH; - return 1; - } + { + token->type = BACK_SLASH; + return 1; + } c2 = re_string_peek_byte_case (input, 1); token->opr.c = c2; token->type = CHARACTER; switch (c2) - { - case '|': - if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR)) - token->type = OP_ALT; - break; - case '1': case '2': case '3': case '4': case '5': - case '6': case '7': case '8': case '9': - if (!(syntax & RE_NO_BK_REFS)) - { - token->type = OP_BACK_REF; - token->opr.idx = c2 - '0'; - } - break; - case '<': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = WORD_FIRST; - } - break; - case '>': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = WORD_LAST; - } - break; - case 'b': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = WORD_DELIM; - } - break; - case 'B': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = INSIDE_WORD; - } - break; - case 'w': - if (!(syntax & RE_NO_GNU_OPS)) - token->type = OP_WORD; - break; - case 'W': - if (!(syntax & RE_NO_GNU_OPS)) - token->type = OP_NOTWORD; - break; - case '`': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = BUF_FIRST; - } - break; - case '\'': - if (!(syntax & RE_NO_GNU_OPS)) - { - token->type = ANCHOR; - token->opr.idx = BUF_LAST; - } - break; - case '(': - if (!(syntax & RE_NO_BK_PARENS)) - token->type = OP_OPEN_SUBEXP; - break; - case ')': - if (!(syntax & RE_NO_BK_PARENS)) - token->type = OP_CLOSE_SUBEXP; - break; - case '+': - if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM)) - token->type = OP_DUP_PLUS; - break; - case '?': - if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM)) - token->type = OP_DUP_QUESTION; - break; - case '{': - if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES))) - token->type = OP_OPEN_DUP_NUM; - break; - case '}': - if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES))) - token->type = OP_CLOSE_DUP_NUM; - break; - default: - break; - } + { + case '|': + if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR)) + token->type = OP_ALT; + break; + case '1': case '2': case '3': case '4': case '5': + case '6': case '7': case '8': case '9': + if (!(syntax & RE_NO_BK_REFS)) + { + token->type = OP_BACK_REF; + token->opr.idx = c2 - '0'; + } + break; + case '<': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = WORD_FIRST; + } + break; + case '>': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = WORD_LAST; + } + break; + case 'b': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = WORD_DELIM; + } + break; + case 'B': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = INSIDE_WORD; + } + break; + case 'w': + if (!(syntax & RE_NO_GNU_OPS)) + token->type = OP_WORD; + break; + case 'W': + if (!(syntax & RE_NO_GNU_OPS)) + token->type = OP_NOTWORD; + break; + case '`': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = BUF_FIRST; + } + break; + case '\'': + if (!(syntax & RE_NO_GNU_OPS)) + { + token->type = ANCHOR; + token->opr.idx = BUF_LAST; + } + break; + case '(': + if (!(syntax & RE_NO_BK_PARENS)) + token->type = OP_OPEN_SUBEXP; + break; + case ')': + if (!(syntax & RE_NO_BK_PARENS)) + token->type = OP_CLOSE_SUBEXP; + break; + case '+': + if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM)) + token->type = OP_DUP_PLUS; + break; + case '?': + if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM)) + token->type = OP_DUP_QUESTION; + break; + case '{': + if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES))) + token->type = OP_OPEN_DUP_NUM; + break; + case '}': + if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES))) + token->type = OP_CLOSE_DUP_NUM; + break; + default: + break; + } return 2; } @@ -1612,38 +1614,38 @@ peek_token (token, input, syntax) { case '\n': if (syntax & RE_NEWLINE_ALT) - token->type = OP_ALT; + token->type = OP_ALT; break; case '|': if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR)) - token->type = OP_ALT; + token->type = OP_ALT; break; case '*': token->type = OP_DUP_ASTERISK; break; case '+': if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM)) - token->type = OP_DUP_PLUS; + token->type = OP_DUP_PLUS; break; case '?': if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM)) - token->type = OP_DUP_QUESTION; + token->type = OP_DUP_QUESTION; break; case '{': if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES)) - token->type = OP_OPEN_DUP_NUM; + token->type = OP_OPEN_DUP_NUM; break; case '}': if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES)) - token->type = OP_CLOSE_DUP_NUM; + token->type = OP_CLOSE_DUP_NUM; break; case '(': if (syntax & RE_NO_BK_PARENS) - token->type = OP_OPEN_SUBEXP; + token->type = OP_OPEN_SUBEXP; break; case ')': if (syntax & RE_NO_BK_PARENS) - token->type = OP_CLOSE_SUBEXP; + token->type = OP_CLOSE_SUBEXP; break; case '[': token->type = OP_OPEN_BRACKET; @@ -1653,27 +1655,27 @@ peek_token (token, input, syntax) break; case '^': if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) && - re_string_cur_idx (input) != 0) - { - char prev = re_string_peek_byte (input, -1); - if (prev != '|' && prev != '(' && - (!(syntax & RE_NEWLINE_ALT) || prev != '\n')) - break; - } + re_string_cur_idx (input) != 0) + { + char prev = re_string_peek_byte (input, -1); + if (prev != '|' && prev != '(' && + (!(syntax & RE_NEWLINE_ALT) || prev != '\n')) + break; + } token->type = ANCHOR; token->opr.idx = LINE_FIRST; break; case '$': if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) && - re_string_cur_idx (input) + 1 != re_string_length (input)) - { - re_token_t next; - re_string_skip_bytes (input, 1); - peek_token (&next, input, syntax); - re_string_skip_bytes (input, -1); - if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP) - break; - } + re_string_cur_idx (input) + 1 != re_string_length (input)) + { + re_token_t next; + re_string_skip_bytes (input, 1); + peek_token (&next, input, syntax); + re_string_skip_bytes (input, -1); + if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP) + break; + } token->type = ANCHOR; token->opr.idx = LINE_LAST; break; @@ -1728,26 +1730,26 @@ peek_token_bracket (token, input, syntax) token->opr.c = c2; token_len = 2; switch (c2) - { - case '.': - token->type = OP_OPEN_COLL_ELEM; - break; - case '=': - token->type = OP_OPEN_EQUIV_CLASS; - break; - case ':': - if (syntax & RE_CHAR_CLASSES) - { - token->type = OP_OPEN_CHAR_CLASS; - break; - } - /* else fall through. */ - default: - token->type = CHARACTER; - token->opr.c = c; - token_len = 1; - break; - } + { + case '.': + token->type = OP_OPEN_COLL_ELEM; + break; + case '=': + token->type = OP_OPEN_EQUIV_CLASS; + break; + case ':': + if (syntax & RE_CHAR_CLASSES) + { + token->type = OP_OPEN_CHAR_CLASS; + break; + } + /* else fall through. */ + default: + token->type = CHARACTER; + token->opr.c = c; + token_len = 1; + break; + } return token_len; } switch (c) @@ -1773,9 +1775,9 @@ peek_token_bracket (token, input, syntax) Parse the regular expression REGEXP and return the structure tree. If an error is occured, ERR is set by error code, and return NULL. This function build the following tree, from regular expression <reg_exp>: - CAT - / \ - / \ + CAT + / \ + / \ <reg_exp> EOR CAT means concatenation. @@ -1812,9 +1814,9 @@ parse (regexp, preg, syntax, err) /* This function build the following tree, from regular expression <branch1>|<branch2>: - ALT - / \ - / \ + ALT + / \ + / \ <branch1> <branch2> ALT means alternative, which represents the operator `|'. */ @@ -1841,23 +1843,23 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err) new_idx = re_dfa_add_node (dfa, alt_token, 0); *token = fetch_token (regexp, syntax); if (token->type != OP_ALT && token->type != END_OF_RE - && (nest == 0 || token->type != OP_CLOSE_SUBEXP)) - { - branch = parse_branch (regexp, preg, token, syntax, nest, err); - if (BE (*err != REG_NOERROR && branch == NULL, 0)) - { - free_bin_tree (tree); - return NULL; - } - } + && (nest == 0 || token->type != OP_CLOSE_SUBEXP)) + { + branch = parse_branch (regexp, preg, token, syntax, nest, err); + if (BE (*err != REG_NOERROR && branch == NULL, 0)) + { + free_bin_tree (tree); + return NULL; + } + } else branch = NULL; tree = create_tree (tree, branch, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } dfa->has_plural_match = 1; } return tree; @@ -1865,8 +1867,8 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err) /* This function build the following tree, from regular expression <exp1><exp2>: - CAT - / \ + CAT + / \ / \ <exp1> <exp2> @@ -1887,34 +1889,34 @@ parse_branch (regexp, preg, token, syntax, nest, err) return NULL; while (token->type != OP_ALT && token->type != END_OF_RE - && (nest == 0 || token->type != OP_CLOSE_SUBEXP)) + && (nest == 0 || token->type != OP_CLOSE_SUBEXP)) { exp = parse_expression (regexp, preg, token, syntax, nest, err); if (BE (*err != REG_NOERROR && exp == NULL, 0)) - { - free_bin_tree (tree); - return NULL; - } + { + free_bin_tree (tree); + return NULL; + } if (tree != NULL && exp != NULL) - { - tree = create_tree (tree, exp, CONCAT, 0); - if (tree == NULL) - { - *err = REG_ESPACE; - return NULL; - } - } + { + tree = create_tree (tree, exp, CONCAT, 0); + if (tree == NULL) + { + *err = REG_ESPACE; + return NULL; + } + } else if (tree == NULL) - tree = exp; + tree = exp; /* Otherwise exp == NULL, we don't need to create new tree. */ } return tree; } /* This function build the following tree, from regular expression a*: - * - | - a + * + | + a */ static bin_tree_t * @@ -1935,51 +1937,51 @@ parse_expression (regexp, preg, token, syntax, nest, err) new_idx = re_dfa_add_node (dfa, *token, 0); tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } #ifdef RE_ENABLE_I18N if (MB_CUR_MAX > 1) { while (!re_string_eoi (regexp) && !re_string_first_byte (regexp, re_string_cur_idx (regexp))) { - bin_tree_t *mbc_remain; - *token = fetch_token (regexp, syntax); - new_idx = re_dfa_add_node (dfa, *token, 0); - mbc_remain = create_tree (NULL, NULL, 0, new_idx); - tree = create_tree (tree, mbc_remain, CONCAT, 0); - if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0)) - return *err = REG_ESPACE, NULL; - } + bin_tree_t *mbc_remain; + *token = fetch_token (regexp, syntax); + new_idx = re_dfa_add_node (dfa, *token, 0); + mbc_remain = create_tree (NULL, NULL, 0, new_idx); + tree = create_tree (tree, mbc_remain, CONCAT, 0); + if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0)) + return *err = REG_ESPACE, NULL; + } } #endif break; case OP_OPEN_SUBEXP: tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; break; case OP_OPEN_BRACKET: tree = parse_bracket_exp (regexp, dfa, token, syntax, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; break; case OP_BACK_REF: if (BE (preg->re_nsub < token->opr.idx - || dfa->subexps[token->opr.idx - 1].end == -1, 0)) - { - *err = REG_ESUBREG; - return NULL; - } + || dfa->subexps[token->opr.idx - 1].end == -1, 0)) + { + *err = REG_ESUBREG; + return NULL; + } new_idx = re_dfa_add_node (dfa, *token, 0); tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } ++dfa->nbackref; dfa->has_mb_node = 1; break; @@ -1988,23 +1990,23 @@ parse_expression (regexp, preg, token, syntax, nest, err) case OP_DUP_QUESTION: case OP_OPEN_DUP_NUM: if (syntax & RE_CONTEXT_INVALID_OPS) - { - *err = REG_BADRPT; - return NULL; - } + { + *err = REG_BADRPT; + return NULL; + } else if (syntax & RE_CONTEXT_INDEP_OPS) - { - *token = fetch_token (regexp, syntax); - return parse_expression (regexp, preg, token, syntax, nest, err); - } + { + *token = fetch_token (regexp, syntax); + return parse_expression (regexp, preg, token, syntax, nest, err); + } /* else fall through */ case OP_CLOSE_SUBEXP: if ((token->type == OP_CLOSE_SUBEXP) && - !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)) - { - *err = REG_ERPAREN; - return NULL; - } + !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)) + { + *err = REG_ERPAREN; + return NULL; + } /* else fall through */ case OP_CLOSE_DUP_NUM: /* We treat it as a normal character. */ @@ -2014,72 +2016,72 @@ parse_expression (regexp, preg, token, syntax, nest, err) new_idx = re_dfa_add_node (dfa, *token, 0); tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } break; case ANCHOR: if (dfa->word_char == NULL) - { - *err = init_word_char (dfa); - if (BE (*err != REG_NOERROR, 0)) - return NULL; - } + { + *err = init_word_char (dfa); + if (BE (*err != REG_NOERROR, 0)) + return NULL; + } if (token->opr.ctx_type == WORD_DELIM) - { - bin_tree_t *tree_first, *tree_last; - int idx_first, idx_last; - token->opr.ctx_type = WORD_FIRST; - idx_first = re_dfa_add_node (dfa, *token, 0); - tree_first = create_tree (NULL, NULL, 0, idx_first); - token->opr.ctx_type = WORD_LAST; - idx_last = re_dfa_add_node (dfa, *token, 0); - tree_last = create_tree (NULL, NULL, 0, idx_last); - token->type = OP_ALT; - new_idx = re_dfa_add_node (dfa, *token, 0); - tree = create_tree (tree_first, tree_last, 0, new_idx); - if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1 - || tree_first == NULL || tree_last == NULL - || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } - } + { + bin_tree_t *tree_first, *tree_last; + int idx_first, idx_last; + token->opr.ctx_type = WORD_FIRST; + idx_first = re_dfa_add_node (dfa, *token, 0); + tree_first = create_tree (NULL, NULL, 0, idx_first); + token->opr.ctx_type = WORD_LAST; + idx_last = re_dfa_add_node (dfa, *token, 0); + tree_last = create_tree (NULL, NULL, 0, idx_last); + token->type = OP_ALT; + new_idx = re_dfa_add_node (dfa, *token, 0); + tree = create_tree (tree_first, tree_last, 0, new_idx); + if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1 + || tree_first == NULL || tree_last == NULL + || tree == NULL, 0)) + { + *err = REG_ESPACE; + return NULL; + } + } else - { - new_idx = re_dfa_add_node (dfa, *token, 0); - tree = create_tree (NULL, NULL, 0, new_idx); - if (BE (new_idx == -1 || tree == NULL, 0)) - return *err = REG_ESPACE, NULL; - } + { + new_idx = re_dfa_add_node (dfa, *token, 0); + tree = create_tree (NULL, NULL, 0, new_idx); + if (BE (new_idx == -1 || tree == NULL, 0)) + return *err = REG_ESPACE, NULL; + } /* We must return here, since ANCHORs can't be followed - by repetition operators. - eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>", - it must not be "<ANCHOR(^)><REPEAT(*)>". */ + by repetition operators. + eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>", + it must not be "<ANCHOR(^)><REPEAT(*)>". */ *token = fetch_token (regexp, syntax); return tree; case OP_PERIOD: new_idx = re_dfa_add_node (dfa, *token, 0); tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } if (MB_CUR_MAX > 1) - dfa->has_mb_node = 1; + dfa->has_mb_node = 1; break; case OP_WORD: tree = build_word_op (dfa, 0, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; break; case OP_NOTWORD: tree = build_word_op (dfa, 1, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; break; case OP_ALT: case END_OF_RE: @@ -2097,11 +2099,11 @@ parse_expression (regexp, preg, token, syntax, nest, err) *token = fetch_token (regexp, syntax); while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS - || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM) + || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM) { tree = parse_dup_op (tree, regexp, dfa, token, syntax, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; dfa->has_plural_match = 1; } @@ -2110,9 +2112,9 @@ parse_expression (regexp, preg, token, syntax, nest, err) /* This function build the following tree, from regular expression (<reg_exp>): - SUBEXP - | - <reg_exp> + SUBEXP + | + <reg_exp> */ static bin_tree_t * @@ -2162,7 +2164,7 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) { tree = parse_reg_exp (regexp, preg, token, syntax, nest, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) - return NULL; + return NULL; } if (BE (token->type != OP_CLOSE_SUBEXP, 0)) { @@ -2174,7 +2176,7 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) dfa->subexps[cur_nsub].end = dfa->nodes_len; right_par = create_tree (NULL, NULL, 0, new_idx); tree = ((tree == NULL) ? right_par - : create_tree (tree, right_par, CONCAT, 0)); + : create_tree (tree, right_par, CONCAT, 0)); tree = create_tree (left_par, tree, CONCAT, 0); if (BE (new_idx == -1 || right_par == NULL || tree == NULL, 0)) { @@ -2208,112 +2210,112 @@ parse_dup_op (dup_elem, regexp, dfa, token, syntax, err) int start = fetch_number (regexp, token, syntax); bin_tree_t *elem; if (start == -1) - { - if (token->type == CHARACTER && token->opr.c == ',') - start = 0; /* We treat "{,m}" as "{0,m}". */ - else - { - *err = REG_BADBR; /* <re>{} is invalid. */ - return NULL; - } - } + { + if (token->type == CHARACTER && token->opr.c == ',') + start = 0; /* We treat "{,m}" as "{0,m}". */ + else + { + *err = REG_BADBR; /* <re>{} is invalid. */ + return NULL; + } + } if (BE (start != -2, 1)) - { - /* We treat "{n}" as "{n,n}". */ - end = ((token->type == OP_CLOSE_DUP_NUM) ? start - : ((token->type == CHARACTER && token->opr.c == ',') - ? fetch_number (regexp, token, syntax) : -2)); - } + { + /* We treat "{n}" as "{n,n}". */ + end = ((token->type == OP_CLOSE_DUP_NUM) ? start + : ((token->type == CHARACTER && token->opr.c == ',') + ? fetch_number (regexp, token, syntax) : -2)); + } if (BE (start == -2 || end == -2, 0)) - { - /* Invalid sequence. */ - if (token->type == OP_CLOSE_DUP_NUM) - goto parse_dup_op_invalid_interval; - else - goto parse_dup_op_ebrace; - } + { + /* Invalid sequence. */ + if (token->type == OP_CLOSE_DUP_NUM) + goto parse_dup_op_invalid_interval; + else + goto parse_dup_op_ebrace; + } if (BE (start == 0 && end == 0, 0)) - { - /* We treat "<re>{0}" and "<re>{0,0}" as null string. */ - *token = fetch_token (regexp, syntax); - free_bin_tree (dup_elem); - return NULL; - } + { + /* We treat "<re>{0}" and "<re>{0,0}" as null string. */ + *token = fetch_token (regexp, syntax); + free_bin_tree (dup_elem); + return NULL; + } /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */ elem = tree; for (i = 0; i < start; ++i) - if (i != 0) - { - work_tree = duplicate_tree (elem, dfa); - tree = create_tree (tree, work_tree, CONCAT, 0); - if (BE (work_tree == NULL || tree == NULL, 0)) - goto parse_dup_op_espace; - } + if (i != 0) + { + work_tree = duplicate_tree (elem, dfa); + tree = create_tree (tree, work_tree, CONCAT, 0); + if (BE (work_tree == NULL || tree == NULL, 0)) + goto parse_dup_op_espace; + } if (end == -1) - { - /* We treat "<re>{0,}" as "<re>*". */ - dup_token.type = OP_DUP_ASTERISK; - if (start > 0) - { - elem = duplicate_tree (elem, dfa); - new_idx = re_dfa_add_node (dfa, dup_token, 0); - work_tree = create_tree (elem, NULL, 0, new_idx); - tree = create_tree (tree, work_tree, CONCAT, 0); - if (BE (elem == NULL || new_idx == -1 || work_tree == NULL - || tree == NULL, 0)) - goto parse_dup_op_espace; - } - else - { - new_idx = re_dfa_add_node (dfa, dup_token, 0); - tree = create_tree (elem, NULL, 0, new_idx); - if (BE (new_idx == -1 || tree == NULL, 0)) - goto parse_dup_op_espace; - } - } + { + /* We treat "<re>{0,}" as "<re>*". */ + dup_token.type = OP_DUP_ASTERISK; + if (start > 0) + { + elem = duplicate_tree (elem, dfa); + new_idx = re_dfa_add_node (dfa, dup_token, 0); + work_tree = create_tree (elem, NULL, 0, new_idx); + tree = create_tree (tree, work_tree, CONCAT, 0); + if (BE (elem == NULL || new_idx == -1 || work_tree == NULL + || tree == NULL, 0)) + goto parse_dup_op_espace; + } + else + { + new_idx = re_dfa_add_node (dfa, dup_token, 0); + tree = create_tree (elem, NULL, 0, new_idx); + if (BE (new_idx == -1 || tree == NULL, 0)) + goto parse_dup_op_espace; + } + } else if (end - start > 0) - { - /* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?". */ - dup_token.type = OP_DUP_QUESTION; - if (start > 0) - { - elem = duplicate_tree (elem, dfa); - new_idx = re_dfa_add_node (dfa, dup_token, 0); - elem = create_tree (elem, NULL, 0, new_idx); - tree = create_tree (tree, elem, CONCAT, 0); - if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0)) - goto parse_dup_op_espace; - } - else - { - new_idx = re_dfa_add_node (dfa, dup_token, 0); - tree = elem = create_tree (elem, NULL, 0, new_idx); - if (BE (new_idx == -1 || tree == NULL, 0)) - goto parse_dup_op_espace; - } - for (i = 1; i < end - start; ++i) - { - work_tree = duplicate_tree (elem, dfa); - tree = create_tree (tree, work_tree, CONCAT, 0); - if (BE (work_tree == NULL || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } - } - } + { + /* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?". */ + dup_token.type = OP_DUP_QUESTION; + if (start > 0) + { + elem = duplicate_tree (elem, dfa); + new_idx = re_dfa_add_node (dfa, dup_token, 0); + elem = create_tree (elem, NULL, 0, new_idx); + tree = create_tree (tree, elem, CONCAT, 0); + if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0)) + goto parse_dup_op_espace; + } + else + { + new_idx = re_dfa_add_node (dfa, dup_token, 0); + tree = elem = create_tree (elem, NULL, 0, new_idx); + if (BE (new_idx == -1 || tree == NULL, 0)) + goto parse_dup_op_espace; + } + for (i = 1; i < end - start; ++i) + { + work_tree = duplicate_tree (elem, dfa); + tree = create_tree (tree, work_tree, CONCAT, 0); + if (BE (work_tree == NULL || tree == NULL, 0)) + { + *err = REG_ESPACE; + return NULL; + } + } + } } else { new_idx = re_dfa_add_node (dfa, *token, 0); tree = create_tree (tree, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) - { - *err = REG_ESPACE; - return NULL; - } + { + *err = REG_ESPACE; + return NULL; + } } *token = fetch_token (regexp, syntax); return tree; @@ -2369,16 +2371,16 @@ build_range_exp (sbcset, start_elem, end_elem) unsigned int start_ch, end_ch; /* Equivalence Classes and Character Classes can't be a range start/end. */ if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS - || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS, - 0)) + || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS, + 0)) return REG_ERANGE; /* We can handle no multi character collating elements without libc support. */ if (BE ((start_elem->type == COLL_SYM - && strlen ((char *) start_elem->opr.name) > 1) - || (end_elem->type == COLL_SYM - && strlen ((char *) end_elem->opr.name) > 1), 0)) + && strlen ((char *) start_elem->opr.name) > 1) + || (end_elem->type == COLL_SYM + && strlen ((char *) end_elem->opr.name) > 1), 0)) return REG_ECOLLATE; # ifdef RE_ENABLE_I18N @@ -2387,15 +2389,15 @@ build_range_exp (sbcset, start_elem, end_elem) wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'}; start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch - : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] - : 0)); + : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] + : 0)); end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch - : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] - : 0)); + : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] + : 0)); start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM) - ? __btowc (start_ch) : start_elem->opr.wch); + ? __btowc (start_ch) : start_elem->opr.wch); end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM) - ? __btowc (end_ch) : end_elem->opr.wch); + ? __btowc (end_ch) : end_elem->opr.wch); cmp_buf[0] = start_wc; cmp_buf[4] = end_wc; if (wcscoll (cmp_buf, cmp_buf + 4) > 0) @@ -2404,25 +2406,25 @@ build_range_exp (sbcset, start_elem, end_elem) /* Check the space of the arrays. */ if (*range_alloc == mbcset->nranges) { - /* There are not enough space, need realloc. */ - wchar_t *new_array_start, *new_array_end; - int new_nranges; - - /* +1 in case of mbcset->nranges is 0. */ - new_nranges = 2 * mbcset->nranges + 1; - /* Use realloc since mbcset->range_starts and mbcset->range_ends - are NULL if *range_alloc == 0. */ - new_array_start = re_realloc (mbcset->range_starts, wchar_t, - new_nranges); - new_array_end = re_realloc (mbcset->range_ends, wchar_t, - new_nranges); - - if (BE (new_array_start == NULL || new_array_end == NULL, 0)) - return REG_ESPACE; - - mbcset->range_starts = new_array_start; - mbcset->range_ends = new_array_end; - *range_alloc = new_nranges; + /* There are not enough space, need realloc. */ + wchar_t *new_array_start, *new_array_end; + int new_nranges; + + /* +1 in case of mbcset->nranges is 0. */ + new_nranges = 2 * mbcset->nranges + 1; + /* Use realloc since mbcset->range_starts and mbcset->range_ends + are NULL if *range_alloc == 0. */ + new_array_start = re_realloc (mbcset->range_starts, wchar_t, + new_nranges); + new_array_end = re_realloc (mbcset->range_ends, wchar_t, + new_nranges); + + if (BE (new_array_start == NULL || new_array_end == NULL, 0)) + return REG_ESPACE; + + mbcset->range_starts = new_array_start; + mbcset->range_ends = new_array_end; + *range_alloc = new_nranges; } mbcset->range_starts[mbcset->nranges] = start_wc; @@ -2431,27 +2433,27 @@ build_range_exp (sbcset, start_elem, end_elem) /* Build the table for single byte characters. */ for (wc = 0; wc <= SBC_MAX; ++wc) { - cmp_buf[2] = wc; - if (wcscoll (cmp_buf, cmp_buf + 2) <= 0 - && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0) - bitset_set (sbcset, wc); + cmp_buf[2] = wc; + if (wcscoll (cmp_buf, cmp_buf + 2) <= 0 + && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0) + bitset_set (sbcset, wc); } } # else /* not RE_ENABLE_I18N */ { unsigned int ch; start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch - : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] - : 0)); + : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] + : 0)); end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch - : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] - : 0)); + : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] + : 0)); if (start_ch > end_ch) return REG_ERANGE; /* Build the table for single byte characters. */ for (ch = 0; ch <= SBC_MAX; ++ch) if (start_ch <= ch && ch <= end_ch) - bitset_set (sbcset, ch); + bitset_set (sbcset, ch); } # endif /* not RE_ENABLE_I18N */ return REG_NOERROR; @@ -2512,29 +2514,29 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) static inline int32_t seek_collating_symbol_entry (name, name_len) - const unsigned char *name; - size_t name_len; + const unsigned char *name; + size_t name_len; { int32_t hash = elem_hash ((const char *) name, name_len); int32_t elem = hash % table_size; int32_t second = hash % (table_size - 2); while (symb_table[2 * elem] != 0) - { - /* First compare the hashing value. */ - if (symb_table[2 * elem] == hash - /* Compare the length of the name. */ - && name_len == extra[symb_table[2 * elem + 1]] - /* Compare the name. */ - && memcmp (name, &extra[symb_table[2 * elem + 1] + 1], - name_len) == 0) - { - /* Yep, this is the entry. */ - break; - } - - /* Next entry. */ - elem += second; - } + { + /* First compare the hashing value. */ + if (symb_table[2 * elem] == hash + /* Compare the length of the name. */ + && name_len == extra[symb_table[2 * elem + 1]] + /* Compare the name. */ + && memcmp (name, &extra[symb_table[2 * elem + 1] + 1], + name_len) == 0) + { + /* Yep, this is the entry. */ + break; + } + + /* Next entry. */ + elem += second; + } return elem; } @@ -2544,61 +2546,61 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) static inline unsigned int lookup_collation_sequence_value (br_elem) - bracket_elem_t *br_elem; + bracket_elem_t *br_elem; { if (br_elem->type == SB_CHAR) - { - /* - if (MB_CUR_MAX == 1) - */ - if (nrules == 0) - return collseqmb[br_elem->opr.ch]; - else - { - wint_t wc = __btowc (br_elem->opr.ch); - return collseq_table_lookup (collseqwc, wc); - } - } + { + /* + if (MB_CUR_MAX == 1) + */ + if (nrules == 0) + return collseqmb[br_elem->opr.ch]; + else + { + wint_t wc = __btowc (br_elem->opr.ch); + return collseq_table_lookup (collseqwc, wc); + } + } else if (br_elem->type == MB_CHAR) - { - return collseq_table_lookup (collseqwc, br_elem->opr.wch); - } + { + return collseq_table_lookup (collseqwc, br_elem->opr.wch); + } else if (br_elem->type == COLL_SYM) - { - size_t sym_name_len = strlen ((char *) br_elem->opr.name); - if (nrules != 0) - { - int32_t elem, idx; - elem = seek_collating_symbol_entry (br_elem->opr.name, - sym_name_len); - if (symb_table[2 * elem] != 0) - { - /* We found the entry. */ - idx = symb_table[2 * elem + 1]; - /* Skip the name of collating element name. */ - idx += 1 + extra[idx]; - /* Skip the byte sequence of the collating element. */ - idx += 1 + extra[idx]; - /* Adjust for the alignment. */ - idx = (idx + 3) & ~3; - /* Skip the multibyte collation sequence value. */ - idx += sizeof (unsigned int); - /* Skip the wide char sequence of the collating element. */ - idx += sizeof (unsigned int) * - (1 + *(unsigned int *) (extra + idx)); - /* Return the collation sequence value. */ - return *(unsigned int *) (extra + idx); - } - else if (symb_table[2 * elem] == 0 && sym_name_len == 1) - { - /* No valid character. Match it as a single byte - character. */ - return collseqmb[br_elem->opr.name[0]]; - } - } - else if (sym_name_len == 1) - return collseqmb[br_elem->opr.name[0]]; - } + { + size_t sym_name_len = strlen ((char *) br_elem->opr.name); + if (nrules != 0) + { + int32_t elem, idx; + elem = seek_collating_symbol_entry (br_elem->opr.name, + sym_name_len); + if (symb_table[2 * elem] != 0) + { + /* We found the entry. */ + idx = symb_table[2 * elem + 1]; + /* Skip the name of collating element name. */ + idx += 1 + extra[idx]; + /* Skip the byte sequence of the collating element. */ + idx += 1 + extra[idx]; + /* Adjust for the alignment. */ + idx = (idx + 3) & ~3; + /* Skip the multibyte collation sequence value. */ + idx += sizeof (unsigned int); + /* Skip the wide char sequence of the collating element. */ + idx += sizeof (unsigned int) * + (1 + *(unsigned int *) (extra + idx)); + /* Return the collation sequence value. */ + return *(unsigned int *) (extra + idx); + } + else if (symb_table[2 * elem] == 0 && sym_name_len == 1) + { + /* No valid character. Match it as a single byte + character. */ + return collseqmb[br_elem->opr.name[0]]; + } + } + else if (sym_name_len == 1) + return collseqmb[br_elem->opr.name[0]]; + } return UINT_MAX; } @@ -2612,13 +2614,13 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) static inline reg_errcode_t # ifdef RE_ENABLE_I18N build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem) - re_charset_t *mbcset; - int *range_alloc; + re_charset_t *mbcset; + int *range_alloc; # else /* not RE_ENABLE_I18N */ build_range_exp (sbcset, start_elem, end_elem) # endif /* not RE_ENABLE_I18N */ - re_bitset_ptr_t sbcset; - bracket_elem_t *start_elem, *end_elem; + re_bitset_ptr_t sbcset; + bracket_elem_t *start_elem, *end_elem; { unsigned int ch; uint32_t start_collseq; @@ -2627,44 +2629,44 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) # ifdef RE_ENABLE_I18N /* Check the space of the arrays. */ if (*range_alloc == mbcset->nranges) - { - /* There are not enough space, need realloc. */ - uint32_t *new_array_start; - uint32_t *new_array_end; + { + /* There are not enough space, need realloc. */ + uint32_t *new_array_start; + uint32_t *new_array_end; int new_nranges; - /* +1 in case of mbcset->nranges is 0. */ - new_nranges = 2 * mbcset->nranges + 1; + /* +1 in case of mbcset->nranges is 0. */ + new_nranges = 2 * mbcset->nranges + 1; /* Use realloc since mbcset->range_starts and mbcset->range_ends - are NULL if *range_alloc == 0. */ - new_array_start = re_realloc (mbcset->range_starts, uint32_t, - new_nranges); - new_array_end = re_realloc (mbcset->range_ends, uint32_t, - new_nranges); + are NULL if *range_alloc == 0. */ + new_array_start = re_realloc (mbcset->range_starts, uint32_t, + new_nranges); + new_array_end = re_realloc (mbcset->range_ends, uint32_t, + new_nranges); - if (BE (new_array_start == NULL || new_array_end == NULL, 0)) - return REG_ESPACE; + if (BE (new_array_start == NULL || new_array_end == NULL, 0)) + return REG_ESPACE; - mbcset->range_starts = new_array_start; - mbcset->range_ends = new_array_end; + mbcset->range_starts = new_array_start; + mbcset->range_ends = new_array_end; *range_alloc = new_nranges; - } + } # endif /* RE_ENABLE_I18N */ /* Equivalence Classes and Character Classes can't be a range - start/end. */ + start/end. */ if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS - || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS, - 0)) - return REG_ERANGE; + || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS, + 0)) + return REG_ERANGE; start_collseq = lookup_collation_sequence_value (start_elem); end_collseq = lookup_collation_sequence_value (end_elem); /* Check start/end collation sequence values. */ if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0)) - return REG_ECOLLATE; + return REG_ECOLLATE; if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0)) - return REG_ERANGE; + return REG_ERANGE; # ifdef RE_ENABLE_I18N /* Got valid collation sequence values, add them as a new entry. */ @@ -2674,18 +2676,18 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) /* Build the table for single byte characters. */ for (ch = 0; ch <= SBC_MAX; ch++) - { - uint32_t ch_collseq; - /* - if (MB_CUR_MAX == 1) - */ - if (nrules == 0) - ch_collseq = collseqmb[ch]; - else - ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch)); - if (start_collseq <= ch_collseq && ch_collseq <= end_collseq) - bitset_set (sbcset, ch); - } + { + uint32_t ch_collseq; + /* + if (MB_CUR_MAX == 1) + */ + if (nrules == 0) + ch_collseq = collseqmb[ch]; + else + ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch)); + if (start_collseq <= ch_collseq && ch_collseq <= end_collseq) + bitset_set (sbcset, ch); + } return REG_NOERROR; } @@ -2698,65 +2700,65 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) static inline reg_errcode_t # ifdef RE_ENABLE_I18N build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name) - re_charset_t *mbcset; - int *coll_sym_alloc; + re_charset_t *mbcset; + int *coll_sym_alloc; # else /* not RE_ENABLE_I18N */ build_collating_symbol (sbcset, name) # endif /* not RE_ENABLE_I18N */ - re_bitset_ptr_t sbcset; - const unsigned char *name; + re_bitset_ptr_t sbcset; + const unsigned char *name; { int32_t elem, idx; size_t name_len = strlen ((const char *) name); if (nrules != 0) - { - elem = seek_collating_symbol_entry (name, name_len); - if (symb_table[2 * elem] != 0) - { - /* We found the entry. */ - idx = symb_table[2 * elem + 1]; - /* Skip the name of collating element name. */ - idx += 1 + extra[idx]; - } - else if (symb_table[2 * elem] == 0 && name_len == 1) - { - /* No valid character, treat it as a normal - character. */ - bitset_set (sbcset, name[0]); - return REG_NOERROR; - } - else - return REG_ECOLLATE; + { + elem = seek_collating_symbol_entry (name, name_len); + if (symb_table[2 * elem] != 0) + { + /* We found the entry. */ + idx = symb_table[2 * elem + 1]; + /* Skip the name of collating element name. */ + idx += 1 + extra[idx]; + } + else if (symb_table[2 * elem] == 0 && name_len == 1) + { + /* No valid character, treat it as a normal + character. */ + bitset_set (sbcset, name[0]); + return REG_NOERROR; + } + else + return REG_ECOLLATE; # ifdef RE_ENABLE_I18N - /* Got valid collation sequence, add it as a new entry. */ - /* Check the space of the arrays. */ - if (*coll_sym_alloc == mbcset->ncoll_syms) - { - /* Not enough, realloc it. */ - /* +1 in case of mbcset->ncoll_syms is 0. */ - *coll_sym_alloc = 2 * mbcset->ncoll_syms + 1; - /* Use realloc since mbcset->coll_syms is NULL - if *alloc == 0. */ - mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t, - *coll_sym_alloc); - if (BE (mbcset->coll_syms == NULL, 0)) - return REG_ESPACE; - } - mbcset->coll_syms[mbcset->ncoll_syms++] = idx; + /* Got valid collation sequence, add it as a new entry. */ + /* Check the space of the arrays. */ + if (*coll_sym_alloc == mbcset->ncoll_syms) + { + /* Not enough, realloc it. */ + /* +1 in case of mbcset->ncoll_syms is 0. */ + *coll_sym_alloc = 2 * mbcset->ncoll_syms + 1; + /* Use realloc since mbcset->coll_syms is NULL + if *alloc == 0. */ + mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t, + *coll_sym_alloc); + if (BE (mbcset->coll_syms == NULL, 0)) + return REG_ESPACE; + } + mbcset->coll_syms[mbcset->ncoll_syms++] = idx; # endif /* RE_ENABLE_I18N */ - return REG_NOERROR; - } + return REG_NOERROR; + } else - { - if (BE (name_len != 1, 0)) - return REG_ECOLLATE; - else - { - bitset_set (sbcset, name[0]); - return REG_NOERROR; - } - } + { + if (BE (name_len != 1, 0)) + return REG_ECOLLATE; + else + { + bitset_set (sbcset, name[0]); + return REG_NOERROR; + } + } } #endif @@ -2780,12 +2782,12 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) /* if (MB_CUR_MAX > 1) */ - collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC); + collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC); table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB); symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE, - _NL_COLLATE_SYMB_TABLEMB); + _NL_COLLATE_SYMB_TABLEMB); extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE, - _NL_COLLATE_SYMB_EXTRAMB); + _NL_COLLATE_SYMB_EXTRAMB); } #endif sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS); @@ -2817,19 +2819,19 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) non_match = 1; #endif /* not RE_ENABLE_I18N */ if (syntax & RE_HAT_LISTS_NOT_NEWLINE) - bitset_set (sbcset, '\0'); + bitset_set (sbcset, '\0'); re_string_skip_bytes (regexp, token_len); /* Skip a token. */ token_len = peek_token_bracket (token, regexp, syntax); if (BE (token->type == END_OF_RE, 0)) - { - *err = REG_BADPAT; - goto parse_bracket_exp_free_return; - } + { + *err = REG_BADPAT; + goto parse_bracket_exp_free_return; + } #ifdef RE_ENABLE_I18N if (MB_CUR_MAX > 1) - for (i = 0; i < SBC_MAX; ++i) - if (__btowc (i) == WEOF) - bitset_set (sbcset, i); + for (i = 0; i < SBC_MAX; ++i) + if (__btowc (i) == WEOF) + bitset_set (sbcset, i); #endif /* RE_ENABLE_I18N */ } @@ -2848,121 +2850,121 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) start_elem.opr.name = start_name_buf; ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa, - syntax); + syntax); if (BE (ret != REG_NOERROR, 0)) - { - *err = ret; - goto parse_bracket_exp_free_return; - } + { + *err = ret; + goto parse_bracket_exp_free_return; + } token_len = peek_token_bracket (token, regexp, syntax); if (BE (token->type == END_OF_RE, 0)) - { - *err = REG_BADPAT; - goto parse_bracket_exp_free_return; - } + { + *err = REG_BADPAT; + goto parse_bracket_exp_free_return; + } if (token->type == OP_CHARSET_RANGE) - { - re_string_skip_bytes (regexp, token_len); /* Skip '-'. */ - token_len2 = peek_token_bracket (&token2, regexp, syntax); - if (BE (token->type == END_OF_RE, 0)) - { - *err = REG_BADPAT; - goto parse_bracket_exp_free_return; - } - if (token2.type == OP_CLOSE_BRACKET) - { - /* We treat the last '-' as a normal character. */ - re_string_skip_bytes (regexp, -token_len); - token->type = CHARACTER; - } - else - is_range_exp = 1; - } + { + re_string_skip_bytes (regexp, token_len); /* Skip '-'. */ + token_len2 = peek_token_bracket (&token2, regexp, syntax); + if (BE (token->type == END_OF_RE, 0)) + { + *err = REG_BADPAT; + goto parse_bracket_exp_free_return; + } + if (token2.type == OP_CLOSE_BRACKET) + { + /* We treat the last '-' as a normal character. */ + re_string_skip_bytes (regexp, -token_len); + token->type = CHARACTER; + } + else + is_range_exp = 1; + } if (is_range_exp == 1) - { - end_elem.opr.name = end_name_buf; - ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2, - dfa, syntax); - if (BE (ret != REG_NOERROR, 0)) - { - *err = ret; - goto parse_bracket_exp_free_return; - } - - token_len = peek_token_bracket (token, regexp, syntax); - if (BE (token->type == END_OF_RE, 0)) - { - *err = REG_BADPAT; - goto parse_bracket_exp_free_return; - } - *err = build_range_exp (sbcset, + { + end_elem.opr.name = end_name_buf; + ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2, + dfa, syntax); + if (BE (ret != REG_NOERROR, 0)) + { + *err = ret; + goto parse_bracket_exp_free_return; + } + + token_len = peek_token_bracket (token, regexp, syntax); + if (BE (token->type == END_OF_RE, 0)) + { + *err = REG_BADPAT; + goto parse_bracket_exp_free_return; + } + *err = build_range_exp (sbcset, #ifdef RE_ENABLE_I18N - mbcset, &range_alloc, + mbcset, &range_alloc, #endif /* RE_ENABLE_I18N */ - &start_elem, &end_elem); - if (BE (*err != REG_NOERROR, 0)) - goto parse_bracket_exp_free_return; - } + &start_elem, &end_elem); + if (BE (*err != REG_NOERROR, 0)) + goto parse_bracket_exp_free_return; + } else - { - switch (start_elem.type) - { - case SB_CHAR: - bitset_set (sbcset, start_elem.opr.ch); - break; + { + switch (start_elem.type) + { + case SB_CHAR: + bitset_set (sbcset, start_elem.opr.ch); + break; #ifdef RE_ENABLE_I18N - case MB_CHAR: - /* Check whether the array has enough space. */ - if (mbchar_alloc == mbcset->nmbchars) - { - /* Not enough, realloc it. */ - /* +1 in case of mbcset->nmbchars is 0. */ - mbchar_alloc = 2 * mbcset->nmbchars + 1; - /* Use realloc since array is NULL if *alloc == 0. */ - mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t, - mbchar_alloc); - if (BE (mbcset->mbchars == NULL, 0)) - goto parse_bracket_exp_espace; - } - mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch; - break; + case MB_CHAR: + /* Check whether the array has enough space. */ + if (mbchar_alloc == mbcset->nmbchars) + { + /* Not enough, realloc it. */ + /* +1 in case of mbcset->nmbchars is 0. */ + mbchar_alloc = 2 * mbcset->nmbchars + 1; + /* Use realloc since array is NULL if *alloc == 0. */ + mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t, + mbchar_alloc); + if (BE (mbcset->mbchars == NULL, 0)) + goto parse_bracket_exp_espace; + } + mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch; + break; #endif /* RE_ENABLE_I18N */ - case EQUIV_CLASS: - *err = build_equiv_class (sbcset, + case EQUIV_CLASS: + *err = build_equiv_class (sbcset, #ifdef RE_ENABLE_I18N - mbcset, &equiv_class_alloc, + mbcset, &equiv_class_alloc, #endif /* RE_ENABLE_I18N */ start_elem.opr.name); - if (BE (*err != REG_NOERROR, 0)) - goto parse_bracket_exp_free_return; - break; - case COLL_SYM: - *err = build_collating_symbol (sbcset, + if (BE (*err != REG_NOERROR, 0)) + goto parse_bracket_exp_free_return; + break; + case COLL_SYM: + *err = build_collating_symbol (sbcset, #ifdef RE_ENABLE_I18N - mbcset, &coll_sym_alloc, + mbcset, &coll_sym_alloc, #endif /* RE_ENABLE_I18N */ start_elem.opr.name); - if (BE (*err != REG_NOERROR, 0)) - goto parse_bracket_exp_free_return; - break; - case CHAR_CLASS: - ret = build_charclass (sbcset, + if (BE (*err != REG_NOERROR, 0)) + goto parse_bracket_exp_free_return; + break; + case CHAR_CLASS: + ret = build_charclass (sbcset, #ifdef RE_ENABLE_I18N - mbcset, &char_class_alloc, + mbcset, &char_class_alloc, #endif /* RE_ENABLE_I18N */ - start_elem.opr.name, syntax); - if (BE (ret != REG_NOERROR, 0)) - goto parse_bracket_exp_espace; - break; - default: - assert (0); - break; - } - } + start_elem.opr.name, syntax); + if (BE (ret != REG_NOERROR, 0)) + goto parse_bracket_exp_espace; + break; + default: + assert (0); + break; + } + } if (token->type == OP_CLOSE_BRACKET) - break; + break; } re_string_skip_bytes (regexp, token_len); /* Skip a token. */ @@ -2986,7 +2988,7 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) #ifdef RE_ENABLE_I18N if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes || mbcset->nranges || (MB_CUR_MAX > 1 && (mbcset->nchar_classes - || mbcset->non_match))) + || mbcset->non_match))) { re_token_t alt_token; bin_tree_t *mbc_tree; @@ -2997,14 +2999,14 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) new_idx = re_dfa_add_node (dfa, br_token, 0); mbc_tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || mbc_tree == NULL, 0)) - goto parse_bracket_exp_espace; + goto parse_bracket_exp_espace; /* Then join them by ALT node. */ dfa->has_plural_match = 1; alt_token.type = OP_ALT; new_idx = re_dfa_add_node (dfa, alt_token, 0); work_tree = create_tree (work_tree, mbc_tree, 0, new_idx); if (BE (new_idx != -1 && mbc_tree != NULL, 1)) - return work_tree; + return work_tree; } else { @@ -3071,13 +3073,13 @@ parse_bracket_symbol (elem, regexp, token) for (;; ++i) { if (re_string_eoi(regexp) || i >= BRACKET_NAME_BUF_SIZE) - return REG_EBRACK; + return REG_EBRACK; if (token->type == OP_OPEN_CHAR_CLASS) - ch = re_string_fetch_byte_case (regexp); + ch = re_string_fetch_byte_case (regexp); else - ch = re_string_fetch_byte (regexp); + ch = re_string_fetch_byte (regexp); if (ch == delim && re_string_peek_byte (regexp, 0) == ']') - break; + break; elem->opr.name[i] = ch; } re_string_skip_bytes (regexp, 1); @@ -3134,58 +3136,58 @@ build_equiv_class (sbcset, name) weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB); extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE, - _NL_COLLATE_EXTRAMB); + _NL_COLLATE_EXTRAMB); indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE, - _NL_COLLATE_INDIRECTMB); + _NL_COLLATE_INDIRECTMB); idx1 = findidx (&cp); if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0)) - /* This isn't a valid character. */ - return REG_ECOLLATE; + /* This isn't a valid character. */ + return REG_ECOLLATE; /* Build single byte matcing table for this equivalence class. */ char_buf[1] = (unsigned char) '\0'; len = weights[idx1]; for (ch = 0; ch < SBC_MAX; ++ch) - { - char_buf[0] = ch; - cp = char_buf; - idx2 = findidx (&cp); + { + char_buf[0] = ch; + cp = char_buf; + idx2 = findidx (&cp); /* - idx2 = table[ch]; + idx2 = table[ch]; */ - if (idx2 == 0) - /* This isn't a valid character. */ - continue; - if (len == weights[idx2]) - { - int cnt = 0; - while (cnt <= len && - weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt]) - ++cnt; - - if (cnt > len) - bitset_set (sbcset, ch); - } - } + if (idx2 == 0) + /* This isn't a valid character. */ + continue; + if (len == weights[idx2]) + { + int cnt = 0; + while (cnt <= len && + weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt]) + ++cnt; + + if (cnt > len) + bitset_set (sbcset, ch); + } + } /* Check whether the array has enough space. */ if (*equiv_class_alloc == mbcset->nequiv_classes) - { - /* Not enough, realloc it. */ - /* +1 in case of mbcset->nequiv_classes is 0. */ - *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1; - /* Use realloc since the array is NULL if *alloc == 0. */ - mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t, - *equiv_class_alloc); - if (BE (mbcset->equiv_classes == NULL, 0)) - return REG_ESPACE; - } + { + /* Not enough, realloc it. */ + /* +1 in case of mbcset->nequiv_classes is 0. */ + *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1; + /* Use realloc since the array is NULL if *alloc == 0. */ + mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t, + *equiv_class_alloc); + if (BE (mbcset->equiv_classes == NULL, 0)) + return REG_ESPACE; + } mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1; } else #endif /* _LIBC && RE_ENABLE_I18N */ { if (BE (strlen ((const char *) name) != 1, 0)) - return REG_ECOLLATE; + return REG_ECOLLATE; bitset_set (sbcset, *name); } return REG_NOERROR; @@ -3227,9 +3229,9 @@ build_charclass (sbcset, class_name, syntax) *char_class_alloc = 2 * mbcset->nchar_classes + 1; /* Use realloc since array is NULL if *alloc == 0. */ mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t, - *char_class_alloc); + *char_class_alloc); if (BE (mbcset->char_classes == NULL, 0)) - return REG_ESPACE; + return REG_ESPACE; } mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name); #endif /* RE_ENABLE_I18N */ @@ -3237,8 +3239,8 @@ build_charclass (sbcset, class_name, syntax) #define BUILD_CHARCLASS_LOOP(ctype_func)\ for (i = 0; i < SBC_MAX; ++i) \ { \ - if (ctype_func (i)) \ - bitset_set (sbcset, i); \ + if (ctype_func (i)) \ + bitset_set (sbcset, i); \ } if (strcmp (name, "alnum") == 0) @@ -3310,13 +3312,13 @@ build_word_op (dfa, not, err) int i; /* if (syntax & RE_HAT_LISTS_NOT_NEWLINE) - bitset_set(cset->sbcset, '\0'); + bitset_set(cset->sbcset, '\0'); */ mbcset->non_match = 1; if (MB_CUR_MAX > 1) - for (i = 0; i < SBC_MAX; ++i) - if (__btowc (i) == WEOF) - bitset_set (sbcset, i); + for (i = 0; i < SBC_MAX; ++i) + if (__btowc (i) == WEOF) + bitset_set (sbcset, i); #else /* not RE_ENABLE_I18N */ non_match = 1; #endif /* not RE_ENABLE_I18N */ @@ -3325,9 +3327,9 @@ build_word_op (dfa, not, err) /* We don't care the syntax in this case. */ ret = build_charclass (sbcset, #ifdef RE_ENABLE_I18N - mbcset, &alloc, + mbcset, &alloc, #endif /* RE_ENABLE_I18N */ - (const unsigned char *) "alpha", 0); + (const unsigned char *) "alpha", 0); if (BE (ret != REG_NOERROR, 0)) { @@ -3369,13 +3371,13 @@ build_word_op (dfa, not, err) new_idx = re_dfa_add_node (dfa, br_token, 0); mbc_tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || mbc_tree == NULL, 0)) - goto build_word_op_espace; + goto build_word_op_espace; /* Then join them by ALT node. */ alt_token.type = OP_ALT; new_idx = re_dfa_add_node (dfa, alt_token, 0); tree = create_tree (tree, mbc_tree, 0, new_idx); if (BE (new_idx != -1 && mbc_tree != NULL, 1)) - return tree; + return tree; } else { @@ -3413,11 +3415,11 @@ fetch_number (input, token, syntax) *token = fetch_token (input, syntax); c = token->opr.c; if (BE (token->type == END_OF_RE, 0)) - return -2; + return -2; if (token->type == OP_CLOSE_DUP_NUM || c == ',') - break; + break; num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2) - ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0')); + ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0')); num = (num > RE_DUP_MAX) ? -2 : num; } return num; @@ -3504,7 +3506,7 @@ duplicate_tree (src, dfa) { left = duplicate_tree (src->left, dfa); if (left == NULL) - return NULL; + return NULL; } /* Secondaly, duplicate the right. */ @@ -3512,10 +3514,10 @@ duplicate_tree (src, dfa) { right = duplicate_tree (src->right, dfa); if (right == NULL) - { - free_bin_tree (left); - return NULL; - } + { + free_bin_tree (left); + return NULL; + } } /* At last, duplicate itself. */ @@ -3524,11 +3526,11 @@ duplicate_tree (src, dfa) new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0); dfa->nodes[new_node_idx].duplicated = 1; if (BE (new_node_idx == -1, 0)) - { - free_bin_tree (left); - free_bin_tree (right); - return NULL; - } + { + free_bin_tree (left); + free_bin_tree (right); + return NULL; + } } else new_node_idx = src->type; diff --git a/posix/regex_internal.h b/posix/regex_internal.h index 7193ea0315..7d5fffac4d 100644 --- a/posix/regex_internal.h +++ b/posix/regex_internal.h @@ -270,15 +270,15 @@ typedef struct re_string_t re_string_t; static reg_errcode_t re_string_allocate (re_string_t *pstr, const char *str, - int len, int init_len, - RE_TRANSLATE_TYPE trans, int icase); + int len, int init_len, + RE_TRANSLATE_TYPE trans, int icase); static reg_errcode_t re_string_construct (re_string_t *pstr, const char *str, - int len, RE_TRANSLATE_TYPE trans, - int icase); + int len, RE_TRANSLATE_TYPE trans, + int icase); static reg_errcode_t re_string_reconstruct (re_string_t *pstr, int idx, - int eflags, int newline); + int eflags, int newline); static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr, - int new_buf_len); + int new_buf_len); #ifdef RE_ENABLE_I18N static void build_wcs_buffer (re_string_t *pstr); static void build_wcs_upper_buffer (re_string_t *pstr); @@ -305,7 +305,7 @@ static unsigned int re_string_context_at (const re_string_t *input, int idx, ((idx) == (pstr)->len || (pstr)->wcs[idx] != WEOF) #define re_string_is_single_byte_char(pstr, idx) \ ((pstr)->wcs[idx] != WEOF && ((pstr)->len == (idx) \ - || (pstr)->wcs[(idx) + 1] != WEOF)) + || (pstr)->wcs[(idx) + 1] != WEOF)) #define re_string_eoi(pstr) ((pstr)->stop <= (pstr)->cur_idx) #define re_string_cur_idx(pstr) ((pstr)->cur_idx) #define re_string_get_buffer(pstr) ((pstr)->mbs) @@ -495,21 +495,21 @@ typedef struct re_dfa_t re_dfa_t; static reg_errcode_t re_node_set_alloc (re_node_set *set, int size); static reg_errcode_t re_node_set_init_1 (re_node_set *set, int elem); static reg_errcode_t re_node_set_init_2 (re_node_set *set, int elem1, - int elem2); + int elem2); #define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set)) static reg_errcode_t re_node_set_init_copy (re_node_set *dest, - const re_node_set *src); + const re_node_set *src); static reg_errcode_t re_node_set_add_intersect (re_node_set *dest, - const re_node_set *src1, - const re_node_set *src2); + const re_node_set *src1, + const re_node_set *src2); static reg_errcode_t re_node_set_init_union (re_node_set *dest, - const re_node_set *src1, - const re_node_set *src2); + const re_node_set *src1, + const re_node_set *src2); static reg_errcode_t re_node_set_merge (re_node_set *dest, - const re_node_set *src); + const re_node_set *src); static int re_node_set_insert (re_node_set *set, int elem); static int re_node_set_compare (const re_node_set *set1, - const re_node_set *set2); + const re_node_set *set2); static int re_node_set_contains (const re_node_set *set, int elem); static void re_node_set_remove_at (re_node_set *set, int idx); #define re_node_set_remove(set,id) \ @@ -518,11 +518,12 @@ static void re_node_set_remove_at (re_node_set *set, int idx); #define re_node_set_free(set) re_free ((set)->elems) static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token, int mode); static re_dfastate_t *re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, - const re_node_set *nodes); + const re_node_set *nodes); static re_dfastate_t *re_acquire_state_context (reg_errcode_t *err, - re_dfa_t *dfa, - const re_node_set *nodes, - unsigned int context); + re_dfa_t *dfa, + const re_node_set *nodes, + unsigned int context); +static void free_state (re_dfastate_t *state); typedef enum @@ -618,7 +619,7 @@ re_string_elem_size_at (pstr, idx) { table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); extra = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB); p = pstr->mbs + idx; diff --git a/posix/regexec.c b/posix/regexec.c index 17c469c47f..f7e0d7f062 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -47,136 +47,136 @@ static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags, re_string_t *input, int n); static void match_ctx_free (re_match_context_t *cache); static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node, - int str_idx, int from, int to); + int str_idx, int from, int to); static void match_ctx_clear_flag (re_match_context_t *mctx); 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, int check_subexp); + re_dfastate_t **limited_sts, int last_node, + int last_str_idx, int check_subexp); static reg_errcode_t re_search_internal (const regex_t *preg, - const char *string, int length, - int start, int range, int stop, - size_t nmatch, regmatch_t pmatch[], - int eflags); + const char *string, int length, + int start, int range, int stop, + size_t nmatch, regmatch_t pmatch[], + int eflags); 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); + const char *string1, int length1, + const char *string2, int length2, + int start, int range, struct re_registers *regs, + int stop, int ret_len); 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); + const char *string, int length, int start, + int range, int stop, struct re_registers *regs, + int ret_len); static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, - int nregs, int regs_allocated); + int nregs, int regs_allocated); static inline re_dfastate_t *acquire_init_state_context (reg_errcode_t *err, - const regex_t *preg, - const re_match_context_t *mctx, - int idx); + const regex_t *preg, + const re_match_context_t *mctx, + int idx); static int check_matching (const regex_t *preg, re_match_context_t *mctx, - int fl_search, int fl_longest_match); + int fl_search, int fl_longest_match); static int check_halt_node_context (const re_dfa_t *dfa, int node, - unsigned int context); + unsigned int context); static int check_halt_state_context (const regex_t *preg, - const re_dfastate_t *state, - const re_match_context_t *mctx, int idx); + const re_dfastate_t *state, + const re_match_context_t *mctx, int idx); static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch, int cur_node, - int cur_idx, int nmatch); + int cur_idx, int nmatch); static int proceed_next_node (const regex_t *preg, int nregs, regmatch_t *regs, - const re_match_context_t *mctx, - int *pidx, int node, re_node_set *eps_via_nodes, - struct re_fail_stack_t *fs); + const re_match_context_t *mctx, + int *pidx, int node, re_node_set *eps_via_nodes, + struct re_fail_stack_t *fs); static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs, - int str_idx, int *dests, int nregs, - regmatch_t *regs, - re_node_set *eps_via_nodes); + int str_idx, int *dests, int nregs, + regmatch_t *regs, + re_node_set *eps_via_nodes); static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs, - regmatch_t *regs, re_node_set *eps_via_nodes); + regmatch_t *regs, re_node_set *eps_via_nodes); 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); + const re_match_context_t *mctx, + size_t nmatch, regmatch_t *pmatch, + int fl_backtrack); static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs); #ifdef RE_ENABLE_I18N static int sift_states_iter_mb (const regex_t *preg, - const re_match_context_t *mctx, - re_sift_context_t *sctx, - int node_idx, int str_idx, int max_str_idx); + const re_match_context_t *mctx, + re_sift_context_t *sctx, + int node_idx, int str_idx, int max_str_idx); #endif /* RE_ENABLE_I18N */ static reg_errcode_t sift_states_backward (const regex_t *preg, - re_match_context_t *mctx, - re_sift_context_t *sctx); + re_match_context_t *mctx, + re_sift_context_t *sctx); static reg_errcode_t update_cur_sifted_state (const regex_t *preg, - re_match_context_t *mctx, - re_sift_context_t *sctx, - int str_idx, - re_node_set *dest_nodes); + re_match_context_t *mctx, + re_sift_context_t *sctx, + int str_idx, + re_node_set *dest_nodes); static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa, - re_node_set *dest_nodes, - const re_node_set *candidates); + re_node_set *dest_nodes, + const re_node_set *candidates); static reg_errcode_t sub_epsilon_src_nodes (re_dfa_t *dfa, int node, - re_node_set *dest_nodes, - const re_node_set *and_nodes); + re_node_set *dest_nodes, + const re_node_set *and_nodes); static int check_dst_limits (re_dfa_t *dfa, re_node_set *limits, - re_match_context_t *mctx, int dst_node, - int dst_idx, int src_node, int src_idx); + re_match_context_t *mctx, int dst_node, + int dst_idx, int src_node, int src_idx); static int check_dst_limits_calc_pos (re_dfa_t *dfa, re_match_context_t *mctx, - int limit, re_node_set *eclosures, - int subexp_idx, int node, int str_idx); + int limit, re_node_set *eclosures, + int subexp_idx, int node, int str_idx); static reg_errcode_t check_subexp_limits (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); + re_node_set *dest_nodes, + const re_node_set *candidates, + re_node_set *limits, + struct re_backref_cache_entry *bkref_ents, + int str_idx); static reg_errcode_t search_subexp (const regex_t *preg, - re_match_context_t *mctx, - re_sift_context_t *sctx, int str_idx, - re_node_set *dest_nodes); + re_match_context_t *mctx, + re_sift_context_t *sctx, int str_idx, + re_node_set *dest_nodes); static reg_errcode_t sift_states_bkref (const regex_t *preg, - re_match_context_t *mctx, - re_sift_context_t *sctx, - int str_idx, re_node_set *dest_nodes); + re_match_context_t *mctx, + re_sift_context_t *sctx, + int str_idx, re_node_set *dest_nodes); static reg_errcode_t clean_state_log_if_need (re_match_context_t *mctx, - int next_state_log_idx); + int next_state_log_idx); static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, - re_dfastate_t **src, int num); + re_dfastate_t **src, int num); static re_dfastate_t *transit_state (reg_errcode_t *err, const regex_t *preg, - re_match_context_t *mctx, - re_dfastate_t *state, int fl_search); + re_match_context_t *mctx, + re_dfastate_t *state, int fl_search); static re_dfastate_t *transit_state_sb (reg_errcode_t *err, const regex_t *preg, - re_dfastate_t *pstate, - int fl_search, - re_match_context_t *mctx); + re_dfastate_t *pstate, + int fl_search, + re_match_context_t *mctx); #ifdef RE_ENABLE_I18N static reg_errcode_t transit_state_mb (const regex_t *preg, - re_dfastate_t *pstate, - re_match_context_t *mctx); + re_dfastate_t *pstate, + re_match_context_t *mctx); #endif /* RE_ENABLE_I18N */ static reg_errcode_t transit_state_bkref (const regex_t *preg, - re_dfastate_t *pstate, - re_match_context_t *mctx); + re_dfastate_t *pstate, + re_match_context_t *mctx); static reg_errcode_t transit_state_bkref_loop (const regex_t *preg, - re_node_set *nodes, - re_dfastate_t **work_state_log, - re_match_context_t *mctx); + re_node_set *nodes, + re_dfastate_t **work_state_log, + re_match_context_t *mctx); static re_dfastate_t **build_trtable (const regex_t *dfa, - const re_dfastate_t *state, - int fl_search); + const re_dfastate_t *state, + int fl_search); #ifdef RE_ENABLE_I18N static int check_node_accept_bytes (const regex_t *preg, int node_idx, - const re_string_t *input, int idx); + const re_string_t *input, int idx); # ifdef _LIBC static unsigned int find_collation_sequence_value (const unsigned char *mbs, - size_t name_len); + size_t name_len); # endif /* _LIBC */ #endif /* RE_ENABLE_I18N */ static int group_nodes_into_DFAstates (const regex_t *dfa, - const re_dfastate_t *state, - re_node_set *states_node, - bitset *states_ch); + const re_dfastate_t *state, + re_node_set *states_node, + bitset *states_ch); static int check_node_accept (const regex_t *preg, const re_token_t *node, - const re_match_context_t *mctx, int idx); + const re_match_context_t *mctx, int idx); static reg_errcode_t extend_buffers (re_match_context_t *mctx); /* Entry point for POSIX code. */ @@ -207,10 +207,10 @@ regexec (preg, string, nmatch, pmatch, eflags) int length = strlen (string); if (preg->no_sub) err = re_search_internal (preg, string, length, 0, length, length, 0, - NULL, eflags); + NULL, eflags); else err = re_search_internal (preg, string, length, 0, length, length, nmatch, - pmatch, eflags); + pmatch, eflags); return err != REG_NOERROR; } #ifdef _LIBC @@ -280,7 +280,7 @@ re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop) struct re_registers *regs; { return re_search_2_stub (bufp, string1, length1, string2, length2, - start, 0, regs, stop, 1); + start, 0, regs, stop, 1); } #ifdef _LIBC weak_alias (__re_match_2, re_match_2) @@ -294,7 +294,7 @@ re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop) struct re_registers *regs; { return re_search_2_stub (bufp, string1, length1, string2, length2, - start, range, regs, stop, 0); + start, range, regs, stop, 0); } #ifdef _LIBC weak_alias (__re_search_2, re_search_2) @@ -302,7 +302,7 @@ weak_alias (__re_search_2, re_search_2) static int re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs, - stop, ret_len) + stop, ret_len) struct re_pattern_buffer *bufp; const char *string1, *string2; int length1, length2, start, range, stop, ret_len; @@ -320,14 +320,14 @@ re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs, if (length2 > 0) if (length1 > 0) { - char *s = re_malloc (char, len); - - if (BE (s == NULL, 0)) - return -2; - memcpy (s, string1, length1); - memcpy (s + length1, string2, length2); - str = s; - free_str = 1; + char *s = re_malloc (char, len); + + if (BE (s == NULL, 0)) + return -2; + memcpy (s, string1, length1); + memcpy (s + length1, string2, length2); + str = s; + free_str = 1; } else str = string2; @@ -335,7 +335,7 @@ re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs, str = string1; rval = re_search_stub (bufp, str, len, start, range, stop, regs, - ret_len); + ret_len); if (free_str) re_free ((char *) str); return rval; @@ -380,15 +380,15 @@ re_search_stub (bufp, string, length, start, range, stop, regs, ret_len) if (regs == NULL) nregs = 1; else if (BE (bufp->regs_allocated == REGS_FIXED && - regs->num_regs < bufp->re_nsub + 1, 0)) + regs->num_regs < bufp->re_nsub + 1, 0)) { nregs = regs->num_regs; if (BE (nregs < 1, 0)) - { - /* Nothing can be copied to regs. */ - regs = NULL; - nregs = 1; - } + { + /* Nothing can be copied to regs. */ + regs = NULL; + nregs = 1; + } } else nregs = bufp->re_nsub + 1; @@ -397,7 +397,7 @@ re_search_stub (bufp, string, length, start, range, stop, regs, ret_len) return -2; result = re_search_internal (bufp, string, length, start, range, stop, - nregs, pmatch, eflags); + nregs, pmatch, eflags); rval = 0; @@ -408,20 +408,20 @@ re_search_stub (bufp, string, length, start, range, stop, regs, ret_len) { /* If caller wants register contents data back, copy them. */ bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs, - bufp->regs_allocated); + bufp->regs_allocated); if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0)) - rval = -2; + rval = -2; } if (BE (rval == 0, 1)) { if (ret_len) - { - assert (pmatch[0].rm_so == start); - rval = pmatch[0].rm_eo - start; - } + { + assert (pmatch[0].rm_so == start); + rval = pmatch[0].rm_eo - start; + } else - rval = pmatch[0].rm_so; + rval = pmatch[0].rm_so; } re_free (pmatch); return rval; @@ -444,36 +444,36 @@ re_copy_regs (regs, pmatch, nregs, regs_allocated) { /* No. So allocate them with malloc. */ regs->start = re_malloc (regoff_t, need_regs); if (BE (regs->start == NULL, 0)) - return REGS_UNALLOCATED; + return REGS_UNALLOCATED; regs->end = re_malloc (regoff_t, need_regs); if (BE (regs->end == NULL, 0)) - { - re_free (regs->start); - return REGS_UNALLOCATED; - } + { + re_free (regs->start); + return REGS_UNALLOCATED; + } regs->num_regs = need_regs; } else if (regs_allocated == REGS_REALLOCATE) { /* Yes. If we need more elements than were already - allocated, reallocate them. If we need fewer, just - leave it alone. */ + allocated, reallocate them. If we need fewer, just + leave it alone. */ if (need_regs > regs->num_regs) - { - regs->start = re_realloc (regs->start, regoff_t, need_regs); - if (BE (regs->start == NULL, 0)) - { - if (regs->end != NULL) - re_free (regs->end); - return REGS_UNALLOCATED; - } - regs->end = re_realloc (regs->end, regoff_t, need_regs); - if (BE (regs->end == NULL, 0)) - { - re_free (regs->start); - return REGS_UNALLOCATED; - } - regs->num_regs = need_regs; - } + { + regs->start = re_realloc (regs->start, regoff_t, need_regs); + if (BE (regs->start == NULL, 0)) + { + if (regs->end != NULL) + re_free (regs->end); + return REGS_UNALLOCATED; + } + regs->end = re_realloc (regs->end, regoff_t, need_regs); + if (BE (regs->end == NULL, 0)) + { + re_free (regs->start); + return REGS_UNALLOCATED; + } + regs->num_regs = need_regs; + } } else { @@ -563,7 +563,7 @@ static re_node_set empty_set; static reg_errcode_t re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, - eflags) + eflags) const regex_t *preg; const char *string; int length, start, range, stop, eflags; @@ -582,8 +582,8 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, /* Check if the DFA haven't been compiled. */ if (BE (preg->used == 0 || dfa->init_state == NULL - || dfa->init_state_word == NULL || dfa->init_state_nl == NULL - || dfa->init_state_begbuf == NULL, 0)) + || dfa->init_state_word == NULL || dfa->init_state_nl == NULL + || dfa->init_state_begbuf == NULL, 0)) return REG_NOMATCH; re_node_set_init_empty (&empty_set); @@ -593,7 +593,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, fl_longest_match = (nmatch != 0); err = re_string_allocate (&input, string, length, dfa->nodes_len + 1, - preg->translate, preg->syntax & RE_ICASE); + preg->translate, preg->syntax & RE_ICASE); if (BE (err != REG_NOERROR, 0)) goto free_return; input.stop = stop; @@ -610,10 +610,10 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, { mctx.state_log = re_malloc (re_dfastate_t *, dfa->nodes_len + 1); if (BE (mctx.state_log == NULL, 0)) - { - err = REG_ESPACE; - goto free_return; - } + { + err = REG_ESPACE; + goto free_return; + } } else mctx.state_log = NULL; @@ -625,7 +625,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, match_first = start; input.tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF - : CONTEXT_NEWLINE | CONTEXT_BEGBUF); + : CONTEXT_NEWLINE | CONTEXT_BEGBUF); /* Check incrementally whether of not the input string match. */ incr = (range < 0) ? -1 : 1; @@ -715,14 +715,14 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, } /* Reconstruct the buffers so that the matcher can assume that - the matching starts from the begining of the buffer. */ + the matching starts from the begining of the buffer. */ err = re_string_reconstruct (&input, match_first, eflags, preg->newline_anchor); if (BE (err != REG_NOERROR, 0)) goto free_return; #ifdef RE_ENABLE_I18N /* Eliminate it when it is a component of a multibyte character - and isn't the head of a multibyte character. */ + and isn't the head of a multibyte character. */ if (sb || re_string_first_byte (&input, 0)) #endif { @@ -745,7 +745,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, /* Update counter. */ match_first += incr; if (match_first < left_lim || right_lim < match_first) - break; + break; } /* Set pmatch[] if we need. */ @@ -755,84 +755,84 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, /* Initialize registers. */ for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) - pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1; + pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1; /* Set the points where matching start/end. */ pmatch[0].rm_so = 0; mctx.match_last = pmatch[0].rm_eo = match_last; if (!preg->no_sub && nmatch > 1) - { - /* We need the ranges of all the subexpressions. */ - int halt_node; - re_dfastate_t **sifted_states; - re_dfastate_t **lim_states = NULL; - re_dfastate_t *pstate = mctx.state_log[match_last]; - re_sift_context_t sctx; + { + /* We need the ranges of all the subexpressions. */ + int halt_node; + re_dfastate_t **sifted_states; + re_dfastate_t **lim_states = NULL; + re_dfastate_t *pstate = mctx.state_log[match_last]; + re_sift_context_t sctx; #ifdef DEBUG - assert (mctx.state_log != NULL); + assert (mctx.state_log != NULL); #endif - halt_node = check_halt_state_context (preg, pstate, &mctx, - match_last); - if (dfa->has_plural_match) - { - match_ctx_clear_flag (&mctx); - sifted_states = re_malloc (re_dfastate_t *, match_last + 1); - if (BE (sifted_states == NULL, 0)) - { - err = REG_ESPACE; - goto free_return; - } - if (dfa->nbackref) - { - lim_states = calloc (sizeof (re_dfastate_t *), - match_last + 1); - if (BE (lim_states == NULL, 0)) - { - re_free (sifted_states); - err = REG_ESPACE; - goto free_return; - } - } - sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, - mctx.match_last, 0); - err = sift_states_backward (preg, &mctx, &sctx); - re_node_set_free (&sctx.limits); - if (BE (err != REG_NOERROR, 0)) - { - re_free (sifted_states); - re_free (lim_states); - goto free_return; - } - if (lim_states != NULL) - { - err = merge_state_array (dfa, sifted_states, lim_states, - match_last + 1); - re_free (lim_states); - if (BE (err != REG_NOERROR, 0)) - { - re_free (sifted_states); - goto free_return; - } - } - re_free (mctx.state_log); - mctx.state_log = sifted_states; - } - mctx.last_node = halt_node; - err = set_regs (preg, &mctx, nmatch, pmatch, - dfa->has_plural_match && dfa->nbackref > 0); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } + halt_node = check_halt_state_context (preg, pstate, &mctx, + match_last); + if (dfa->has_plural_match) + { + match_ctx_clear_flag (&mctx); + sifted_states = re_malloc (re_dfastate_t *, match_last + 1); + if (BE (sifted_states == NULL, 0)) + { + err = REG_ESPACE; + goto free_return; + } + if (dfa->nbackref) + { + lim_states = calloc (sizeof (re_dfastate_t *), + match_last + 1); + if (BE (lim_states == NULL, 0)) + { + re_free (sifted_states); + err = REG_ESPACE; + goto free_return; + } + } + sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, + mctx.match_last, 0); + err = sift_states_backward (preg, &mctx, &sctx); + re_node_set_free (&sctx.limits); + if (BE (err != REG_NOERROR, 0)) + { + re_free (sifted_states); + re_free (lim_states); + goto free_return; + } + if (lim_states != NULL) + { + err = merge_state_array (dfa, sifted_states, lim_states, + match_last + 1); + re_free (lim_states); + if (BE (err != REG_NOERROR, 0)) + { + re_free (sifted_states); + goto free_return; + } + } + re_free (mctx.state_log); + mctx.state_log = sifted_states; + } + mctx.last_node = halt_node; + err = set_regs (preg, &mctx, nmatch, pmatch, + dfa->has_plural_match && dfa->nbackref > 0); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } /* At last, add the offset to the each registers, since we slided - the buffers so that We can assume that the matching starts from 0. */ + the buffers so that We can assume that the matching starts from 0. */ for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) - if (pmatch[reg_idx].rm_so != -1) - { - pmatch[reg_idx].rm_so += match_first; - pmatch[reg_idx].rm_eo += match_first; - } + if (pmatch[reg_idx].rm_so != -1) + { + pmatch[reg_idx].rm_so += match_first; + pmatch[reg_idx].rm_eo += match_first; + } } err = (match_last == -1) ? REG_NOMATCH : REG_NOERROR; free_return: @@ -861,25 +861,25 @@ acquire_init_state_context (err, preg, mctx, idx) { unsigned int context; context = re_string_context_at (mctx->input, idx - 1, mctx->eflags, - preg->newline_anchor); + preg->newline_anchor); if (IS_WORD_CONTEXT (context)) - return dfa->init_state_word; + return dfa->init_state_word; else if (IS_ORDINARY_CONTEXT (context)) - return dfa->init_state; + return dfa->init_state; else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context)) - return dfa->init_state_begbuf; + return dfa->init_state_begbuf; else if (IS_NEWLINE_CONTEXT (context)) - return dfa->init_state_nl; + return dfa->init_state_nl; else if (IS_BEGBUF_CONTEXT (context)) - { - /* It is relatively rare case, then calculate on demand. */ - return re_acquire_state_context (err, dfa, - dfa->init_state->entrance_nodes, - context); - } + { + /* It is relatively rare case, then calculate on demand. */ + return re_acquire_state_context (err, dfa, + dfa->init_state->entrance_nodes, + context); + } else - /* Must not happen? */ - return dfa->init_state; + /* Must not happen? */ + return dfa->init_state; } else return dfa->init_state; @@ -917,103 +917,103 @@ check_matching (preg, mctx, fl_search, fl_longest_match) int i; re_dfa_t *dfa = (re_dfa_t *) preg->buffer; for (i = 0; i < cur_state->nodes.nelem; ++i) - { - int node = cur_state->nodes.elems[i]; - re_token_type_t type = dfa->nodes[node].type; - if (type == OP_BACK_REF) - { - int clexp_idx; - for (clexp_idx = 0; clexp_idx < cur_state->nodes.nelem; - ++clexp_idx) - { - re_token_t *clexp_node; - clexp_node = dfa->nodes + cur_state->nodes.elems[clexp_idx]; - if (clexp_node->type == OP_CLOSE_SUBEXP - && clexp_node->opr.idx + 1== dfa->nodes[node].opr.idx) - { - err = match_ctx_add_entry (mctx, node, 0, 0, 0); - if (BE (err != REG_NOERROR, 0)) - return -2; - break; - } - } - } - } + { + int node = cur_state->nodes.elems[i]; + re_token_type_t type = dfa->nodes[node].type; + if (type == OP_BACK_REF) + { + int clexp_idx; + for (clexp_idx = 0; clexp_idx < cur_state->nodes.nelem; + ++clexp_idx) + { + re_token_t *clexp_node; + clexp_node = dfa->nodes + cur_state->nodes.elems[clexp_idx]; + if (clexp_node->type == OP_CLOSE_SUBEXP + && clexp_node->opr.idx + 1== dfa->nodes[node].opr.idx) + { + err = match_ctx_add_entry (mctx, node, 0, 0, 0); + if (BE (err != REG_NOERROR, 0)) + return -2; + break; + } + } + } + } } /* If the RE accepts NULL string. */ if (cur_state->halt) { if (!cur_state->has_constraint - || check_halt_state_context (preg, cur_state, mctx, cur_str_idx)) - { - if (!fl_longest_match) - return cur_str_idx; - else - { - match_last = cur_str_idx; - match = 1; - } - } + || check_halt_state_context (preg, cur_state, mctx, cur_str_idx)) + { + if (!fl_longest_match) + return cur_str_idx; + else + { + match_last = cur_str_idx; + match = 1; + } + } } while (!re_string_eoi (mctx->input)) { cur_state = transit_state (&err, preg, mctx, cur_state, - fl_search && !match); + fl_search && !match); if (cur_state == NULL) /* Reached at the invalid state or an error. */ - { - cur_str_idx = re_string_cur_idx (mctx->input); - if (BE (err != REG_NOERROR, 0)) - return -2; - if (fl_search && !match) - { - /* Restart from initial state, since we are searching - the point from where matching start. */ + { + cur_str_idx = re_string_cur_idx (mctx->input); + if (BE (err != REG_NOERROR, 0)) + return -2; + if (fl_search && !match) + { + /* Restart from initial state, since we are searching + the point from where matching start. */ #ifdef RE_ENABLE_I18N - if (MB_CUR_MAX == 1 - || re_string_first_byte (mctx->input, cur_str_idx)) + if (MB_CUR_MAX == 1 + || re_string_first_byte (mctx->input, cur_str_idx)) #endif /* RE_ENABLE_I18N */ - cur_state = acquire_init_state_context (&err, preg, mctx, - cur_str_idx); - if (BE (cur_state == NULL && err != REG_NOERROR, 0)) - return -2; - if (mctx->state_log != NULL) - mctx->state_log[cur_str_idx] = cur_state; - } - else if (!fl_longest_match && match) - break; - else /* (fl_longest_match && match) || (!fl_search && !match) */ - { - if (mctx->state_log == NULL) - break; - else - { - int max = mctx->state_log_top; - for (; cur_str_idx <= max; ++cur_str_idx) - if (mctx->state_log[cur_str_idx] != NULL) - break; - if (cur_str_idx > max) - break; - } - } - } + cur_state = acquire_init_state_context (&err, preg, mctx, + cur_str_idx); + if (BE (cur_state == NULL && err != REG_NOERROR, 0)) + return -2; + if (mctx->state_log != NULL) + mctx->state_log[cur_str_idx] = cur_state; + } + else if (!fl_longest_match && match) + break; + else /* (fl_longest_match && match) || (!fl_search && !match) */ + { + if (mctx->state_log == NULL) + break; + else + { + int max = mctx->state_log_top; + for (; cur_str_idx <= max; ++cur_str_idx) + if (mctx->state_log[cur_str_idx] != NULL) + break; + if (cur_str_idx > max) + break; + } + } + } if (cur_state != NULL && cur_state->halt) - { - /* Reached at a halt state. - Check the halt state can satisfy the current context. */ - if (!cur_state->has_constraint - || check_halt_state_context (preg, cur_state, mctx, - re_string_cur_idx (mctx->input))) - { - /* We found an appropriate halt state. */ - match_last = re_string_cur_idx (mctx->input); - match = 1; - if (!fl_longest_match) - break; - } - } + { + /* Reached at a halt state. + Check the halt state can satisfy the current context. */ + if (!cur_state->has_constraint + || check_halt_state_context (preg, cur_state, mctx, + re_string_cur_idx (mctx->input))) + { + /* We found an appropriate halt state. */ + match_last = re_string_cur_idx (mctx->input); + match = 1; + if (!fl_longest_match) + break; + } + } } return match_last; } @@ -1054,7 +1054,7 @@ check_halt_state_context (preg, state, mctx, idx) assert (state->halt); #endif context = re_string_context_at (mctx->input, idx, mctx->eflags, - preg->newline_anchor); + preg->newline_anchor); for (i = 0; i < state->nodes.nelem; ++i) if (check_halt_node_context (dfa, state->nodes.elems[i], context)) return state->nodes.elems[i]; @@ -1084,24 +1084,24 @@ proceed_next_node (preg, nregs, regs, mctx, pidx, node, eps_via_nodes, fs) int ndest, dest_nodes[2]; err = re_node_set_insert (eps_via_nodes, node); if (BE (err < 0, 0)) - return -1; + return -1; /* Pick up valid destinations. */ for (ndest = 0, i = 0; i < dfa->edests[node].nelem; ++i) - { - int candidate = dfa->edests[node].elems[i]; - if (!re_node_set_contains (cur_nodes, candidate)) - continue; - dest_nodes[0] = (ndest == 0) ? candidate : dest_nodes[0]; - dest_nodes[1] = (ndest == 1) ? candidate : dest_nodes[1]; - ++ndest; - } + { + int candidate = dfa->edests[node].elems[i]; + if (!re_node_set_contains (cur_nodes, candidate)) + continue; + dest_nodes[0] = (ndest == 0) ? candidate : dest_nodes[0]; + dest_nodes[1] = (ndest == 1) ? candidate : dest_nodes[1]; + ++ndest; + } if (ndest <= 1) - return ndest == 0 ? -1 : (ndest == 1 ? dest_nodes[0] : 0); + return ndest == 0 ? -1 : (ndest == 1 ? dest_nodes[0] : 0); /* In order to avoid infinite loop like "(a*)*". */ if (re_node_set_contains (eps_via_nodes, dest_nodes[0])) - return dest_nodes[1]; + return dest_nodes[1]; if (fs != NULL) - push_fail_stack (fs, *pidx, dest_nodes, nregs, regs, eps_via_nodes); + push_fail_stack (fs, *pidx, dest_nodes, nregs, regs, eps_via_nodes); return dest_nodes[0]; } else @@ -1111,50 +1111,50 @@ proceed_next_node (preg, nregs, regs, mctx, pidx, node, eps_via_nodes, fs) #ifdef RE_ENABLE_I18N if (ACCEPT_MB_NODE (type)) - naccepted = check_node_accept_bytes (preg, node, mctx->input, *pidx); + naccepted = check_node_accept_bytes (preg, node, mctx->input, *pidx); else #endif /* RE_ENABLE_I18N */ if (type == OP_BACK_REF) - { - int subexp_idx = dfa->nodes[node].opr.idx; - 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; - else if (naccepted) - { - char *buf = re_string_get_buffer (mctx->input); - if (strncmp (buf + regs[subexp_idx].rm_so, buf + *pidx, - naccepted) != 0) - return -1; - } - } - - if (naccepted == 0) - { - err = re_node_set_insert (eps_via_nodes, node); - if (BE (err < 0, 0)) - return -2; - dest_node = dfa->edests[node].elems[0]; - if (re_node_set_contains (&mctx->state_log[*pidx]->nodes, - dest_node)) - return dest_node; - } - } + { + int subexp_idx = dfa->nodes[node].opr.idx; + 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; + else if (naccepted) + { + char *buf = re_string_get_buffer (mctx->input); + if (strncmp (buf + regs[subexp_idx].rm_so, buf + *pidx, + naccepted) != 0) + return -1; + } + } + + if (naccepted == 0) + { + err = re_node_set_insert (eps_via_nodes, node); + if (BE (err < 0, 0)) + return -2; + dest_node = dfa->edests[node].elems[0]; + if (re_node_set_contains (&mctx->state_log[*pidx]->nodes, + dest_node)) + return dest_node; + } + } if (naccepted != 0 - || check_node_accept (preg, dfa->nodes + node, mctx, *pidx)) - { - 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; - re_node_set_empty (eps_via_nodes); - return dest_node; - } + || check_node_accept (preg, dfa->nodes + node, mctx, *pidx)) + { + 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; + re_node_set_empty (eps_via_nodes); + return dest_node; + } } return -1; } @@ -1173,9 +1173,9 @@ push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes) struct re_fail_stack_ent_t *new_array; fs->alloc *= 2; new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t) - * fs->alloc)); + * fs->alloc)); if (new_array == NULL) - return REG_ESPACE; + return REG_ESPACE; fs->stack = new_array; } fs->stack[num].idx = str_idx; @@ -1239,45 +1239,45 @@ set_regs (preg, mctx, nmatch, pmatch, fl_backtrack) { update_regs (dfa, pmatch, cur_node, idx, real_nmatch); if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node) - { - int reg_idx; - if (fs) - { - for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) - if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1) - break; - if (reg_idx == nmatch) - { - re_node_set_free (&eps_via_nodes); - return free_fail_stack_return (fs); - } - cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, - &eps_via_nodes); - } - else - { - re_node_set_free (&eps_via_nodes); - return REG_NOERROR; - } - } + { + int reg_idx; + if (fs) + { + for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) + if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1) + break; + if (reg_idx == nmatch) + { + re_node_set_free (&eps_via_nodes); + return free_fail_stack_return (fs); + } + cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, + &eps_via_nodes); + } + else + { + re_node_set_free (&eps_via_nodes); + return REG_NOERROR; + } + } /* Proceed to next node. */ cur_node = proceed_next_node (preg, nmatch, pmatch, mctx, &idx, cur_node, - &eps_via_nodes, fs); + &eps_via_nodes, fs); if (BE (cur_node < 0, 0)) - { - if (cur_node == -2) - return REG_ESPACE; - if (fs) - cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, - &eps_via_nodes); - else - { - re_node_set_free (&eps_via_nodes); - return REG_NOMATCH; - } - } + { + if (cur_node == -2) + return REG_ESPACE; + if (fs) + cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, + &eps_via_nodes); + else + { + re_node_set_free (&eps_via_nodes); + return REG_NOMATCH; + } + } } re_node_set_free (&eps_via_nodes); return free_fail_stack_return (fs); @@ -1291,10 +1291,10 @@ free_fail_stack_return (fs) { int fs_idx; for (fs_idx = 0; fs_idx < fs->num; ++fs_idx) - { - re_node_set_free (&fs->stack[fs_idx].eps_via_nodes); - re_free (fs->stack[fs_idx].regs); - } + { + re_node_set_free (&fs->stack[fs_idx].eps_via_nodes); + re_free (fs->stack[fs_idx].regs); + } re_free (fs->stack); } return REG_NOERROR; @@ -1332,19 +1332,19 @@ update_regs (dfa, pmatch, cur_node, cur_idx, nmatch) Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if... 1. When STR_IDX == MATCH_LAST(the last index in the state_log): - If `a' isn't the LAST_NODE and `a' can't epsilon transit to - the LAST_NODE, we throw away the node `a'. + If `a' isn't the LAST_NODE and `a' can't epsilon transit to + the LAST_NODE, we throw away the node `a'. 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts - string `s' and transit to `b': - i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw - away the node `a'. - ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is - throwed away, we throw away the node `a'. + string `s' and transit to `b': + i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw + away the node `a'. + ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is + throwed away, we throw away the node `a'. 3. When 0 <= STR_IDX < n and 'a' epsilon transit to 'b': - i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the - node `a'. - ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is throwed away, - we throw away the node `a'. */ + i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the + node `a'. + ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is throwed away, + we throw away the node `a'. */ #define STATE_NODE_CONTAINS(state,node) \ ((state) != NULL && re_node_set_contains (&(state)->nodes, node)) @@ -1383,74 +1383,74 @@ sift_states_backward (preg, mctx, sctx) /* Update counters. */ null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0; if (null_cnt > mctx->max_mb_elem_len) - { - memset (sctx->sifted_states, '\0', - sizeof (re_dfastate_t *) * str_idx); - re_node_set_free (&cur_dest); - return REG_NOERROR; - } + { + memset (sctx->sifted_states, '\0', + sizeof (re_dfastate_t *) * str_idx); + re_node_set_free (&cur_dest); + return REG_NOERROR; + } re_node_set_empty (&cur_dest); --str_idx; cur_src = ((mctx->state_log[str_idx] == NULL) ? &empty_set - : &mctx->state_log[str_idx]->nodes); + : &mctx->state_log[str_idx]->nodes); /* Then build the next sifted state. - We build the next sifted state on `cur_dest', and update - `sifted_states[str_idx]' with `cur_dest'. - Note: - `cur_dest' is the sifted state from `state_log[str_idx + 1]'. - `cur_src' points the node_set of the old `state_log[str_idx]'. */ + We build the next sifted state on `cur_dest', and update + `sifted_states[str_idx]' with `cur_dest'. + Note: + `cur_dest' is the sifted state from `state_log[str_idx + 1]'. + `cur_src' points the node_set of the old `state_log[str_idx]'. */ for (i = 0; i < cur_src->nelem; i++) - { - int prev_node = cur_src->elems[i]; - int naccepted = 0; - re_token_type_t type = dfa->nodes[prev_node].type; + { + int prev_node = cur_src->elems[i]; + int naccepted = 0; + re_token_type_t type = dfa->nodes[prev_node].type; - if (IS_EPSILON_NODE(type)) - continue; + if (IS_EPSILON_NODE(type)) + continue; #ifdef RE_ENABLE_I18N - /* If the node may accept `multi byte'. */ - if (ACCEPT_MB_NODE (type)) - naccepted = sift_states_iter_mb (preg, mctx, sctx, prev_node, - str_idx, sctx->last_str_idx); + /* If the node may accept `multi byte'. */ + if (ACCEPT_MB_NODE (type)) + naccepted = sift_states_iter_mb (preg, mctx, sctx, prev_node, + str_idx, sctx->last_str_idx); #endif /* RE_ENABLE_I18N */ - /* We don't check backreferences here. - See update_cur_sifted_state(). */ - - if (!naccepted - && check_node_accept (preg, dfa->nodes + prev_node, mctx, - str_idx) - && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1], - dfa->nexts[prev_node])) - naccepted = 1; - - if (naccepted == 0) - continue; - - if (sctx->limits.nelem) - { - int to_idx = str_idx + naccepted; - if (check_dst_limits (dfa, &sctx->limits, mctx, - 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)) - { - err = REG_ESPACE; - goto free_return; - } - } + /* We don't check backreferences here. + See update_cur_sifted_state(). */ + + if (!naccepted + && check_node_accept (preg, dfa->nodes + prev_node, mctx, + str_idx) + && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1], + dfa->nexts[prev_node])) + naccepted = 1; + + if (naccepted == 0) + continue; + + if (sctx->limits.nelem) + { + int to_idx = str_idx + naccepted; + if (check_dst_limits (dfa, &sctx->limits, mctx, + 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)) + { + err = REG_ESPACE; + goto free_return; + } + } /* Add all the nodes which satisfy the following conditions: - - It can epsilon transit to a node in CUR_DEST. - - It is in CUR_SRC. - And update state_log. */ + - It can epsilon transit to a node in CUR_DEST. + - It is in CUR_SRC. + And update state_log. */ err = update_cur_sifted_state (preg, mctx, sctx, str_idx, &cur_dest); if (BE (err != REG_NOERROR, 0)) - goto free_return; + goto free_return; } err = REG_NOERROR; free_return: @@ -1469,18 +1469,18 @@ clean_state_log_if_need (mctx, next_state_log_idx) if (next_state_log_idx >= mctx->input->bufs_len || (next_state_log_idx >= mctx->input->valid_len - && mctx->input->valid_len < mctx->input->len)) + && mctx->input->valid_len < mctx->input->len)) { reg_errcode_t err; err = extend_buffers (mctx); if (BE (err != REG_NOERROR, 0)) - return err; + return err; } if (top < next_state_log_idx) { memset (mctx->state_log + top + 1, '\0', - sizeof (re_dfastate_t *) * (next_state_log_idx - top)); + sizeof (re_dfastate_t *) * (next_state_log_idx - top)); mctx->state_log_top = next_state_log_idx; } return REG_NOERROR; @@ -1498,19 +1498,19 @@ merge_state_array (dfa, dst, src, num) for (st_idx = 0; st_idx < num; ++st_idx) { if (dst[st_idx] == NULL) - dst[st_idx] = src[st_idx]; + dst[st_idx] = src[st_idx]; else if (src[st_idx] != NULL) - { - re_node_set merged_set; - err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes, - &src[st_idx]->nodes); - if (BE (err != REG_NOERROR, 0)) - return err; - dst[st_idx] = re_acquire_state (&err, dfa, &merged_set); - re_node_set_free (&merged_set); - if (BE (err != REG_NOERROR, 0)) - return err; - } + { + re_node_set merged_set; + err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes, + &src[st_idx]->nodes); + if (BE (err != REG_NOERROR, 0)) + return err; + dst[st_idx] = re_acquire_state (&err, dfa, &merged_set); + re_node_set_free (&merged_set); + if (BE (err != REG_NOERROR, 0)) + return err; + } } return REG_NOERROR; } @@ -1527,7 +1527,7 @@ update_cur_sifted_state (preg, mctx, sctx, str_idx, dest_nodes) re_dfa_t *dfa = (re_dfa_t *)preg->buffer; const re_node_set *candidates; candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set - : &mctx->state_log[str_idx]->nodes); + : &mctx->state_log[str_idx]->nodes); /* At first, add the nodes which can epsilon transit to a node in DEST_NODE. */ @@ -1542,9 +1542,9 @@ update_cur_sifted_state (preg, mctx, sctx, str_idx, dest_nodes) if (dest_nodes->nelem && sctx->limits.nelem) { err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits, - mctx->bkref_ents, str_idx); + mctx->bkref_ents, str_idx); if (BE (err != REG_NOERROR, 0)) - return err; + return err; } /* Update state_log. */ @@ -1558,7 +1558,7 @@ update_cur_sifted_state (preg, mctx, sctx, str_idx, dest_nodes) { err = search_subexp (preg, mctx, sctx, str_idx, dest_nodes); if (BE (err != REG_NOERROR, 0)) - return err; + return err; } if ((mctx->state_log[str_idx] != NULL @@ -1566,7 +1566,7 @@ update_cur_sifted_state (preg, mctx, sctx, str_idx, dest_nodes) { err = sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes); if (BE (err != REG_NOERROR, 0)) - return err; + return err; } return REG_NOERROR; } @@ -1587,13 +1587,13 @@ add_epsilon_src_nodes (dfa, dest_nodes, candidates) for (src_idx = 0; src_idx < src_copy.nelem; ++src_idx) { err = re_node_set_add_intersect (dest_nodes, candidates, - dfa->inveclosures - + src_copy.elems[src_idx]); + dfa->inveclosures + + src_copy.elems[src_idx]); if (BE (err != REG_NOERROR, 0)) - { - re_node_set_free (&src_copy); - return err; - } + { + re_node_set_free (&src_copy); + return err; + } } re_node_set_free (&src_copy); return REG_NOERROR; @@ -1613,38 +1613,38 @@ sub_epsilon_src_nodes (dfa, node, dest_nodes, candidates) 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]; - 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); - if ((!re_node_set_contains (inv_eclosure, edst1) - && re_node_set_contains (dest_nodes, edst1)) - || (edst2 > 0 - && !re_node_set_contains (inv_eclosure, edst2) - && re_node_set_contains (dest_nodes, edst2))) - { - err = re_node_set_add_intersect (&except_nodes, candidates, - dfa->inveclosures + cur_node); - if (BE (err != REG_NOERROR, 0)) - { - re_node_set_free (&except_nodes); - return err; - } - } - } + int 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); + if ((!re_node_set_contains (inv_eclosure, edst1) + && re_node_set_contains (dest_nodes, edst1)) + || (edst2 > 0 + && !re_node_set_contains (inv_eclosure, edst2) + && re_node_set_contains (dest_nodes, edst2))) + { + err = re_node_set_add_intersect (&except_nodes, candidates, + dfa->inveclosures + cur_node); + if (BE (err != REG_NOERROR, 0)) + { + re_node_set_free (&except_nodes); + return err; + } + } + } } for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx) { - int 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; - re_node_set_remove_at (dest_nodes, idx); - } + int 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; + re_node_set_remove_at (dest_nodes, idx); + } } re_node_set_free (&except_nodes); return REG_NOERROR; @@ -1667,27 +1667,27 @@ check_dst_limits (dfa, limits, mctx, dst_node, dst_idx, src_node, src_idx) subexp_idx = dfa->nodes[ent->node].opr.idx - 1; dst_pos = check_dst_limits_calc_pos (dfa, mctx, limits->elems[lim_idx], - dfa->eclosures + dst_node, - subexp_idx, dst_node, dst_idx); + dfa->eclosures + dst_node, + subexp_idx, dst_node, dst_idx); src_pos = check_dst_limits_calc_pos (dfa, mctx, limits->elems[lim_idx], - dfa->eclosures + src_node, - subexp_idx, src_node, src_idx); + dfa->eclosures + src_node, + subexp_idx, src_node, src_idx); /* In case of: - <src> <dst> ( <subexp> ) - ( <subexp> ) <src> <dst> - ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */ + <src> <dst> ( <subexp> ) + ( <subexp> ) <src> <dst> + ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */ if (src_pos == dst_pos) - continue; /* This is unrelated limitation. */ + continue; /* This is unrelated limitation. */ else - return 1; + return 1; } return 0; } static int check_dst_limits_calc_pos (dfa, mctx, limit, eclosures, subexp_idx, node, - str_idx) + str_idx) re_dfa_t *dfa; re_match_context_t *mctx; re_node_set *eclosures; @@ -1695,48 +1695,48 @@ check_dst_limits_calc_pos (dfa, mctx, limit, eclosures, subexp_idx, node, { struct re_backref_cache_entry *lim = mctx->bkref_ents + limit; int pos = (str_idx < lim->subexp_from ? -1 - : (lim->subexp_to < str_idx ? 1 : 0)); + : (lim->subexp_to < str_idx ? 1 : 0)); if (pos == 0 && (str_idx == lim->subexp_from || str_idx == lim->subexp_to)) { int node_idx; for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx) - { - int node = eclosures->elems[node_idx]; - re_token_type_t type= dfa->nodes[node].type; - if (type == OP_BACK_REF) - { - int bi; - for (bi = 0; bi < mctx->nbkref_ents; ++bi) - { - struct re_backref_cache_entry *ent = mctx->bkref_ents + bi; - if (ent->node == node && ent->subexp_from == ent->subexp_to - && ent->str_idx == str_idx) - { - int cpos, dst; - dst = dfa->edests[node].elems[0]; - cpos = check_dst_limits_calc_pos (dfa, mctx, limit, - dfa->eclosures + dst, - subexp_idx, dst, - str_idx); - if ((str_idx == lim->subexp_from && cpos == -1) - || (str_idx == lim->subexp_to && cpos == 0)) - return cpos; - } - } - } - if (type == OP_OPEN_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx - && str_idx == lim->subexp_from) - { - pos = -1; - break; - } - if (type == OP_CLOSE_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx - && str_idx == lim->subexp_to) - break; - } + { + int node = eclosures->elems[node_idx]; + re_token_type_t type= dfa->nodes[node].type; + if (type == OP_BACK_REF) + { + int bi; + for (bi = 0; bi < mctx->nbkref_ents; ++bi) + { + struct re_backref_cache_entry *ent = mctx->bkref_ents + bi; + if (ent->node == node && ent->subexp_from == ent->subexp_to + && ent->str_idx == str_idx) + { + int cpos, dst; + dst = dfa->edests[node].elems[0]; + cpos = check_dst_limits_calc_pos (dfa, mctx, limit, + dfa->eclosures + dst, + subexp_idx, dst, + str_idx); + if ((str_idx == lim->subexp_from && cpos == -1) + || (str_idx == lim->subexp_to && cpos == 0)) + return cpos; + } + } + } + if (type == OP_OPEN_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx + && str_idx == lim->subexp_from) + { + pos = -1; + break; + } + if (type == OP_CLOSE_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx + && str_idx == lim->subexp_to) + break; + } if (node_idx == eclosures->nelem && str_idx == lim->subexp_to) - pos = 1; + pos = 1; } return pos; } @@ -1763,74 +1763,74 @@ check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx) ent = bkref_ents + limits->elems[lim_idx]; if (str_idx <= ent->subexp_from || ent->str_idx < str_idx) - continue; /* This is unrelated limitation. */ + continue; /* This is unrelated limitation. */ subexp_idx = dfa->nodes[ent->node].opr.idx - 1; if (ent->subexp_to == str_idx) - { - int ops_node = -1; - int cls_node = -1; - for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) - { - int 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) - ops_node = node; - else if (type == OP_CLOSE_SUBEXP - && subexp_idx == dfa->nodes[node].opr.idx) - cls_node = node; - } - - /* Check the limitation of the open subexpression. */ - /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */ - if (ops_node >= 0) - { - err = sub_epsilon_src_nodes(dfa, ops_node, dest_nodes, - candidates); - if (BE (err != REG_NOERROR, 0)) - return err; - } - /* Check the limitation of the close subexpression. */ - for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) - { - int node = dest_nodes->elems[node_idx]; - if (!re_node_set_contains (dfa->inveclosures + node, cls_node) - && !re_node_set_contains (dfa->eclosures + node, cls_node)) - { - /* 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; - --node_idx; - } - } - } + { + int ops_node = -1; + int cls_node = -1; + for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) + { + int 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) + ops_node = node; + else if (type == OP_CLOSE_SUBEXP + && subexp_idx == dfa->nodes[node].opr.idx) + cls_node = node; + } + + /* Check the limitation of the open subexpression. */ + /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */ + if (ops_node >= 0) + { + err = sub_epsilon_src_nodes(dfa, ops_node, dest_nodes, + candidates); + if (BE (err != REG_NOERROR, 0)) + return err; + } + /* Check the limitation of the close subexpression. */ + for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) + { + int node = dest_nodes->elems[node_idx]; + if (!re_node_set_contains (dfa->inveclosures + node, cls_node) + && !re_node_set_contains (dfa->eclosures + node, cls_node)) + { + /* 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; + --node_idx; + } + } + } else /* (ent->subexp_to != str_idx) */ - { - for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) - { - int node = dest_nodes->elems[node_idx]; - re_token_type_t type= dfa->nodes[node].type; - if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP) - { - 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; - } - } - } - } + { + for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) + { + int node = dest_nodes->elems[node_idx]; + re_token_type_t type= dfa->nodes[node].type; + if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP) + { + 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; + } + } + } + } } return REG_NOERROR; } @@ -1854,7 +1854,7 @@ search_subexp (preg, mctx, sctx, str_idx, dest_nodes) const re_node_set *candidates; re_dfastate_t **lim_states = NULL; candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set - : &mctx->state_log[str_idx]->nodes); + : &mctx->state_log[str_idx]->nodes); local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */ for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) @@ -1864,104 +1864,104 @@ search_subexp (preg, mctx, sctx, str_idx, dest_nodes) type = dfa->nodes[node].type; if (type == OP_CLOSE_SUBEXP - && sctx->check_subexp == dfa->nodes[node].opr.idx + 1) - { - re_dfastate_t *cur_state; - /* Found the bottom of the subexpression, then search for the - top of it. */ - if (local_sctx.sifted_states == NULL) - { - /* It hasn't been initialized yet, initialize it now. */ - local_sctx = *sctx; - err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - local_sctx.check_subexp = -sctx->check_subexp; - local_sctx.limited_states = sctx->limited_states; - local_sctx.last_node = node; - local_sctx.last_str_idx = local_sctx.cls_subexp_idx = str_idx; - cur_state = local_sctx.sifted_states[str_idx]; - err = sift_states_backward (preg, mctx, &local_sctx); - local_sctx.sifted_states[str_idx] = cur_state; - if (BE (err != REG_NOERROR, 0)) - goto free_return; - /* There must not 2 same node in a node set. */ - break; - } + && sctx->check_subexp == dfa->nodes[node].opr.idx + 1) + { + re_dfastate_t *cur_state; + /* Found the bottom of the subexpression, then search for the + top of it. */ + if (local_sctx.sifted_states == NULL) + { + /* It hasn't been initialized yet, initialize it now. */ + local_sctx = *sctx; + err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + local_sctx.check_subexp = -sctx->check_subexp; + local_sctx.limited_states = sctx->limited_states; + local_sctx.last_node = node; + local_sctx.last_str_idx = local_sctx.cls_subexp_idx = str_idx; + cur_state = local_sctx.sifted_states[str_idx]; + err = sift_states_backward (preg, mctx, &local_sctx); + local_sctx.sifted_states[str_idx] = cur_state; + if (BE (err != REG_NOERROR, 0)) + goto free_return; + /* There must not 2 same node in a node set. */ + break; + } else if (type == OP_OPEN_SUBEXP - && -sctx->check_subexp == dfa->nodes[node].opr.idx + 1) - { - /* Found the top of the subexpression, check that the - backreference can match the input string. */ - char *buf; - int dest_str_idx; - int bkref_str_idx = re_string_cur_idx (mctx->input); - int subexp_len = sctx->cls_subexp_idx - str_idx; - if (subexp_len < 0 || bkref_str_idx + subexp_len > mctx->input->len) - break; - - if (bkref_str_idx + subexp_len > mctx->input->valid_len - && mctx->input->valid_len < mctx->input->len) - { - reg_errcode_t err; - err = extend_buffers (mctx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - buf = (char *) re_string_get_buffer (mctx->input); - if (strncmp (buf + str_idx, buf + bkref_str_idx, subexp_len) != 0) - break; - - if (sctx->limits.nelem && str_idx > 0) - { - re_dfastate_t *cur_state = sctx->sifted_states[str_idx]; - if (lim_states == NULL) - { - lim_states = re_malloc (re_dfastate_t *, str_idx + 1); - if (BE (lim_states == NULL, 0)) - { - err = REG_ESPACE; - goto free_return; - } - } - if (local_sctx.sifted_states == NULL) - { - /* It hasn't been initialized yet, initialize it now. */ - local_sctx = *sctx; - err = re_node_set_init_copy (&local_sctx.limits, - &sctx->limits); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - local_sctx.check_subexp = 0; - local_sctx.last_node = node; - local_sctx.last_str_idx = str_idx; - local_sctx.limited_states = lim_states; - memset (lim_states, '\0', - sizeof (re_dfastate_t*) * (str_idx + 1)); - err = sift_states_backward (preg, mctx, &local_sctx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - if (local_sctx.sifted_states[0] == NULL - && local_sctx.limited_states[0] == NULL) - { - sctx->sifted_states[str_idx] = cur_state; - break; - } - sctx->sifted_states[str_idx] = cur_state; - } - /* Successfully matched, add a new cache entry. */ - dest_str_idx = bkref_str_idx + subexp_len; - err = match_ctx_add_entry (mctx, sctx->cur_bkref, bkref_str_idx, - str_idx, sctx->cls_subexp_idx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - err = clean_state_log_if_need (mctx, dest_str_idx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - break; - } + && -sctx->check_subexp == dfa->nodes[node].opr.idx + 1) + { + /* Found the top of the subexpression, check that the + backreference can match the input string. */ + char *buf; + int dest_str_idx; + int bkref_str_idx = re_string_cur_idx (mctx->input); + int subexp_len = sctx->cls_subexp_idx - str_idx; + if (subexp_len < 0 || bkref_str_idx + subexp_len > mctx->input->len) + break; + + if (bkref_str_idx + subexp_len > mctx->input->valid_len + && mctx->input->valid_len < mctx->input->len) + { + reg_errcode_t err; + err = extend_buffers (mctx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + buf = (char *) re_string_get_buffer (mctx->input); + if (strncmp (buf + str_idx, buf + bkref_str_idx, subexp_len) != 0) + break; + + if (sctx->limits.nelem && str_idx > 0) + { + re_dfastate_t *cur_state = sctx->sifted_states[str_idx]; + if (lim_states == NULL) + { + lim_states = re_malloc (re_dfastate_t *, str_idx + 1); + if (BE (lim_states == NULL, 0)) + { + err = REG_ESPACE; + goto free_return; + } + } + if (local_sctx.sifted_states == NULL) + { + /* It hasn't been initialized yet, initialize it now. */ + local_sctx = *sctx; + err = re_node_set_init_copy (&local_sctx.limits, + &sctx->limits); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + local_sctx.check_subexp = 0; + local_sctx.last_node = node; + local_sctx.last_str_idx = str_idx; + local_sctx.limited_states = lim_states; + memset (lim_states, '\0', + sizeof (re_dfastate_t*) * (str_idx + 1)); + err = sift_states_backward (preg, mctx, &local_sctx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + if (local_sctx.sifted_states[0] == NULL + && local_sctx.limited_states[0] == NULL) + { + sctx->sifted_states[str_idx] = cur_state; + break; + } + sctx->sifted_states[str_idx] = cur_state; + } + /* Successfully matched, add a new cache entry. */ + dest_str_idx = bkref_str_idx + subexp_len; + err = match_ctx_add_entry (mctx, sctx->cur_bkref, bkref_str_idx, + str_idx, sctx->cls_subexp_idx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + err = clean_state_log_if_need (mctx, dest_str_idx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + break; + } } /* Remove the top/bottom of the sub expression we processed. */ @@ -1969,11 +1969,11 @@ search_subexp (preg, mctx, sctx, str_idx, dest_nodes) { err = sub_epsilon_src_nodes(dfa, node, dest_nodes, candidates); if (BE (err != REG_NOERROR, 0)) - goto free_return; + goto free_return; /* Update state_log. */ sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes); if (BE (err != REG_NOERROR, 0)) - goto free_return; + goto free_return; } err = REG_NOERROR; free_return: @@ -1998,7 +1998,7 @@ sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes) re_sift_context_t local_sctx; const re_node_set *candidates; candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set - : &mctx->state_log[str_idx]->nodes); + : &mctx->state_log[str_idx]->nodes); local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */ for (node_idx = 0; node_idx < candidates->nelem; ++node_idx) @@ -2008,107 +2008,107 @@ sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes) node = candidates->elems[node_idx]; type = dfa->nodes[node].type; if (node == sctx->cur_bkref && str_idx == cur_bkref_idx) - continue; + continue; /* Avoid infinite loop for the REs like "()\1+". */ if (node == sctx->last_node && str_idx == sctx->last_str_idx) - continue; + continue; if (type == OP_BACK_REF) - { - int enabled_idx; - for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx) - { - int disabled_idx, subexp_len, to_idx, dst_node; - struct re_backref_cache_entry *entry; - entry = mctx->bkref_ents + enabled_idx; - subexp_len = entry->subexp_to - entry->subexp_from; - to_idx = str_idx + subexp_len; - dst_node = (subexp_len ? dfa->nexts[node] - : dfa->edests[node].elems[0]); - - if (entry->node != node || entry->str_idx != str_idx - || to_idx > sctx->last_str_idx - || sctx->sifted_states[to_idx] == NULL) - continue; - if (!STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)) - continue; - - if (check_dst_limits (dfa, &sctx->limits, mctx, node, - str_idx, dst_node, to_idx)) - continue; - if (sctx->check_subexp == dfa->nodes[node].opr.idx) - { - char *buf; - buf = (char *) re_string_get_buffer (mctx->input); - if (strncmp (buf + entry->subexp_from, - buf + cur_bkref_idx, subexp_len) != 0) - continue; - err = match_ctx_add_entry (mctx, sctx->cur_bkref, - cur_bkref_idx, entry->subexp_from, - entry->subexp_to); - if (BE (err != REG_NOERROR, 0)) + { + int enabled_idx; + for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx) + { + int disabled_idx, subexp_len, to_idx, dst_node; + struct re_backref_cache_entry *entry; + entry = mctx->bkref_ents + enabled_idx; + subexp_len = entry->subexp_to - entry->subexp_from; + to_idx = str_idx + subexp_len; + dst_node = (subexp_len ? dfa->nexts[node] + : dfa->edests[node].elems[0]); + + if (entry->node != node || entry->str_idx != str_idx + || to_idx > sctx->last_str_idx + || sctx->sifted_states[to_idx] == NULL) + continue; + if (!STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)) + continue; + + if (check_dst_limits (dfa, &sctx->limits, mctx, node, + str_idx, dst_node, to_idx)) + continue; + if (sctx->check_subexp == dfa->nodes[node].opr.idx) + { + char *buf; + buf = (char *) re_string_get_buffer (mctx->input); + if (strncmp (buf + entry->subexp_from, + buf + cur_bkref_idx, subexp_len) != 0) + continue; + err = match_ctx_add_entry (mctx, sctx->cur_bkref, + cur_bkref_idx, entry->subexp_from, + entry->subexp_to); + if (BE (err != REG_NOERROR, 0)) goto free_return; - err = clean_state_log_if_need (mctx, cur_bkref_idx - + subexp_len); - if (BE (err != REG_NOERROR, 0)) + err = clean_state_log_if_need (mctx, cur_bkref_idx + + subexp_len); + if (BE (err != REG_NOERROR, 0)) goto free_return; - } - else - { - re_dfastate_t *cur_state; - entry->flag = 0; - for (disabled_idx = enabled_idx + 1; - disabled_idx < mctx->nbkref_ents; ++disabled_idx) - { - struct re_backref_cache_entry *entry2; - entry2 = mctx->bkref_ents + disabled_idx; - if (entry2->node != node || entry2->str_idx != str_idx) - continue; - entry2->flag = 1; - } - - if (local_sctx.sifted_states == NULL) - { - local_sctx = *sctx; - err = re_node_set_init_copy (&local_sctx.limits, - &sctx->limits); - if (BE (err != REG_NOERROR, 0)) + } + else + { + re_dfastate_t *cur_state; + entry->flag = 0; + for (disabled_idx = enabled_idx + 1; + disabled_idx < mctx->nbkref_ents; ++disabled_idx) + { + struct re_backref_cache_entry *entry2; + entry2 = mctx->bkref_ents + disabled_idx; + if (entry2->node != node || entry2->str_idx != str_idx) + continue; + entry2->flag = 1; + } + + if (local_sctx.sifted_states == NULL) + { + local_sctx = *sctx; + err = re_node_set_init_copy (&local_sctx.limits, + &sctx->limits); + if (BE (err != REG_NOERROR, 0)) goto free_return; - } - 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)) + } + 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)) { err = REG_ESPACE; goto free_return; } - cur_state = local_sctx.sifted_states[str_idx]; - err = sift_states_backward (preg, mctx, &local_sctx); - if (BE (err != REG_NOERROR, 0)) + cur_state = local_sctx.sifted_states[str_idx]; + err = sift_states_backward (preg, mctx, &local_sctx); + if (BE (err != REG_NOERROR, 0)) goto free_return; - if (sctx->limited_states != NULL) - { - err = merge_state_array (dfa, sctx->limited_states, - local_sctx.sifted_states, - str_idx + 1); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - local_sctx.sifted_states[str_idx] = cur_state; - re_node_set_remove (&local_sctx.limits, enabled_idx); + if (sctx->limited_states != NULL) + { + err = merge_state_array (dfa, sctx->limited_states, + local_sctx.sifted_states, + str_idx + 1); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + local_sctx.sifted_states[str_idx] = cur_state; + re_node_set_remove (&local_sctx.limits, enabled_idx); /* We must not use the variable entry here, since mctx->bkref_ents might be realloced. */ mctx->bkref_ents[enabled_idx].flag = 1; - } - } - for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx) - { - struct re_backref_cache_entry *entry; - entry = mctx->bkref_ents + enabled_idx; - if (entry->node == node && entry->str_idx == str_idx) - entry->flag = 0; - } - } + } + } + for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx) + { + struct re_backref_cache_entry *entry; + entry = mctx->bkref_ents + enabled_idx; + if (entry->node == node && entry->str_idx == str_idx) + entry->flag = 0; + } + } } err = REG_NOERROR; free_return: @@ -2135,7 +2135,7 @@ sift_states_iter_mb (preg, mctx, sctx, node_idx, str_idx, max_str_idx) naccepted = check_node_accept_bytes (preg, node_idx, mctx->input, str_idx); if (naccepted > 0 && str_idx + naccepted <= max_str_idx && !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted], - dfa->nexts[node_idx])) + dfa->nexts[node_idx])) /* The node can't accept the `multi byte', or the destination was already throwed away, then the node could't accept the current input `multi byte'. */ @@ -2168,11 +2168,11 @@ transit_state (err, preg, mctx, state, fl_search) if (re_string_cur_idx (mctx->input) + 1 >= mctx->input->bufs_len || (re_string_cur_idx (mctx->input) + 1 >= mctx->input->valid_len - && mctx->input->valid_len < mctx->input->len)) + && mctx->input->valid_len < mctx->input->len)) { *err = extend_buffers (mctx); if (BE (*err != REG_NOERROR, 0)) - return NULL; + return NULL; } *err = REG_NOERROR; @@ -2186,36 +2186,36 @@ transit_state (err, preg, mctx, state, fl_search) #ifdef RE_ENABLE_I18N /* If the current state can accept multibyte. */ if (state->accept_mb) - { - *err = transit_state_mb (preg, state, mctx); - if (BE (*err != REG_NOERROR, 0)) - return NULL; - } + { + *err = transit_state_mb (preg, state, mctx); + if (BE (*err != REG_NOERROR, 0)) + return NULL; + } #endif /* RE_ENABLE_I18N */ /* Then decide the next state with the single byte. */ if (1) - { - /* Use transition table */ - ch = re_string_fetch_byte (mctx->input); - trtable = fl_search ? state->trtable_search : state->trtable; - if (trtable == NULL) - { - trtable = build_trtable (preg, state, fl_search); - if (fl_search) - state->trtable_search = trtable; - else - state->trtable = trtable; - } - next_state = trtable[ch]; - } + { + /* Use transition table */ + ch = re_string_fetch_byte (mctx->input); + trtable = fl_search ? state->trtable_search : state->trtable; + if (trtable == NULL) + { + trtable = build_trtable (preg, state, fl_search); + if (fl_search) + state->trtable_search = trtable; + else + state->trtable = trtable; + } + next_state = trtable[ch]; + } else - { - /* don't use transition table */ - next_state = transit_state_sb (err, preg, state, fl_search, mctx); - if (BE (next_state == NULL && err != REG_NOERROR, 0)) - return NULL; - } + { + /* don't use transition table */ + next_state = transit_state_sb (err, preg, state, fl_search, mctx); + if (BE (next_state == NULL && err != REG_NOERROR, 0)) + return NULL; + } } /* Update the state_log if we need. */ @@ -2223,57 +2223,57 @@ transit_state (err, preg, mctx, state, fl_search) { int cur_idx = re_string_cur_idx (mctx->input); if (cur_idx > mctx->state_log_top) - { - mctx->state_log[cur_idx] = next_state; - mctx->state_log_top = cur_idx; - } + { + mctx->state_log[cur_idx] = next_state; + mctx->state_log_top = cur_idx; + } else if (mctx->state_log[cur_idx] == 0) - { - mctx->state_log[cur_idx] = next_state; - } + { + mctx->state_log[cur_idx] = next_state; + } else - { - re_dfastate_t *pstate; - 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. */ - 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, - log_nodes); - if (BE (*err != REG_NOERROR, 0)) - return NULL; - } - else - next_nodes = *log_nodes; - /* Note: We already add the nodes of the initial state, - then we don't need to add them here. */ - - context = re_string_context_at (mctx->input, - re_string_cur_idx (mctx->input) - 1, - mctx->eflags, preg->newline_anchor); - next_state = mctx->state_log[cur_idx] - = 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. */ - - if (table_nodes != NULL) - re_node_set_free (&next_nodes); - } + { + re_dfastate_t *pstate; + 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. */ + 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, + log_nodes); + if (BE (*err != REG_NOERROR, 0)) + return NULL; + } + else + next_nodes = *log_nodes; + /* Note: We already add the nodes of the initial state, + then we don't need to add them here. */ + + context = re_string_context_at (mctx->input, + re_string_cur_idx (mctx->input) - 1, + mctx->eflags, preg->newline_anchor); + next_state = mctx->state_log[cur_idx] + = 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. */ + + if (table_nodes != NULL) + re_node_set_free (&next_nodes); + } /* If the next state has back references. */ if (next_state != NULL && next_state->has_backref) - { - *err = transit_state_bkref (preg, next_state, mctx); - if (BE (*err != REG_NOERROR, 0)) - return NULL; - next_state = mctx->state_log[cur_idx]; - } + { + *err = transit_state_bkref (preg, next_state, mctx); + if (BE (*err != REG_NOERROR, 0)) + return NULL; + next_state = mctx->state_log[cur_idx]; + } } return next_state; } @@ -2304,41 +2304,41 @@ transit_state_sb (err, preg, state, fl_search, mctx) { int cur_node = state->nodes.elems[node_cnt]; if (check_node_accept (preg, dfa->nodes + cur_node, mctx, cur_str_idx)) - { - *err = re_node_set_merge (&next_nodes, - dfa->eclosures + dfa->nexts[cur_node]); - if (BE (*err != REG_NOERROR, 0)) - { - re_node_set_free (&next_nodes); - return NULL; - } - } + { + *err = re_node_set_merge (&next_nodes, + dfa->eclosures + dfa->nexts[cur_node]); + if (BE (*err != REG_NOERROR, 0)) + { + re_node_set_free (&next_nodes); + return NULL; + } + } } if (fl_search) { #ifdef RE_ENABLE_I18N int not_initial = 0; if (MB_CUR_MAX > 1) - for (node_cnt = 0; node_cnt < next_nodes.nelem; ++node_cnt) - if (dfa->nodes[next_nodes.elems[node_cnt]].type == CHARACTER) - { - not_initial = dfa->nodes[next_nodes.elems[node_cnt]].mb_partial; - break; - } + for (node_cnt = 0; node_cnt < next_nodes.nelem; ++node_cnt) + if (dfa->nodes[next_nodes.elems[node_cnt]].type == CHARACTER) + { + not_initial = dfa->nodes[next_nodes.elems[node_cnt]].mb_partial; + break; + } if (!not_initial) #endif - { - *err = re_node_set_merge (&next_nodes, - dfa->init_state->entrance_nodes); - if (BE (*err != REG_NOERROR, 0)) - { - re_node_set_free (&next_nodes); - return NULL; - } - } + { + *err = re_node_set_merge (&next_nodes, + dfa->init_state->entrance_nodes); + if (BE (*err != REG_NOERROR, 0)) + { + re_node_set_free (&next_nodes); + return NULL; + } + } } context = re_string_context_at (mctx->input, cur_str_idx, mctx->eflags, - preg->newline_anchor); + preg->newline_anchor); next_state = 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. */ @@ -2368,54 +2368,54 @@ transit_state_mb (preg, pstate, mctx) re_dfastate_t *dest_state; if (dfa->nodes[cur_node_idx].constraint) - { - context = re_string_context_at (mctx->input, - re_string_cur_idx (mctx->input), - mctx->eflags, preg->newline_anchor); - if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint, - context)) - continue; - } + { + context = re_string_context_at (mctx->input, + re_string_cur_idx (mctx->input), + mctx->eflags, preg->newline_anchor); + if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint, + context)) + continue; + } /* How many bytes the node can accepts? */ if (ACCEPT_MB_NODE (dfa->nodes[cur_node_idx].type)) - naccepted = check_node_accept_bytes (preg, cur_node_idx, mctx->input, - re_string_cur_idx (mctx->input)); + naccepted = check_node_accept_bytes (preg, cur_node_idx, mctx->input, + re_string_cur_idx (mctx->input)); if (naccepted == 0) - continue; + continue; /* The node can accepts `naccepted' bytes. */ dest_idx = re_string_cur_idx (mctx->input) + naccepted; mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted - : mctx->max_mb_elem_len); + : mctx->max_mb_elem_len); err = clean_state_log_if_need (mctx, dest_idx); if (BE (err != REG_NOERROR, 0)) - return err; + return err; #ifdef DEBUG assert (dfa->nexts[cur_node_idx] != -1); #endif /* `cur_node_idx' may point the entity of the OP_CONTEXT_NODE, - then we use pstate->nodes.elems[i] instead. */ + then we use pstate->nodes.elems[i] instead. */ new_nodes = dfa->eclosures + dfa->nexts[pstate->nodes.elems[i]]; dest_state = mctx->state_log[dest_idx]; if (dest_state == NULL) - dest_nodes = *new_nodes; + dest_nodes = *new_nodes; else - { - err = re_node_set_init_union (&dest_nodes, - dest_state->entrance_nodes, new_nodes); - if (BE (err != REG_NOERROR, 0)) - return err; - } + { + err = re_node_set_init_union (&dest_nodes, + dest_state->entrance_nodes, new_nodes); + if (BE (err != REG_NOERROR, 0)) + return err; + } context = re_string_context_at (mctx->input, dest_idx - 1, mctx->eflags, - preg->newline_anchor); + preg->newline_anchor); mctx->state_log[dest_idx] - = re_acquire_state_context (&err, dfa, &dest_nodes, context); + = re_acquire_state_context (&err, dfa, &dest_nodes, context); if (dest_state != NULL) - re_node_set_free (&dest_nodes); + re_node_set_free (&dest_nodes); if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0)) - return err; + return err; } return REG_NOERROR; } @@ -2431,7 +2431,7 @@ transit_state_bkref (preg, pstate, mctx) re_dfastate_t **work_state_log; work_state_log = re_malloc (re_dfastate_t *, - re_string_cur_idx (mctx->input) + 1); + re_string_cur_idx (mctx->input) + 1); if (BE (work_state_log == NULL, 0)) return REG_ESPACE; @@ -2468,92 +2468,92 @@ transit_state_bkref_loop (preg, nodes, work_state_log, mctx) /* Check whether `node' is a backreference or not. */ if (node->type == OP_BACK_REF) - subexp_idx = node->opr.idx; + subexp_idx = node->opr.idx; else - continue; + continue; if (node->constraint) - { - context = re_string_context_at (mctx->input, cur_str_idx, - mctx->eflags, preg->newline_anchor); - if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context)) - continue; - } + { + context = re_string_context_at (mctx->input, cur_str_idx, + mctx->eflags, preg->newline_anchor); + if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context)) + continue; + } /* `node' is a backreference. - Check the substring which the substring matched. */ + Check the substring which the substring matched. */ sift_ctx_init (&sctx, work_state_log, NULL, node_idx, cur_str_idx, - subexp_idx); + subexp_idx); sctx.cur_bkref = node_idx; match_ctx_clear_flag (mctx); err = sift_states_backward (preg, mctx, &sctx); if (BE (err != REG_NOERROR, 0)) - goto free_return; + goto free_return; /* And add the epsilon closures (which is `new_dest_nodes') of - the backreference to appropriate state_log. */ + the backreference to appropriate state_log. */ #ifdef DEBUG assert (dfa->nexts[node_idx] != -1); #endif for (bkc_idx = 0; bkc_idx < mctx->nbkref_ents; ++bkc_idx) - { - int subexp_len; - re_dfastate_t *dest_state; - struct re_backref_cache_entry *bkref_ent; - bkref_ent = mctx->bkref_ents + bkc_idx; - if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx) - continue; - subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from; - new_dest_nodes = (subexp_len == 0 - ? dfa->eclosures + dfa->edests[node_idx].elems[0] - : dfa->eclosures + dfa->nexts[node_idx]); - dest_str_idx = (cur_str_idx + bkref_ent->subexp_to - - bkref_ent->subexp_from); - context = (IS_WORD_CHAR (re_string_byte_at (mctx->input, - dest_str_idx - 1)) - ? CONTEXT_WORD : 0); - dest_state = mctx->state_log[dest_str_idx]; - prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0 - : mctx->state_log[cur_str_idx]->nodes.nelem); - /* Add `new_dest_node' to state_log. */ - if (dest_state == NULL) - { - mctx->state_log[dest_str_idx] - = re_acquire_state_context (&err, dfa, new_dest_nodes, - context); - if (BE (mctx->state_log[dest_str_idx] == NULL - && err != REG_NOERROR, 0)) - goto free_return; - } - else - { - re_node_set dest_nodes; - err = re_node_set_init_union (&dest_nodes, - dest_state->entrance_nodes, - new_dest_nodes); - if (BE (err != REG_NOERROR, 0)) - { - re_node_set_free (&dest_nodes); - goto free_return; - } - mctx->state_log[dest_str_idx] - = re_acquire_state_context (&err, dfa, &dest_nodes, context); - re_node_set_free (&dest_nodes); - if (BE (mctx->state_log[dest_str_idx] == NULL - && err != REG_NOERROR, 0)) - goto free_return; - } - /* We need to check recursively if the backreference can epsilon - transit. */ - if (subexp_len == 0 - && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem) - { - err = transit_state_bkref_loop (preg, new_dest_nodes, - work_state_log, mctx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - } + { + int subexp_len; + re_dfastate_t *dest_state; + struct re_backref_cache_entry *bkref_ent; + bkref_ent = mctx->bkref_ents + bkc_idx; + if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx) + continue; + subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from; + new_dest_nodes = (subexp_len == 0 + ? dfa->eclosures + dfa->edests[node_idx].elems[0] + : dfa->eclosures + dfa->nexts[node_idx]); + dest_str_idx = (cur_str_idx + bkref_ent->subexp_to + - bkref_ent->subexp_from); + context = (IS_WORD_CHAR (re_string_byte_at (mctx->input, + dest_str_idx - 1)) + ? CONTEXT_WORD : 0); + dest_state = mctx->state_log[dest_str_idx]; + prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0 + : mctx->state_log[cur_str_idx]->nodes.nelem); + /* Add `new_dest_node' to state_log. */ + if (dest_state == NULL) + { + mctx->state_log[dest_str_idx] + = re_acquire_state_context (&err, dfa, new_dest_nodes, + context); + if (BE (mctx->state_log[dest_str_idx] == NULL + && err != REG_NOERROR, 0)) + goto free_return; + } + else + { + re_node_set dest_nodes; + err = re_node_set_init_union (&dest_nodes, + dest_state->entrance_nodes, + new_dest_nodes); + if (BE (err != REG_NOERROR, 0)) + { + re_node_set_free (&dest_nodes); + goto free_return; + } + mctx->state_log[dest_str_idx] + = re_acquire_state_context (&err, dfa, &dest_nodes, context); + re_node_set_free (&dest_nodes); + if (BE (mctx->state_log[dest_str_idx] == NULL + && err != REG_NOERROR, 0)) + goto free_return; + } + /* We need to check recursively if the backreference can epsilon + transit. */ + if (subexp_len == 0 + && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem) + { + err = transit_state_bkref_loop (preg, new_dest_nodes, + work_state_log, mctx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + } } err = REG_NOERROR; free_return: @@ -2663,56 +2663,56 @@ out_free: 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) - { - err = re_node_set_merge (&follows, dfa->eclosures + next_node); - if (BE (err != REG_NOERROR, 0)) + { + next_node = dfa->nexts[dests_node[i].elems[j]]; + if (next_node != -1) + { + err = re_node_set_merge (&follows, dfa->eclosures + next_node); + if (BE (err != REG_NOERROR, 0)) goto out_free; - } - } + } + } /* If search flag is set, merge the initial state. */ if (fl_search) - { + { #ifdef RE_ENABLE_I18N - int not_initial = 0; - for (j = 0; j < follows.nelem; ++j) - if (dfa->nodes[follows.elems[j]].type == CHARACTER) - { - not_initial = dfa->nodes[follows.elems[j]].mb_partial; - break; - } - if (!not_initial) + int not_initial = 0; + for (j = 0; j < follows.nelem; ++j) + if (dfa->nodes[follows.elems[j]].type == CHARACTER) + { + not_initial = dfa->nodes[follows.elems[j]].mb_partial; + break; + } + if (!not_initial) #endif - { - err = re_node_set_merge (&follows, - dfa->init_state->entrance_nodes); - if (BE (err != REG_NOERROR, 0)) - goto out_free; - } - } + { + err = re_node_set_merge (&follows, + dfa->init_state->entrance_nodes); + if (BE (err != REG_NOERROR, 0)) + goto out_free; + } + } dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0); if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0)) - goto out_free; + goto out_free; /* If the new state has context constraint, - build appropriate states for these contexts. */ + build appropriate states for these contexts. */ if (dest_states[i]->has_constraint) - { - dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows, - CONTEXT_WORD); - if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0)) - goto out_free; - 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; - } + { + dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows, + CONTEXT_WORD); + if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0)) + goto out_free; + 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]; - dest_states_nl[i] = dest_states[i]; - } + { + dest_states_word[i] = dest_states[i]; + dest_states_nl[i] = dest_states[i]; + } bitset_merge (acceptable, dests_ch[i]); } @@ -2721,46 +2721,46 @@ out_free: for (i = 0, ch = 0; i < BITSET_UINTS; ++i) for (j = 0; j < UINT_BITS; ++j, ++ch) if ((acceptable[i] >> j) & 1) - { - /* The current state accepts the character ch. */ - if (IS_WORD_CHAR (ch)) - { - for (k = 0; k < ndests; ++k) - if ((dests_ch[k][i] >> j) & 1) - { - /* k-th destination accepts the word character ch. */ - trtable[ch] = dest_states_word[k]; - /* There must be only one destination which accepts - character ch. See group_nodes_into_DFAstates. */ - break; - } - } - else /* not WORD_CHAR */ - { - for (k = 0; k < ndests; ++k) - if ((dests_ch[k][i] >> j) & 1) - { - /* k-th destination accepts the non-word character ch. */ - trtable[ch] = dest_states[k]; - /* There must be only one destination which accepts - character ch. See group_nodes_into_DFAstates. */ - break; - } - } - } + { + /* The current state accepts the character ch. */ + if (IS_WORD_CHAR (ch)) + { + for (k = 0; k < ndests; ++k) + if ((dests_ch[k][i] >> j) & 1) + { + /* k-th destination accepts the word character ch. */ + trtable[ch] = dest_states_word[k]; + /* There must be only one destination which accepts + character ch. See group_nodes_into_DFAstates. */ + break; + } + } + else /* not WORD_CHAR */ + { + for (k = 0; k < ndests; ++k) + if ((dests_ch[k][i] >> j) & 1) + { + /* k-th destination accepts the non-word character ch. */ + trtable[ch] = dest_states[k]; + /* There must be only one destination which accepts + character ch. See group_nodes_into_DFAstates. */ + break; + } + } + } /* new line */ if (bitset_contain (acceptable, NEWLINE_CHAR)) { /* The current state accepts newline character. */ for (k = 0; k < ndests; ++k) - if (bitset_contain (dests_ch[k], NEWLINE_CHAR)) - { - /* k-th destination accepts newline character. */ - trtable[NEWLINE_CHAR] = dest_states_nl[k]; - /* There must be only one destination which accepts - newline. See group_nodes_into_DFAstates. */ - break; - } + if (bitset_contain (dests_ch[k], NEWLINE_CHAR)) + { + /* k-th destination accepts newline character. */ + trtable[NEWLINE_CHAR] = dest_states_nl[k]; + /* There must be only one destination which accepts + newline. See group_nodes_into_DFAstates. */ + break; + } } if (dest_states_malloced) @@ -2806,103 +2806,103 @@ group_nodes_into_DFAstates (preg, state, dests_node, dests_ch) /* Enumerate all single byte character this node can accept. */ if (type == CHARACTER) - bitset_set (accepts, node->opr.c); + bitset_set (accepts, node->opr.c); else if (type == SIMPLE_BRACKET) - { - bitset_merge (accepts, node->opr.sbcset); - } + { + bitset_merge (accepts, node->opr.sbcset); + } else if (type == OP_PERIOD) - { - bitset_set_all (accepts); - if (!(preg->syntax & RE_DOT_NEWLINE)) - bitset_clear (accepts, '\n'); - if (preg->syntax & RE_DOT_NOT_NULL) - bitset_clear (accepts, '\0'); - } + { + bitset_set_all (accepts); + if (!(preg->syntax & RE_DOT_NEWLINE)) + bitset_clear (accepts, '\n'); + if (preg->syntax & RE_DOT_NOT_NULL) + bitset_clear (accepts, '\0'); + } else - continue; + continue; /* Check the `accepts' and sift the characters which are not - match it the context. */ + match it the context. */ if (constraint) - { - if (constraint & NEXT_WORD_CONSTRAINT) - for (j = 0; j < BITSET_UINTS; ++j) - accepts[j] &= dfa->word_char[j]; - if (constraint & NEXT_NOTWORD_CONSTRAINT) - for (j = 0; j < BITSET_UINTS; ++j) - accepts[j] &= ~dfa->word_char[j]; - if (constraint & NEXT_NEWLINE_CONSTRAINT) - { - int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR); - bitset_empty (accepts); - if (accepts_newline) - bitset_set (accepts, NEWLINE_CHAR); - else - continue; - } - } + { + if (constraint & NEXT_WORD_CONSTRAINT) + for (j = 0; j < BITSET_UINTS; ++j) + accepts[j] &= dfa->word_char[j]; + if (constraint & NEXT_NOTWORD_CONSTRAINT) + for (j = 0; j < BITSET_UINTS; ++j) + accepts[j] &= ~dfa->word_char[j]; + if (constraint & NEXT_NEWLINE_CONSTRAINT) + { + int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR); + bitset_empty (accepts); + if (accepts_newline) + bitset_set (accepts, NEWLINE_CHAR); + else + continue; + } + } /* Then divide `accepts' into DFA states, or create a new - state. */ + state. */ for (j = 0; j < ndests; ++j) - { - bitset intersec; /* Intersection sets, see below. */ - bitset remains; - /* Flags, see below. */ - int 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)) - continue; - - /* Enumerate the intersection set of this state and `accepts'. */ - has_intersec = 0; - for (k = 0; k < BITSET_UINTS; ++k) - has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k]; - /* And skip if the intersection set is empty. */ - if (!has_intersec) - continue; - - /* Then check if this state is a subset of `accepts'. */ - not_subset = not_consumed = 0; - for (k = 0; k < BITSET_UINTS; ++k) - { - not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k]; - not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k]; - } - - /* If this state isn't a subset of `accepts', create a - new group state, which has the `remains'. */ - if (not_subset) - { - bitset_copy (dests_ch[ndests], remains); - bitset_copy (dests_ch[j], intersec); - err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]); - if (BE (err != REG_NOERROR, 0)) - goto error_return; - ++ndests; - } - - /* Put the position in the current group. */ - err = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]); - if (BE (err < 0, 0)) - goto error_return; - - /* If all characters are consumed, go to next node. */ - if (!not_consumed) - break; - } + { + bitset intersec; /* Intersection sets, see below. */ + bitset remains; + /* Flags, see below. */ + int 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)) + continue; + + /* Enumerate the intersection set of this state and `accepts'. */ + has_intersec = 0; + for (k = 0; k < BITSET_UINTS; ++k) + has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k]; + /* And skip if the intersection set is empty. */ + if (!has_intersec) + continue; + + /* Then check if this state is a subset of `accepts'. */ + not_subset = not_consumed = 0; + for (k = 0; k < BITSET_UINTS; ++k) + { + not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k]; + not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k]; + } + + /* If this state isn't a subset of `accepts', create a + new group state, which has the `remains'. */ + if (not_subset) + { + bitset_copy (dests_ch[ndests], remains); + bitset_copy (dests_ch[j], intersec); + err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]); + if (BE (err != REG_NOERROR, 0)) + goto error_return; + ++ndests; + } + + /* Put the position in the current group. */ + err = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]); + if (BE (err < 0, 0)) + goto error_return; + + /* If all characters are consumed, go to next node. */ + if (!not_consumed) + break; + } /* Some characters remain, create a new group. */ if (j == ndests) - { - bitset_copy (dests_ch[ndests], accepts); - err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]); - if (BE (err != REG_NOERROR, 0)) - goto error_return; - ++ndests; - bitset_empty (accepts); - } + { + bitset_copy (dests_ch[ndests], accepts); + err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]); + if (BE (err != REG_NOERROR, 0)) + goto error_return; + ++ndests; + bitset_empty (accepts); + } } return ndests; error_return: @@ -2941,10 +2941,10 @@ check_node_accept_bytes (preg, node_idx, input, str_idx) { /* '.' accepts any one character except the following two cases. */ if ((!(preg->syntax & RE_DOT_NEWLINE) && - re_string_byte_at (input, str_idx) == '\n') || - ((preg->syntax & RE_DOT_NOT_NULL) && - re_string_byte_at (input, str_idx) == '\0')) - return 0; + re_string_byte_at (input, str_idx) == '\n') || + ((preg->syntax & RE_DOT_NOT_NULL) && + re_string_byte_at (input, str_idx) == '\0')) + return 0; return char_len; } else if (node->type == COMPLEX_BRACKET) @@ -2955,145 +2955,145 @@ check_node_accept_bytes (preg, node_idx, input, str_idx) # endif /* _LIBC */ int match_len = 0; wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars) - ? re_string_wchar_at (input, str_idx) : 0); + ? re_string_wchar_at (input, str_idx) : 0); /* match with multibyte character? */ for (i = 0; i < cset->nmbchars; ++i) - if (wc == cset->mbchars[i]) - { - match_len = char_len; - goto check_node_accept_bytes_match; - } + if (wc == cset->mbchars[i]) + { + match_len = char_len; + goto check_node_accept_bytes_match; + } /* match with character_class? */ for (i = 0; i < cset->nchar_classes; ++i) - { - wctype_t wt = cset->char_classes[i]; - if (__iswctype (wc, wt)) - { - match_len = char_len; - goto check_node_accept_bytes_match; - } - } + { + wctype_t wt = cset->char_classes[i]; + if (__iswctype (wc, wt)) + { + match_len = char_len; + goto check_node_accept_bytes_match; + } + } # ifdef _LIBC if (nrules != 0) - { - unsigned int in_collseq = 0; - const int32_t *table, *indirect; - const unsigned char *weights, *extra; - const char *collseqwc; - int32_t idx; - /* This #include defines a local function! */ + { + unsigned int in_collseq = 0; + const int32_t *table, *indirect; + const unsigned char *weights, *extra; + const char *collseqwc; + int32_t idx; + /* This #include defines a local function! */ # include <locale/weight.h> - /* match with collating_symbol? */ - if (cset->ncoll_syms) - extra = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB); - for (i = 0; i < cset->ncoll_syms; ++i) - { - const unsigned char *coll_sym = extra + cset->coll_syms[i]; - /* Compare the length of input collating element and - the length of current collating element. */ - if (*coll_sym != elem_len) - continue; - /* Compare each bytes. */ - for (j = 0; j < *coll_sym; j++) - if (pin[j] != coll_sym[1 + j]) - break; - if (j == *coll_sym) - { - /* Match if every bytes is equal. */ - match_len = j; - goto check_node_accept_bytes_match; - } - } - - if (cset->nranges) - { - if (elem_len <= char_len) - { - collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC); - in_collseq = collseq_table_lookup (collseqwc, wc); - } - else - in_collseq = find_collation_sequence_value (pin, elem_len); - } - /* match with range expression? */ - for (i = 0; i < cset->nranges; ++i) - if (cset->range_starts[i] <= in_collseq - && in_collseq <= cset->range_ends[i]) - { - match_len = elem_len; - goto check_node_accept_bytes_match; - } - - /* match with equivalence_class? */ - if (cset->nequiv_classes) - { - const unsigned char *cp = pin; - table = (const int32_t *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); - weights = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB); - extra = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); - indirect = (const int32_t *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB); - 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]) - { - int cnt = 0; - while (cnt <= weight_len - && (weights[equiv_class_idx + 1 + cnt] - == weights[idx + 1 + cnt])) - ++cnt; - if (cnt > weight_len) - { - match_len = elem_len; - goto check_node_accept_bytes_match; - } - } - } - } - } + /* match with collating_symbol? */ + if (cset->ncoll_syms) + extra = (const unsigned char *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB); + for (i = 0; i < cset->ncoll_syms; ++i) + { + const unsigned char *coll_sym = extra + cset->coll_syms[i]; + /* Compare the length of input collating element and + the length of current collating element. */ + if (*coll_sym != elem_len) + continue; + /* Compare each bytes. */ + for (j = 0; j < *coll_sym; j++) + if (pin[j] != coll_sym[1 + j]) + break; + if (j == *coll_sym) + { + /* Match if every bytes is equal. */ + match_len = j; + goto check_node_accept_bytes_match; + } + } + + if (cset->nranges) + { + if (elem_len <= char_len) + { + collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC); + in_collseq = collseq_table_lookup (collseqwc, wc); + } + else + in_collseq = find_collation_sequence_value (pin, elem_len); + } + /* match with range expression? */ + for (i = 0; i < cset->nranges; ++i) + if (cset->range_starts[i] <= in_collseq + && in_collseq <= cset->range_ends[i]) + { + match_len = elem_len; + goto check_node_accept_bytes_match; + } + + /* match with equivalence_class? */ + if (cset->nequiv_classes) + { + const unsigned char *cp = pin; + table = (const int32_t *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); + weights = (const unsigned char *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB); + extra = (const unsigned char *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); + indirect = (const int32_t *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB); + 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]) + { + int cnt = 0; + while (cnt <= weight_len + && (weights[equiv_class_idx + 1 + cnt] + == weights[idx + 1 + cnt])) + ++cnt; + if (cnt > weight_len) + { + match_len = elem_len; + goto check_node_accept_bytes_match; + } + } + } + } + } else # endif /* _LIBC */ - { - /* match with range expression? */ + { + /* match with range expression? */ #if __GNUC__ >= 2 - wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'}; + 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'}; - cmp_buf[2] = wc; + wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'}; + cmp_buf[2] = wc; #endif - for (i = 0; i < cset->nranges; ++i) - { - cmp_buf[0] = cset->range_starts[i]; - cmp_buf[4] = cset->range_ends[i]; - if (wcscoll (cmp_buf, cmp_buf + 2) <= 0 - && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0) - { - match_len = char_len; - goto check_node_accept_bytes_match; - } - } - } + for (i = 0; i < cset->nranges; ++i) + { + cmp_buf[0] = cset->range_starts[i]; + cmp_buf[4] = cset->range_ends[i]; + if (wcscoll (cmp_buf, cmp_buf + 2) <= 0 + && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0) + { + match_len = char_len; + goto check_node_accept_bytes_match; + } + } + } check_node_accept_bytes_match: if (!cset->non_match) - return match_len; + return match_len; else - { - if (match_len > 0) - return 0; - else - return (elem_len > char_len) ? elem_len : char_len; - } + { + if (match_len > 0) + return 0; + else + return (elem_len > char_len) ? elem_len : char_len; + } } return 0; } @@ -3108,50 +3108,50 @@ find_collation_sequence_value (mbs, mbs_len) if (nrules == 0) { if (mbs_len == 1) - { - /* No valid character. Match it as a single byte character. */ - const unsigned char *collseq = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB); - return collseq[mbs[0]]; - } + { + /* No valid character. Match it as a single byte character. */ + const unsigned char *collseq = (const unsigned char *) + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB); + return collseq[mbs[0]]; + } return UINT_MAX; } else { int32_t idx; const unsigned char *extra = (const unsigned char *) - _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB); + _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB); for (idx = 0; ;) - { - int mbs_cnt, found = 0; - int32_t elem_mbs_len; - /* Skip the name of collating element name. */ - idx = idx + extra[idx] + 1; - elem_mbs_len = extra[idx++]; - if (mbs_len == elem_mbs_len) - { - for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt) - if (extra[idx + mbs_cnt] != mbs[mbs_cnt]) - break; - if (mbs_cnt == elem_mbs_len) - /* Found the entry. */ - found = 1; - } - /* Skip the byte sequence of the collating element. */ - idx += elem_mbs_len; - /* Adjust for the alignment. */ - idx = (idx + 3) & ~3; - /* Skip the collation sequence value. */ - idx += sizeof (uint32_t); - /* Skip the wide char sequence of the collating element. */ - idx = idx + sizeof (uint32_t) * (extra[idx] + 1); - /* If we found the entry, return the sequence value. */ - if (found) - return *(uint32_t *) (extra + idx); - /* Skip the collation sequence value. */ - idx += sizeof (uint32_t); - } + { + int mbs_cnt, found = 0; + int32_t elem_mbs_len; + /* Skip the name of collating element name. */ + idx = idx + extra[idx] + 1; + elem_mbs_len = extra[idx++]; + if (mbs_len == elem_mbs_len) + { + for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt) + if (extra[idx + mbs_cnt] != mbs[mbs_cnt]) + break; + if (mbs_cnt == elem_mbs_len) + /* Found the entry. */ + found = 1; + } + /* Skip the byte sequence of the collating element. */ + idx += elem_mbs_len; + /* Adjust for the alignment. */ + idx = (idx + 3) & ~3; + /* Skip the collation sequence value. */ + idx += sizeof (uint32_t); + /* Skip the wide char sequence of the collating element. */ + idx = idx + sizeof (uint32_t) * (extra[idx] + 1); + /* If we found the entry, return the sequence value. */ + if (found) + return *(uint32_t *) (extra + idx); + /* Skip the collation sequence value. */ + idx += sizeof (uint32_t); + } } } # endif /* _LIBC */ @@ -3171,12 +3171,12 @@ check_node_accept (preg, node, mctx, idx) if (node->constraint) { /* The node has constraints. Check whether the current context - satisfies the constraints. */ + satisfies the constraints. */ unsigned int context = re_string_context_at (mctx->input, idx, - mctx->eflags, - preg->newline_anchor); + mctx->eflags, + preg->newline_anchor); if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context)) - return 0; + return 0; } ch = re_string_byte_at (mctx->input, idx); if (node->type == CHARACTER) @@ -3185,7 +3185,7 @@ check_node_accept (preg, node, mctx, idx) return bitset_contain (node->opr.sbcset, ch); else if (node->type == OP_PERIOD) return !((ch == '\n' && !(preg->syntax & RE_DOT_NEWLINE)) - || (ch == '\0' && (preg->syntax & RE_DOT_NOT_NULL))); + || (ch == '\0' && (preg->syntax & RE_DOT_NOT_NULL))); else return 0; } @@ -3209,9 +3209,9 @@ extend_buffers (mctx) /* And double the length of state_log. */ re_dfastate_t **new_array; new_array = re_realloc (mctx->state_log, re_dfastate_t *, - pstr->bufs_len * 2); + pstr->bufs_len * 2); if (BE (new_array == NULL, 0)) - return REG_ESPACE; + return REG_ESPACE; mctx->state_log = new_array; } @@ -3220,24 +3220,24 @@ extend_buffers (mctx) { #ifdef RE_ENABLE_I18N if (MB_CUR_MAX > 1) - build_wcs_upper_buffer (pstr); + build_wcs_upper_buffer (pstr); else #endif /* RE_ENABLE_I18N */ - build_upper_buffer (pstr); + build_upper_buffer (pstr); } else { #ifdef RE_ENABLE_I18N if (MB_CUR_MAX > 1) - build_wcs_buffer (pstr); + build_wcs_buffer (pstr); else #endif /* RE_ENABLE_I18N */ - { - if (pstr->trans != NULL) - re_string_translate_buffer (pstr); - else - pstr->valid_len = pstr->bufs_len; - } + { + if (pstr->trans != NULL) + re_string_translate_buffer (pstr); + else + pstr->valid_len = pstr->bufs_len; + } } return REG_NOERROR; } @@ -3258,7 +3258,7 @@ match_ctx_init (mctx, eflags, input, n) { mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n); if (BE (mctx->bkref_ents == NULL, 0)) - return REG_ESPACE; + return REG_ESPACE; } else mctx->bkref_ents = NULL; @@ -3286,15 +3286,15 @@ match_ctx_add_entry (mctx, node, str_idx, from, to) { struct re_backref_cache_entry* new_entry; new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry, - mctx->abkref_ents * 2); + mctx->abkref_ents * 2); if (BE (new_entry == NULL, 0)) - { - re_free (mctx->bkref_ents); - return REG_ESPACE; - } + { + re_free (mctx->bkref_ents); + return REG_ESPACE; + } mctx->bkref_ents = new_entry; memset (mctx->bkref_ents + mctx->nbkref_ents, '\0', - sizeof (struct re_backref_cache_entry) * mctx->abkref_ents); + sizeof (struct re_backref_cache_entry) * mctx->abkref_ents); mctx->abkref_ents *= 2; } mctx->bkref_ents[mctx->nbkref_ents].node = node; @@ -3320,7 +3320,7 @@ match_ctx_clear_flag (mctx) static void sift_ctx_init (sctx, sifted_sts, limited_sts, last_node, last_str_idx, - check_subexp) + check_subexp) re_sift_context_t *sctx; re_dfastate_t **sifted_sts, **limited_sts; int last_node, last_str_idx, check_subexp; |