summaryrefslogtreecommitdiff
path: root/posix/regcomp.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2004-12-22 20:10:10 +0000
committerUlrich Drepper <drepper@redhat.com>2004-12-22 20:10:10 +0000
commita334319f6530564d22e775935d9c91663623a1b4 (patch)
treeb5877475619e4c938e98757d518bb1e9cbead751 /posix/regcomp.c
parent0ecb606cb6cf65de1d9fc8a919bceb4be476c602 (diff)
downloadglibc-a334319f6530564d22e775935d9c91663623a1b4.tar.gz
(CFLAGS-tst-align.c): Add -mpreferred-stack-boundary=4.
Diffstat (limited to 'posix/regcomp.c')
-rw-r--r--posix/regcomp.c1483
1 files changed, 804 insertions, 679 deletions
diff --git a/posix/regcomp.c b/posix/regcomp.c
index e99fd74924..5de5bf725a 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -1,5 +1,5 @@
/* Extended regular expression matching and search library.
- Copyright (C) 2002,2003,2004,2005,2006,2007 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of the GNU C Library.
Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
@@ -19,11 +19,12 @@
02111-1307 USA. */
static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
- size_t 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);
-static reg_errcode_t init_dfa (re_dfa_t *dfa, size_t pat_len);
+static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
+static void init_word_char (re_dfa_t *dfa);
#ifdef RE_ENABLE_I18N
static void free_charset (re_charset_t *cset);
#endif /* RE_ENABLE_I18N */
@@ -32,31 +33,38 @@ static reg_errcode_t create_initial_state (re_dfa_t *dfa);
#ifdef RE_ENABLE_I18N
static void optimize_utf8 (re_dfa_t *dfa);
#endif
-static reg_errcode_t analyze (regex_t *preg);
-static reg_errcode_t preorder (bin_tree_t *root,
- reg_errcode_t (fn (void *, bin_tree_t *)),
- void *extra);
-static reg_errcode_t postorder (bin_tree_t *root,
- reg_errcode_t (fn (void *, bin_tree_t *)),
- void *extra);
-static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
-static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
-static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
- bin_tree_t *node);
-static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
-static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
-static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
-static int duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint);
-static int search_duplicated_node (const re_dfa_t *dfa, int org_node,
+struct subexp_optimize
+{
+ re_dfa_t *dfa;
+ re_token_t *nodes;
+ int no_sub, re_nsub;
+};
+static bin_tree_t *optimize_subexps (struct subexp_optimize *so,
+ bin_tree_t *node, int sidx, int depth);
+static reg_errcode_t analyze (re_dfa_t *dfa);
+static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);
+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);
+static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
+ unsigned int constraint);
+static int search_duplicated_node (re_dfa_t *dfa, int org_node,
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);
-static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
+static void calc_inveclosure (re_dfa_t *dfa);
static int fetch_number (re_string_t *input, re_token_t *token,
reg_syntax_t syntax);
+static void fetch_token (re_token_t *result, re_string_t *input,
+ reg_syntax_t syntax);
static int peek_token (re_token_t *token, re_string_t *input,
- reg_syntax_t syntax) internal_function;
+ reg_syntax_t syntax);
+static int peek_token_bracket (re_token_t *token, re_string_t *input,
+ reg_syntax_t syntax);
static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
reg_syntax_t syntax, reg_errcode_t *err);
static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
@@ -86,40 +94,58 @@ static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
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);
+static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
+ 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);
+static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
+ const unsigned char *name);
+# endif /* not RE_ENABLE_I18N */
+#endif /* not _LIBC */
#ifdef RE_ENABLE_I18N
-static reg_errcode_t build_equiv_class (bitset_t sbcset,
+static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
re_charset_t *mbcset,
int *equiv_class_alloc,
const unsigned char *name);
-static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
- bitset_t sbcset,
+static reg_errcode_t build_charclass (unsigned RE_TRANSLATE_TYPE trans,
+ re_bitset_ptr_t sbcset,
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 (bitset_t sbcset,
+static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
const unsigned char *name);
-static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
- bitset_t sbcset,
+static reg_errcode_t build_charclass (unsigned RE_TRANSLATE_TYPE trans,
+ re_bitset_ptr_t sbcset,
const unsigned char *class_name,
reg_syntax_t syntax);
#endif /* not RE_ENABLE_I18N */
static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
- RE_TRANSLATE_TYPE trans,
+ unsigned RE_TRANSLATE_TYPE trans,
const unsigned char *class_name,
const unsigned char *extra,
int non_match, reg_errcode_t *err);
static bin_tree_t *create_tree (re_dfa_t *dfa,
bin_tree_t *left, bin_tree_t *right,
- re_token_type_t type);
-static bin_tree_t *create_token_tree (re_dfa_t *dfa,
- bin_tree_t *left, bin_tree_t *right,
- const re_token_t *token);
+ re_token_type_t type, int index);
+static bin_tree_t *re_dfa_add_tree_node (re_dfa_t *dfa,
+ bin_tree_t *left, bin_tree_t *right,
+ const re_token_t *token)
+ __attribute ((noinline));
static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
-static void free_token (re_token_t *node);
-static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
-static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
+static void mark_opt_subexp (const bin_tree_t *src, re_dfa_t *dfa);
+static void mark_opt_subexp_iter (const bin_tree_t *src, re_dfa_t *dfa, int idx);
/* This table gives an error message for each of the error codes listed
in regex.h. Obviously the order here has to be same as there.
@@ -299,8 +325,10 @@ re_set_fastmap (char *fastmap, int icase, int ch)
Compile fastmap for the initial_state INIT_STATE. */
static void
-re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
- char *fastmap)
+re_compile_fastmap_iter (bufp, init_state, fastmap)
+ regex_t *bufp;
+ const re_dfastate_t *init_state;
+ char *fastmap;
{
re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
int node_cnt;
@@ -326,26 +354,21 @@ re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
&& dfa->nodes[node].type == CHARACTER
&& dfa->nodes[node].mb_partial)
*p++ = dfa->nodes[node].opr.c;
- memset (&state, '\0', sizeof (state));
+ memset (&state, 0, sizeof (state));
if (mbrtowc (&wc, (const char *) buf, p - buf,
&state) == p - buf
- && (__wcrtomb ((char *) buf, towlower (wc), &state)
- != (size_t) -1))
+ && __wcrtomb ((char *) buf, towlower (wc), &state) > 0)
re_set_fastmap (fastmap, 0, buf[0]);
}
#endif
}
else if (type == SIMPLE_BRACKET)
{
- int i, ch;
- for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
- {
- int j;
- bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
- for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
- if (w & ((bitset_word_t) 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)
@@ -364,11 +387,13 @@ re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
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; i < SBC_MAX; ++i)
- if (table[i] < 0)
- re_set_fastmap (fastmap, icase, i);
+ 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 (dfa->mb_cur_max > 1)
@@ -382,13 +407,12 @@ re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
char buf[256];
mbstate_t state;
memset (&state, '\0', sizeof (state));
- if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)
- re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
+ __wcrtomb (buf, cset->mbchars[i], &state);
+ re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
{
- if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
- != (size_t) -1)
- re_set_fastmap (fastmap, 0, *(unsigned char *) buf);
+ __wcrtomb (buf, towlower (cset->mbchars[i]), &state);
+ re_set_fastmap (fastmap, 0, *(unsigned char *) buf);
}
}
}
@@ -508,8 +532,8 @@ weak_alias (__regcomp, regcomp)
size_t
regerror (errcode, preg, errbuf, errbuf_size)
int errcode;
- const regex_t *__restrict preg;
- char *__restrict errbuf;
+ const regex_t *preg;
+ char *errbuf;
size_t errbuf_size;
{
const char *msg;
@@ -555,10 +579,14 @@ weak_alias (__regerror, regerror)
UTF-8 is used. Otherwise we would allocate memory just to initialize
it the same all the time. UTF-8 is the preferred encoding so this is
a worthwhile optimization. */
-static const bitset_t utf8_sb_map =
+static const bitset utf8_sb_map =
{
/* Set the first 128 bits. */
- [0 ... 0x80 / BITSET_WORD_BITS - 1] = BITSET_WORD_MAX
+# if UINT_MAX == 0xffffffff
+ 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
+# else
+# error "Add case for new unsigned int size"
+# endif
};
#endif
@@ -570,7 +598,16 @@ free_dfa_content (re_dfa_t *dfa)
if (dfa->nodes)
for (i = 0; i < dfa->nodes_len; ++i)
- free_token (dfa->nodes + i);
+ {
+ re_token_t *node = dfa->nodes + i;
+#ifdef RE_ENABLE_I18N
+ if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
+ free_charset (node->opr.mbcset);
+ else
+#endif /* RE_ENABLE_I18N */
+ if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
+ re_free (node->opr.sbcset);
+ }
re_free (dfa->nexts);
for (i = 0; i < dfa->nodes_len; ++i)
{
@@ -707,8 +744,11 @@ libc_freeres_fn (free_mem)
SYNTAX indicate regular expression's syntax. */
static reg_errcode_t
-re_compile_internal (regex_t *preg, const char * pattern, size_t length,
- reg_syntax_t syntax)
+re_compile_internal (preg, pattern, length, syntax)
+ regex_t *preg;
+ const char * pattern;
+ int length;
+ reg_syntax_t syntax;
{
reg_errcode_t err = REG_NOERROR;
re_dfa_t *dfa;
@@ -748,13 +788,10 @@ re_compile_internal (regex_t *preg, const char * pattern, size_t length,
return err;
}
#ifdef DEBUG
- /* Note: length+1 will not overflow since it is checked in init_dfa. */
dfa->re_str = re_malloc (char, length + 1);
strncpy (dfa->re_str, pattern, length + 1);
#endif
- __libc_lock_init (dfa->lock);
-
err = re_string_construct (&regexp, pattern, length, preg->translate,
syntax & RE_ICASE, dfa);
if (BE (err != REG_NOERROR, 0))
@@ -774,17 +811,29 @@ re_compile_internal (regex_t *preg, const char * pattern, size_t length,
if (BE (dfa->str_tree == NULL, 0))
goto re_compile_internal_free_return;
- /* Analyze the tree and create the nfa. */
- err = analyze (preg);
- if (BE (err != REG_NOERROR, 0))
- goto re_compile_internal_free_return;
-
#ifdef RE_ENABLE_I18N
/* If possible, do searching in single byte encoding to speed things up. */
if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)
optimize_utf8 (dfa);
#endif
+ if (preg->re_nsub > 0)
+ {
+ struct subexp_optimize so;
+
+ so.dfa = dfa;
+ so.nodes = dfa->nodes;
+ so.no_sub = preg->no_sub;
+ so.re_nsub = preg->re_nsub;
+ dfa->str_tree = optimize_subexps (&so, dfa->str_tree, -1, 0);
+ }
+
+ /* Analyze the tree and collect information which is necessary to
+ create the dfa. */
+ err = analyze (dfa);
+ if (BE (err != REG_NOERROR, 0))
+ goto re_compile_internal_free_return;
+
/* Then create the initial state of the dfa. */
err = create_initial_state (dfa);
@@ -806,9 +855,11 @@ re_compile_internal (regex_t *preg, const char * pattern, size_t length,
as the initial length of some arrays. */
static reg_errcode_t
-init_dfa (re_dfa_t *dfa, size_t pat_len)
+init_dfa (dfa, pat_len)
+ re_dfa_t *dfa;
+ int pat_len;
{
- unsigned int table_size;
+ int table_size;
#ifndef _LIBC
char *codeset_name;
#endif
@@ -818,15 +869,13 @@ init_dfa (re_dfa_t *dfa, size_t pat_len)
/* Force allocation of str_tree_storage the first time. */
dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
- /* Avoid overflows. */
- if (pat_len == SIZE_MAX)
- return REG_ESPACE;
-
dfa->nodes_alloc = pat_len + 1;
dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
+ dfa->states_alloc = pat_len + 1;
+
/* table_size = 2 ^ ceil(log pat_len) */
- for (table_size = 1; ; table_size <<= 1)
+ for (table_size = 1; table_size > 0; table_size <<= 1)
if (table_size > pat_len)
break;
@@ -845,9 +894,9 @@ init_dfa (re_dfa_t *dfa, size_t pat_len)
codeset_name = nl_langinfo (CODESET);
# else
codeset_name = getenv ("LC_ALL");
- if (codeset_name == NULL || codeset_name[0] == '\0')
+ if (codeset_name == NULL || codeset[0] == '\0')
codeset_name = getenv ("LC_CTYPE");
- if (codeset_name == NULL || codeset_name[0] == '\0')
+ if (codeset_name == NULL || codeset[0] == '\0')
codeset_name = getenv ("LANG");
if (codeset_name == NULL)
codeset_name = "";
@@ -873,19 +922,22 @@ init_dfa (re_dfa_t *dfa, size_t pat_len)
{
int i, j, ch;
- dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
+ dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);
if (BE (dfa->sb_char == NULL, 0))
return REG_ESPACE;
- /* Set the bits corresponding to single byte chars. */
- for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
- for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
+ /* Clear all bits by, then set those corresponding to single
+ byte chars. */
+ bitset_empty (dfa->sb_char);
+
+ for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
+ for (j = 0; j < UINT_BITS; ++j, ++ch)
{
- wint_t wch = __btowc (ch);
+ wchar_t wch = __btowc (ch);
if (wch != WEOF)
- dfa->sb_char[i] |= (bitset_word_t) 1 << j;
+ dfa->sb_char[i] |= 1 << j;
# ifndef _LIBC
- if (isascii (ch) && wch != ch)
+ if (isascii (ch) && wch != (wchar_t) ch)
dfa->map_notascii = 1;
# endif
}
@@ -903,21 +955,22 @@ init_dfa (re_dfa_t *dfa, size_t pat_len)
character used by some operators like "\<", "\>", etc. */
static void
-internal_function
-init_word_char (re_dfa_t *dfa)
+init_word_char (dfa)
+ re_dfa_t *dfa;
{
int i, j, ch;
dfa->word_ops_used = 1;
- for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
- for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
+ 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] |= (bitset_word_t) 1 << j;
+ dfa->word_char[i] |= 1 << j;
}
/* Free the work area which are only used while compiling. */
static void
-free_workarea_compile (regex_t *preg)
+free_workarea_compile (preg)
+ regex_t *preg;
{
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
bin_tree_storage_t *storage, *next;
@@ -936,7 +989,8 @@ free_workarea_compile (regex_t *preg)
/* Create initial states for all contexts. */
static reg_errcode_t
-create_initial_state (re_dfa_t *dfa)
+create_initial_state (dfa)
+ re_dfa_t *dfa;
{
int first, i;
reg_errcode_t err;
@@ -944,7 +998,7 @@ create_initial_state (re_dfa_t *dfa)
/* Initial states have the epsilon closure of the node which is
the first node of the regular expression. */
- first = dfa->str_tree->first->node_idx;
+ first = dfa->str_tree->first;
dfa->init_node = first;
err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
if (BE (err != REG_NOERROR, 0))
@@ -1018,7 +1072,8 @@ create_initial_state (re_dfa_t *dfa)
DFA nodes where needed. */
static void
-optimize_utf8 (re_dfa_t *dfa)
+optimize_utf8 (dfa)
+ re_dfa_t *dfa;
{
int node, i, mb_chars = 0, has_period = 0;
@@ -1049,20 +1104,18 @@ optimize_utf8 (re_dfa_t *dfa)
case OP_ALT:
case END_OF_RE:
case OP_DUP_ASTERISK:
+ case OP_DUP_QUESTION:
case OP_OPEN_SUBEXP:
case OP_CLOSE_SUBEXP:
break;
- case COMPLEX_BRACKET:
- return;
case SIMPLE_BRACKET:
- /* Just double check. The non-ASCII range starts at 0x80. */
- assert (0x80 % BITSET_WORD_BITS == 0);
- for (i = 0x80 / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
+ /* Just double check. */
+ for (i = 0x80 / UINT_BITS; i < BITSET_UINTS; ++i)
if (dfa->nodes[node].opr.sbcset[i])
return;
break;
default:
- abort ();
+ return;
}
if (mb_chars || has_period)
@@ -1082,13 +1135,90 @@ optimize_utf8 (re_dfa_t *dfa)
}
#endif
+static bin_tree_t *
+optimize_subexps (so, node, sidx, depth)
+ struct subexp_optimize *so;
+ bin_tree_t *node;
+ int sidx, depth;
+{
+ int idx, new_depth, new_sidx;
+ bin_tree_t *ret;
+ if (node == NULL)
+ return NULL;
+
+ new_depth = 0;
+ new_sidx = sidx;
+ if ((depth & 1) && node->type == CONCAT
+ && node->right && node->right->type == 0
+ && so->nodes[idx = node->right->node_idx].type == OP_CLOSE_SUBEXP)
+ {
+ new_depth = depth + 1;
+ if (new_depth == 2
+ || (so->nodes[idx].opr.idx < 8 * sizeof (so->dfa->used_bkref_map)
+ && so->dfa->used_bkref_map & (1 << so->nodes[idx].opr.idx)))
+ new_sidx = so->nodes[idx].opr.idx;
+ }
+ node->left = optimize_subexps (so, node->left, new_sidx, new_depth);
+ new_depth = (depth & 1) == 0 && node->type == CONCAT
+ && node->left && node->left->type == 0
+ && so->nodes[node->left->node_idx].type == OP_OPEN_SUBEXP
+ ? depth + 1 : 0;
+ node->right = optimize_subexps (so, node->right, sidx, new_depth);
+
+ if (node->type != CONCAT)
+ return node;
+ if ((depth & 1) == 0
+ && node->left
+ && node->left->type == 0
+ && so->nodes[idx = node->left->node_idx].type == OP_OPEN_SUBEXP)
+ ret = node->right;
+ else if ((depth & 1)
+ && node->right
+ && node->right->type == 0
+ && so->nodes[idx = node->right->node_idx].type == OP_CLOSE_SUBEXP)
+ ret = node->left;
+ else
+ return node;
+
+ if (so->nodes[idx].opr.idx < 8 * sizeof (so->dfa->used_bkref_map)
+ && so->dfa->used_bkref_map & (1 << so->nodes[idx].opr.idx))
+ return node;
+
+ if (!so->no_sub)
+ {
+ int i;
+
+ if (depth < 2)
+ return node;
+
+ if (so->dfa->subexp_map == NULL)
+ {
+ so->dfa->subexp_map = re_malloc (int, so->re_nsub);
+ if (so->dfa->subexp_map == NULL)
+ return node;
+
+ for (i = 0; i < so->re_nsub; i++)
+ so->dfa->subexp_map[i] = i;
+ }
+
+ i = so->nodes[idx].opr.idx;
+ assert (sidx < i);
+ so->dfa->subexp_map[i] = sidx;
+ }
+
+ so->nodes[idx].type = OP_DELETED_SUBEXP;
+ ret->parent = node->parent;
+ return ret;
+}
+
/* Analyze the structure tree, and calculate "first", "next", "edest",
"eclosure", and "inveclosure". */
static reg_errcode_t
-analyze (regex_t *preg)
+analyze (dfa)
+ re_dfa_t *dfa;
{
- re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+ int i;
reg_errcode_t ret;
/* Allocate arrays. */
@@ -1096,310 +1226,225 @@ analyze (regex_t *preg)
dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
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->org_indices == NULL || dfa->edests == NULL
- || dfa->eclosures == NULL, 0))
+ || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
return REG_ESPACE;
-
- dfa->subexp_map = re_malloc (int, preg->re_nsub);
- if (dfa->subexp_map != NULL)
+ /* Initialize them. */
+ for (i = 0; i < dfa->nodes_len; ++i)
{
- int i;
- for (i = 0; i < preg->re_nsub; i++)
- dfa->subexp_map[i] = i;
- preorder (dfa->str_tree, optimize_subexps, dfa);
- for (i = 0; i < preg->re_nsub; i++)
- if (dfa->subexp_map[i] != i)
- break;
- if (i == preg->re_nsub)
- {
- free (dfa->subexp_map);
- dfa->subexp_map = NULL;
- }
+ dfa->nexts[i] = -1;
+ re_node_set_init_empty (dfa->edests + i);
+ re_node_set_init_empty (dfa->eclosures + i);
+ re_node_set_init_empty (dfa->inveclosures + i);
}
- ret = postorder (dfa->str_tree, lower_subexps, preg);
- if (BE (ret != REG_NOERROR, 0))
- return ret;
- ret = postorder (dfa->str_tree, calc_first, dfa);
- if (BE (ret != REG_NOERROR, 0))
- return ret;
- preorder (dfa->str_tree, calc_next, dfa);
- ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
- if (BE (ret != REG_NOERROR, 0))
- return ret;
- ret = calc_eclosure (dfa);
- if (BE (ret != REG_NOERROR, 0))
- return ret;
-
- /* We only need this during the prune_impossible_nodes pass in regexec.c;
- skip it if p_i_n will not run, as calc_inveclosure can be quadratic. */
- if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
- || dfa->nbackref)
+ ret = analyze_tree (dfa, dfa->str_tree);
+ if (BE (ret == REG_NOERROR, 1))
{
- dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
- if (BE (dfa->inveclosures == NULL, 0))
- return REG_ESPACE;
- ret = calc_inveclosure (dfa);
+ ret = calc_eclosure (dfa);
+ if (ret == REG_NOERROR)
+ calc_inveclosure (dfa);
}
-
return ret;
}
-/* Our parse trees are very unbalanced, so we cannot use a stack to
- implement parse tree visits. Instead, we use parent pointers and
- some hairy code in these two functions. */
-static reg_errcode_t
-postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
- void *extra)
-{
- bin_tree_t *node, *prev;
-
- for (node = root; ; )
- {
- /* Descend down the tree, preferably to the left (or to the right
- if that's the only child). */
- while (node->left || node->right)
- if (node->left)
- node = node->left;
- else
- node = node->right;
-
- do
- {
- reg_errcode_t err = fn (extra, node);
- if (BE (err != REG_NOERROR, 0))
- return err;
- if (node->parent == NULL)
- return REG_NOERROR;
- prev = node;
- node = node->parent;
- }
- /* Go up while we have a node that is reached from the right. */
- while (node->right == prev || node->right == NULL);
- node = node->right;
- }
-}
-
-static reg_errcode_t
-preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
- void *extra)
-{
- bin_tree_t *node;
-
- for (node = root; ; )
- {
- reg_errcode_t err = fn (extra, node);
- if (BE (err != REG_NOERROR, 0))
- return err;
+/* Helper functions for analyze.
+ This function calculate "first", "next", and "edest" for the subtree
+ whose root is NODE. */
- /* Go to the left node, or up and to the right. */
- if (node->left)
- node = node->left;
- else
- {
- bin_tree_t *prev = NULL;
- while (node->right == prev || node->right == NULL)
- {
- prev = node;
- node = node->parent;
- if (!node)
- return REG_NOERROR;
- }
- node = node->right;
- }
- }
-}
-
-/* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
- re_search_internal to map the inner one's opr.idx to this one's. Adjust
- backreferences as well. Requires a preorder visit. */
static reg_errcode_t
-optimize_subexps (void *extra, bin_tree_t *node)
+analyze_tree (dfa, node)
+ re_dfa_t *dfa;
+ bin_tree_t *node;
{
- re_dfa_t *dfa = (re_dfa_t *) extra;
+ reg_errcode_t ret;
+ if (node->first == -1)
+ calc_first (dfa, node);
+ if (node->next == -1)
+ calc_next (dfa, node);
+ calc_epsdest (dfa, node);
- if (node->token.type == OP_BACK_REF && dfa->subexp_map)
+ /* Calculate "first" etc. for the left child. */
+ if (node->left != NULL)
{
- int idx = node->token.opr.idx;
- node->token.opr.idx = dfa->subexp_map[idx];
- dfa->used_bkref_map |= 1 << node->token.opr.idx;
+ ret = analyze_tree (dfa, node->left);
+ if (BE (ret != REG_NOERROR, 0))
+ return ret;
}
-
- else if (node->token.type == SUBEXP
- && node->left && node->left->token.type == SUBEXP)
+ /* Calculate "first" etc. for the right child. */
+ if (node->right != NULL)
{
- int other_idx = node->left->token.opr.idx;
-
- node->left = node->left->left;
- if (node->left)
- node->left->parent = node;
-
- dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
- if (other_idx < BITSET_WORD_BITS)
- dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
+ ret = analyze_tree (dfa, node->right);
+ if (BE (ret != REG_NOERROR, 0))
+ return ret;
}
-
return REG_NOERROR;
}
-/* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
- of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP. */
-static reg_errcode_t
-lower_subexps (void *extra, bin_tree_t *node)
+/* Calculate "first" for the node NODE. */
+static void
+calc_first (dfa, node)
+ re_dfa_t *dfa;
+ bin_tree_t *node;
{
- regex_t *preg = (regex_t *) extra;
- reg_errcode_t err = REG_NOERROR;
+ int idx, type;
+ idx = node->node_idx;
+ type = (node->type == 0) ? dfa->nodes[idx].type : node->type;
- if (node->left && node->left->token.type == SUBEXP)
- {
- node->left = lower_subexp (&err, preg, node->left);
- if (node->left)
- node->left->parent = node;
- }
- if (node->right && node->right->token.type == SUBEXP)
+ switch (type)
{
- node->right = lower_subexp (&err, preg, node->right);
- if (node->right)
- node->right->parent = node;
+#ifdef DEBUG
+ case OP_OPEN_BRACKET:
+ case OP_CLOSE_BRACKET:
+ case OP_OPEN_DUP_NUM:
+ case OP_CLOSE_DUP_NUM:
+ case OP_DUP_PLUS:
+ case OP_NON_MATCH_LIST:
+ case OP_OPEN_COLL_ELEM:
+ case OP_CLOSE_COLL_ELEM:
+ case OP_OPEN_EQUIV_CLASS:
+ case OP_CLOSE_EQUIV_CLASS:
+ case OP_OPEN_CHAR_CLASS:
+ case OP_CLOSE_CHAR_CLASS:
+ /* These must not appear here. */
+ assert (0);
+#endif
+ case END_OF_RE:
+ case CHARACTER:
+ case OP_PERIOD:
+ case OP_DUP_ASTERISK:
+ case OP_DUP_QUESTION:
+#ifdef RE_ENABLE_I18N
+ case OP_UTF8_PERIOD:
+ case COMPLEX_BRACKET:
+#endif /* RE_ENABLE_I18N */
+ case SIMPLE_BRACKET:
+ case OP_BACK_REF:
+ case ANCHOR:
+ case OP_OPEN_SUBEXP:
+ case OP_CLOSE_SUBEXP:
+ node->first = idx;
+ break;
+ case OP_ALT:
+ node->first = idx;
+ break;
+ /* else fall through */
+ default:
+#ifdef DEBUG
+ assert (node->left != NULL);
+#endif
+ if (node->left->first == -1)
+ calc_first (dfa, node->left);
+ node->first = node->left->first;
+ break;
}
-
- return err;
}
-static bin_tree_t *
-lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
-{
- re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
- bin_tree_t *body = node->left;
- bin_tree_t *op, *cls, *tree1, *tree;
-
- if (preg->no_sub
- /* We do not optimize empty subexpressions, because otherwise we may
- have bad CONCAT nodes with NULL children. This is obviously not
- very common, so we do not lose much. An example that triggers
- this case is the sed "script" /\(\)/x. */
- && node->left != NULL
- && (node->token.opr.idx >= BITSET_WORD_BITS
- || !(dfa->used_bkref_map
- & ((bitset_word_t) 1 << node->token.opr.idx))))
- return node->left;
-
- /* Convert the SUBEXP node to the concatenation of an
- OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP. */
- op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
- cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
- tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
- tree = create_tree (dfa, op, tree1, CONCAT);
- if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
- {
- *err = REG_ESPACE;
- return NULL;
- }
+/* Calculate "next" for the node NODE. */
- op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
- op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
- return tree;
-}
-
-/* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
- nodes. Requires a postorder visit. */
-static reg_errcode_t
-calc_first (void *extra, bin_tree_t *node)
+static void
+calc_next (dfa, node)
+ re_dfa_t *dfa;
+ bin_tree_t *node;
{
- re_dfa_t *dfa = (re_dfa_t *) extra;
- if (node->token.type == CONCAT)
+ int idx, type;
+ bin_tree_t *parent = node->parent;
+ if (parent == NULL)
{
- node->first = node->left->first;
- node->node_idx = node->left->node_idx;
+ node->next = -1;
+ idx = node->node_idx;
+ if (node->type == 0)
+ dfa->nexts[idx] = node->next;
+ return;
}
- else
- {
- node->first = node;
- node->node_idx = re_dfa_add_node (dfa, node->token);
- if (BE (node->node_idx == -1, 0))
- return REG_ESPACE;
- }
- return REG_NOERROR;
-}
-/* Pass 2: compute NEXT on the tree. Preorder visit. */
-static reg_errcode_t
-calc_next (void *extra, bin_tree_t *node)
-{
- switch (node->token.type)
+ idx = parent->node_idx;
+ type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;
+
+ switch (type)
{
case OP_DUP_ASTERISK:
- node->left->next = node;
+ node->next = idx;
break;
case CONCAT:
- node->left->next = node->right->first;
- node->right->next = node->next;
- break;
+ if (parent->left == node)
+ {
+ if (parent->right->first == -1)
+ calc_first (dfa, parent->right);
+ node->next = parent->right->first;
+ break;
+ }
+ /* else fall through */
default:
- if (node->left)
- node->left->next = node->next;
- if (node->right)
- node->right->next = node->next;
+ if (parent->next == -1)
+ calc_next (dfa, parent);
+ node->next = parent->next;
break;
}
- return REG_NOERROR;
+ idx = node->node_idx;
+ if (node->type == 0)
+ dfa->nexts[idx] = node->next;
}
-/* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
-static reg_errcode_t
-link_nfa_nodes (void *extra, bin_tree_t *node)
-{
- re_dfa_t *dfa = (re_dfa_t *) extra;
- int idx = node->node_idx;
- reg_errcode_t err = REG_NOERROR;
+/* Calculate "edest" for the node NODE. */
- switch (node->token.type)
+static void
+calc_epsdest (dfa, node)
+ re_dfa_t *dfa;
+ bin_tree_t *node;
+{
+ int idx;
+ idx = node->node_idx;
+ if (node->type == 0)
{
- case CONCAT:
- break;
-
- case END_OF_RE:
- assert (node->next == NULL);
- break;
-
- case OP_DUP_ASTERISK:
- case OP_ALT:
- {
- int left, right;
- dfa->has_plural_match = 1;
- if (node->left != NULL)
- left = node->left->first->node_idx;
- else
- left = node->next->node_idx;
- if (node->right != NULL)
- right = node->right->first->node_idx;
- else
- right = node->next->node_idx;
- assert (left > -1);
- assert (right > -1);
- err = re_node_set_init_2 (dfa->edests + idx, left, right);
- }
- break;
-
- case ANCHOR:
- case OP_OPEN_SUBEXP:
- case OP_CLOSE_SUBEXP:
- err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
- break;
-
- case OP_BACK_REF:
- dfa->nexts[idx] = node->next->node_idx;
- if (node->token.type == OP_BACK_REF)
- re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
- break;
-
- default:
- assert (!IS_EPSILON_NODE (node->token.type));
- dfa->nexts[idx] = node->next->node_idx;
- break;
+ if (dfa->nodes[idx].type == OP_DUP_ASTERISK
+ || 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);
+ }
+ 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);
+ else
+ assert (!IS_EPSILON_NODE (dfa->nodes[idx].type));
}
-
- return err;
}
/* Duplicate the epsilon closure of the node ROOT_NODE.
@@ -1407,10 +1452,13 @@ link_nfa_nodes (void *extra, bin_tree_t *node)
to their own constraint. */
static reg_errcode_t
-internal_function
-duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
- int root_node, unsigned int init_constraint)
+duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
+ init_constraint)
+ re_dfa_t *dfa;
+ int top_org_node, top_clone_node, root_node;
+ unsigned int init_constraint;
{
+ reg_errcode_t err;
int org_node, clone_node, ret;
unsigned int constraint = init_constraint;
for (org_node = top_org_node, clone_node = top_clone_node;;)
@@ -1424,9 +1472,9 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
edests of the back reference. */
org_dest = dfa->nexts[org_node];
re_node_set_empty (dfa->edests + clone_node);
- clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
- return REG_ESPACE;
+ 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))
@@ -1462,9 +1510,9 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
}
constraint |= dfa->nodes[org_node].opr.ctx_type;
}
- clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
- return REG_ESPACE;
+ 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;
@@ -1472,7 +1520,7 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
else /* dfa->edests[org_node].nelem == 2 */
{
/* In case of the node can epsilon-transit, and it has two
- destinations. In the bin_tree_t and DFA, that's '|' and '*'. */
+ destinations. E.g. '|', '*', '+', '?'. */
org_dest = dfa->edests[org_node].elems[0];
re_node_set_empty (dfa->edests + clone_node);
/* Search for a duplicated node which satisfies the constraint. */
@@ -1480,10 +1528,9 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
if (clone_dest == -1)
{
/* There are no such a duplicated node, create a new one. */
- reg_errcode_t err;
- clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
- return REG_ESPACE;
+ 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;
@@ -1502,9 +1549,9 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
}
org_dest = dfa->edests[org_node].elems[1];
- clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
- return REG_ESPACE;
+ 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;
@@ -1519,8 +1566,10 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
satisfies the constraint CONSTRAINT. */
static int
-search_duplicated_node (const re_dfa_t *dfa, int org_node,
- unsigned int constraint)
+search_duplicated_node (dfa, org_node, constraint)
+ re_dfa_t *dfa;
+ int org_node;
+ unsigned int constraint;
{
int idx;
for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
@@ -1533,51 +1582,54 @@ search_duplicated_node (const re_dfa_t *dfa, int org_node,
}
/* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
- Return the index of the new node, or -1 if insufficient storage is
- available. */
+ The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
+ otherwise return the error code. */
-static int
-duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint)
+static reg_errcode_t
+duplicate_node (new_idx, dfa, org_idx, constraint)
+ re_dfa_t *dfa;
+ int *new_idx, org_idx;
+ unsigned int constraint;
{
- int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
- if (BE (dup_idx != -1, 1))
- {
- dfa->nodes[dup_idx].constraint = constraint;
- if (dfa->nodes[org_idx].type == ANCHOR)
- dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
- dfa->nodes[dup_idx].duplicated = 1;
-
- /* Store the index of the original node. */
- dfa->org_indices[dup_idx] = org_idx;
- }
- return dup_idx;
+ int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx], 1);
+ if (BE (dup_idx == -1, 0))
+ return REG_ESPACE;
+ dfa->nodes[dup_idx].constraint = constraint;
+ if (dfa->nodes[org_idx].type == ANCHOR)
+ dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
+ dfa->nodes[dup_idx].duplicated = 1;
+ re_node_set_init_empty (dfa->edests + dup_idx);
+ re_node_set_init_empty (dfa->eclosures + dup_idx);
+ re_node_set_init_empty (dfa->inveclosures + dup_idx);
+
+ /* Store the index of the original node. */
+ dfa->org_indices[dup_idx] = org_idx;
+ *new_idx = dup_idx;
+ return REG_NOERROR;
}
-static reg_errcode_t
-calc_inveclosure (re_dfa_t *dfa)
+static void
+calc_inveclosure (dfa)
+ re_dfa_t *dfa;
{
- int src, idx, ret;
- for (idx = 0; idx < dfa->nodes_len; ++idx)
- re_node_set_init_empty (dfa->inveclosures + idx);
-
+ int src, idx, dest;
for (src = 0; src < dfa->nodes_len; ++src)
{
- int *elems = dfa->eclosures[src].elems;
+ if (dfa->nodes[src].type == OP_DELETED_SUBEXP)
+ continue;
for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
{
- ret = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
- if (BE (ret == -1, 0))
- return REG_ESPACE;
+ dest = dfa->eclosures[src].elems[idx];
+ re_node_set_insert_last (dfa->inveclosures + dest, src);
}
}
-
- return REG_NOERROR;
}
/* Calculate "eclosure" for all the node in DFA. */
static reg_errcode_t
-calc_eclosure (re_dfa_t *dfa)
+calc_eclosure (dfa)
+ re_dfa_t *dfa;
{
int node_idx, incomplete;
#ifdef DEBUG
@@ -1600,6 +1652,8 @@ calc_eclosure (re_dfa_t *dfa)
#ifdef DEBUG
assert (dfa->eclosures[node_idx].nelem != -1);
#endif
+ if (dfa->nodes[node_idx].type == OP_DELETED_SUBEXP)
+ continue;
/* If we have already calculated, skip it. */
if (dfa->eclosures[node_idx].nelem != 0)
@@ -1621,7 +1675,10 @@ calc_eclosure (re_dfa_t *dfa)
/* Calculate epsilon closure of NODE. */
static reg_errcode_t
-calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
+calc_eclosure_iter (new_set, dfa, node, root)
+ re_node_set *new_set;
+ re_dfa_t *dfa;
+ int node, root;
{
reg_errcode_t err;
unsigned int constraint;
@@ -1644,6 +1701,8 @@ calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
&& dfa->edests[node].nelem
&& !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
{
+ int org_node, cur_node;
+ org_node = cur_node = node;
err = duplicate_node_closure (dfa, node, node, node, constraint);
if (BE (err != REG_NOERROR, 0))
return err;
@@ -1699,8 +1758,10 @@ calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
We must not use this function inside bracket expressions. */
static void
-internal_function
-fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
+fetch_token (result, input, syntax)
+ re_token_t *result;
+ re_string_t *input;
+ reg_syntax_t syntax;
{
re_string_skip_bytes (input, peek_token (result, input, syntax));
}
@@ -1709,8 +1770,10 @@ fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
We must not use this function inside bracket expressions. */
static int
-internal_function
-peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
+peek_token (token, input, syntax)
+ re_token_t *token;
+ re_string_t *input;
+ reg_syntax_t syntax;
{
unsigned char c;
@@ -1796,7 +1859,7 @@ peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.ctx_type = NOT_WORD_DELIM;
+ token->opr.ctx_type = INSIDE_WORD;
}
break;
case 'w':
@@ -1948,8 +2011,10 @@ peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
We must not use this function out of bracket expressions. */
static int
-internal_function
-peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
+peek_token_bracket (token, input, syntax)
+ re_token_t *token;
+ re_string_t *input;
+ reg_syntax_t syntax;
{
unsigned char c;
if (re_string_eoi (input))
@@ -2045,8 +2110,11 @@ peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
EOR means end of regular expression. */
static bin_tree_t *
-parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
- reg_errcode_t *err)
+parse (regexp, preg, syntax, err)
+ re_string_t *regexp;
+ regex_t *preg;
+ reg_syntax_t syntax;
+ reg_errcode_t *err;
{
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
bin_tree_t *tree, *eor, *root;
@@ -2056,9 +2124,9 @@ parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
if (BE (*err != REG_NOERROR && tree == NULL, 0))
return NULL;
- eor = create_tree (dfa, NULL, NULL, END_OF_RE);
+ eor = re_dfa_add_tree_node (dfa, NULL, NULL, &current_token);
if (tree != NULL)
- root = create_tree (dfa, tree, eor, CONCAT);
+ root = create_tree (dfa, tree, eor, CONCAT, 0);
else
root = eor;
if (BE (eor == NULL || root == NULL, 0))
@@ -2079,8 +2147,13 @@ parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
ALT means alternative, which represents the operator `|'. */
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)
+parse_reg_exp (regexp, preg, token, syntax, nest, err)
+ re_string_t *regexp;
+ regex_t *preg;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ int nest;
+ reg_errcode_t *err;
{
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
bin_tree_t *tree, *branch = NULL;
@@ -2090,6 +2163,7 @@ parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
while (token->type == OP_ALT)
{
+ re_token_t alt_token = *token;
fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
if (token->type != OP_ALT && token->type != END_OF_RE
&& (nest == 0 || token->type != OP_CLOSE_SUBEXP))
@@ -2100,12 +2174,13 @@ parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
}
else
branch = NULL;
- tree = create_tree (dfa, tree, branch, OP_ALT);
+ tree = re_dfa_add_tree_node (dfa, tree, branch, &alt_token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
return NULL;
}
+ dfa->has_plural_match = 1;
}
return tree;
}
@@ -2120,8 +2195,13 @@ parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
CAT means concatenation. */
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)
+parse_branch (regexp, preg, token, syntax, nest, err)
+ re_string_t *regexp;
+ regex_t *preg;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ int nest;
+ reg_errcode_t *err;
{
bin_tree_t *tree, *exp;
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -2139,7 +2219,7 @@ parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
}
if (tree != NULL && exp != NULL)
{
- tree = create_tree (dfa, tree, exp, CONCAT);
+ tree = create_tree (dfa, tree, exp, CONCAT, 0);
if (tree == NULL)
{
*err = REG_ESPACE;
@@ -2160,15 +2240,20 @@ parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
*/
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)
+parse_expression (regexp, preg, token, syntax, nest, err)
+ re_string_t *regexp;
+ regex_t *preg;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ int nest;
+ reg_errcode_t *err;
{
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
bin_tree_t *tree;
switch (token->type)
{
case CHARACTER:
- tree = create_token_tree (dfa, NULL, NULL, token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2182,8 +2267,8 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
{
bin_tree_t *mbc_remain;
fetch_token (token, regexp, syntax);
- mbc_remain = create_token_tree (dfa, NULL, NULL, token);
- tree = create_tree (dfa, tree, mbc_remain, CONCAT);
+ mbc_remain = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+ tree = create_tree (dfa, tree, mbc_remain, CONCAT, 0);
if (BE (mbc_remain == NULL || tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2210,7 +2295,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
return NULL;
}
dfa->used_bkref_map |= 1 << token->opr.idx;
- tree = create_token_tree (dfa, NULL, NULL, token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2255,7 +2340,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
token->type = CHARACTER;
/* mb_partial and word_char bits should be initialized already
by peek_token. */
- tree = create_token_tree (dfa, NULL, NULL, token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2264,27 +2349,18 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
break;
case ANCHOR:
if ((token->opr.ctx_type
- & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
+ & (WORD_DELIM | INSIDE_WORD | WORD_FIRST | WORD_LAST))
&& dfa->word_ops_used == 0)
init_word_char (dfa);
- if (token->opr.ctx_type == WORD_DELIM
- || token->opr.ctx_type == NOT_WORD_DELIM)
+ if (token->opr.ctx_type == WORD_DELIM)
{
bin_tree_t *tree_first, *tree_last;
- if (token->opr.ctx_type == WORD_DELIM)
- {
- token->opr.ctx_type = WORD_FIRST;
- tree_first = create_token_tree (dfa, NULL, NULL, token);
- token->opr.ctx_type = WORD_LAST;
- }
- else
- {
- token->opr.ctx_type = INSIDE_WORD;
- tree_first = create_token_tree (dfa, NULL, NULL, token);
- token->opr.ctx_type = INSIDE_NOTWORD;
- }
- tree_last = create_token_tree (dfa, NULL, NULL, token);
- tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
+ token->opr.ctx_type = WORD_FIRST;
+ tree_first = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+ token->opr.ctx_type = WORD_LAST;
+ tree_last = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+ token->type = OP_ALT;
+ tree = re_dfa_add_tree_node (dfa, tree_first, tree_last, token);
if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2293,7 +2369,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
}
else
{
- tree = create_token_tree (dfa, NULL, NULL, token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2307,7 +2383,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
fetch_token (token, regexp, syntax);
return tree;
case OP_PERIOD:
- tree = create_token_tree (dfa, NULL, NULL, token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
if (BE (tree == NULL, 0))
{
*err = REG_ESPACE;
@@ -2363,6 +2439,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
*err = REG_BADRPT;
return NULL;
}
+ dfa->has_plural_match = 1;
}
return tree;
@@ -2376,14 +2453,26 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
*/
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)
+parse_sub_exp (regexp, preg, token, syntax, nest, err)
+ re_string_t *regexp;
+ regex_t *preg;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ int nest;
+ reg_errcode_t *err;
{
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
- bin_tree_t *tree;
+ bin_tree_t *tree, *left_par, *right_par;
size_t cur_nsub;
cur_nsub = preg->re_nsub++;
+ left_par = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+ if (BE (left_par == NULL, 0))
+ {
+ *err = REG_ESPACE;
+ return NULL;
+ }
+ dfa->nodes[left_par->node_idx].opr.idx = cur_nsub;
fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
/* The subexpression may be a null string. */
@@ -2392,31 +2481,41 @@ parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
else
{
tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
- if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
- *err = REG_EPAREN;
- if (BE (*err != REG_NOERROR, 0))
+ if (BE (*err != REG_NOERROR && tree == NULL, 0))
return NULL;
}
-
- if (cur_nsub <= '9' - '1')
- dfa->completed_bkref_map |= 1 << cur_nsub;
-
- tree = create_tree (dfa, tree, NULL, SUBEXP);
- if (BE (tree == NULL, 0))
+ if (BE (token->type != OP_CLOSE_SUBEXP, 0))
+ {
+ *err = REG_EPAREN;
+ return NULL;
+ }
+ right_par = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+ dfa->completed_bkref_map |= 1 << cur_nsub;
+ tree = ((tree == NULL) ? right_par
+ : create_tree (dfa, tree, right_par, CONCAT, 0));
+ tree = create_tree (dfa, left_par, tree, CONCAT, 0);
+ if (BE (right_par == NULL || tree == NULL, 0))
{
*err = REG_ESPACE;
return NULL;
}
- tree->token.opr.idx = cur_nsub;
+ dfa->nodes[right_par->node_idx].opr.idx = cur_nsub;
+
return tree;
}
/* This function parse repetition operators like "*", "+", "{1,3}" etc. */
static bin_tree_t *
-parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
- re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
+parse_dup_op (elem, regexp, dfa, token, syntax, err)
+ bin_tree_t *elem;
+ re_string_t *regexp;
+ re_dfa_t *dfa;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ reg_errcode_t *err;
{
+ re_token_t dup_token;
bin_tree_t *tree = NULL, *old_tree = NULL;
int i, start, end, start_idx = re_string_cur_idx (regexp);
re_token_t start_token = *token;
@@ -2479,13 +2578,9 @@ parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
fetch_token (token, regexp, syntax);
- if (BE (elem == NULL, 0))
+ /* Treat "<re>{0}*" etc. as "<re>{0}". */
+ if (BE (elem == NULL || (start == 0 && end == 0), 0))
return NULL;
- if (BE (start == 0 && end == 0, 0))
- {
- postorder (elem, free_tree, NULL);
- return NULL;
- }
/* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
if (BE (start > 0, 0))
@@ -2494,7 +2589,7 @@ parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
for (i = 2; i <= start; ++i)
{
elem = duplicate_tree (elem, dfa);
- tree = create_tree (dfa, tree, elem, CONCAT);
+ tree = create_tree (dfa, tree, elem, CONCAT, 0);
if (BE (elem == NULL || tree == NULL, 0))
goto parse_dup_op_espace;
}
@@ -2509,10 +2604,9 @@ parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
else
old_tree = NULL;
- if (elem->token.type == SUBEXP)
- postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
-
- tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
+ mark_opt_subexp (elem, dfa);
+ dup_token.type = (end == -1 ? OP_DUP_ASTERISK : OP_DUP_QUESTION);
+ tree = re_dfa_add_tree_node (dfa, elem, NULL, &dup_token);
if (BE (tree == NULL, 0))
goto parse_dup_op_espace;
@@ -2522,17 +2616,17 @@ parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
for (i = start + 2; i <= end; ++i)
{
elem = duplicate_tree (elem, dfa);
- tree = create_tree (dfa, tree, elem, CONCAT);
+ tree = create_tree (dfa, tree, elem, CONCAT, 0);
if (BE (elem == NULL || tree == NULL, 0))
goto parse_dup_op_espace;
- tree = create_tree (dfa, tree, NULL, OP_ALT);
+ tree = re_dfa_add_tree_node (dfa, tree, NULL, &dup_token);
if (BE (tree == NULL, 0))
goto parse_dup_op_espace;
}
if (old_tree)
- tree = create_tree (dfa, old_tree, tree, CONCAT);
+ tree = create_tree (dfa, old_tree, tree, CONCAT, 0);
return tree;
@@ -2554,14 +2648,15 @@ parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
update it. */
static reg_errcode_t
-internal_function
# ifdef RE_ENABLE_I18N
-build_range_exp (bitset_t sbcset, re_charset_t *mbcset, int *range_alloc,
- bracket_elem_t *start_elem, bracket_elem_t *end_elem)
+build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
+ re_charset_t *mbcset;
+ int *range_alloc;
# else /* not RE_ENABLE_I18N */
-build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
- bracket_elem_t *end_elem)
+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;
{
unsigned int start_ch, end_ch;
/* Equivalence Classes and Character Classes can't be a range start/end. */
@@ -2580,9 +2675,7 @@ build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
# ifdef RE_ENABLE_I18N
{
- wchar_t wc;
- wint_t start_wc;
- wint_t end_wc;
+ wchar_t wc, start_wc, end_wc;
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
@@ -2675,13 +2768,15 @@ build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
pointer argument since we may update it. */
static reg_errcode_t
-internal_function
# ifdef RE_ENABLE_I18N
-build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
- int *coll_sym_alloc, const unsigned char *name)
+build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
+ re_charset_t *mbcset;
+ int *coll_sym_alloc;
# else /* not RE_ENABLE_I18N */
-build_collating_symbol (bitset_t sbcset, const unsigned char *name)
+build_collating_symbol (sbcset, name)
# endif /* not RE_ENABLE_I18N */
+ re_bitset_ptr_t sbcset;
+ const unsigned char *name;
{
size_t name_len = strlen ((const char *) name);
if (BE (name_len != 1, 0))
@@ -2698,8 +2793,12 @@ build_collating_symbol (bitset_t sbcset, const unsigned char *name)
"[[.a-a.]]" etc. */
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)
+parse_bracket_exp (regexp, dfa, token, syntax, err)
+ re_string_t *regexp;
+ re_dfa_t *dfa;
+ re_token_t *token;
+ reg_syntax_t syntax;
+ reg_errcode_t *err;
{
#ifdef _LIBC
const unsigned char *collseqmb;
@@ -2721,28 +2820,23 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
{
int32_t hash = elem_hash ((const char *) name, name_len);
int32_t elem = hash % table_size;
- if (symb_table[2 * elem] != 0)
- {
- int32_t second = hash % (table_size - 2) + 1;
-
- do
+ 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)
{
- /* 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;
+ /* Yep, this is the entry. */
+ break;
}
- while (symb_table[2 * elem] != 0);
+
+ /* Next entry. */
+ elem += second;
}
return elem;
}
@@ -2824,7 +2918,7 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
re_charset_t *mbcset;
int *range_alloc;
- bitset_t sbcset;
+ re_bitset_ptr_t sbcset;
bracket_elem_t *start_elem, *end_elem;
{
unsigned int ch;
@@ -2907,7 +3001,7 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
re_charset_t *mbcset;
int *coll_sym_alloc;
- bitset_t sbcset;
+ re_bitset_ptr_t sbcset;
const unsigned char *name;
{
int32_t elem, idx;
@@ -2984,7 +3078,7 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
/*
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);
@@ -2992,7 +3086,7 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
_NL_COLLATE_SYMB_EXTRAMB);
}
#endif
- sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
+ sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
#ifdef RE_ENABLE_I18N
mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
#endif /* RE_ENABLE_I18N */
@@ -3019,7 +3113,7 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
#endif /* not RE_ENABLE_I18N */
non_match = 1;
if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
- bitset_set (sbcset, '\n');
+ 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))
@@ -3188,59 +3282,57 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
/* Ensure only single byte characters are set. */
if (dfa->mb_cur_max > 1)
bitset_mask (sbcset, dfa->sb_char);
+#endif /* RE_ENABLE_I18N */
+
+ /* Build a tree for simple bracket. */
+ br_token.type = SIMPLE_BRACKET;
+ br_token.opr.sbcset = sbcset;
+ work_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
+ if (BE (work_tree == NULL, 0))
+ goto parse_bracket_exp_espace;
+#ifdef RE_ENABLE_I18N
if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
|| mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
|| mbcset->non_match)))
{
+ re_token_t alt_token;
bin_tree_t *mbc_tree;
int sbc_idx;
/* Build a tree for complex bracket. */
dfa->has_mb_node = 1;
- br_token.type = COMPLEX_BRACKET;
- br_token.opr.mbcset = mbcset;
- mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
- if (BE (mbc_tree == NULL, 0))
- goto parse_bracket_exp_espace;
- for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
+ for (sbc_idx = 0; sbc_idx < BITSET_UINTS; ++sbc_idx)
if (sbcset[sbc_idx])
break;
/* If there are no bits set in sbcset, there is no point
of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
- if (sbc_idx < BITSET_WORDS)
- {
- /* Build a tree for simple bracket. */
- br_token.type = SIMPLE_BRACKET;
- br_token.opr.sbcset = sbcset;
- work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
- if (BE (work_tree == NULL, 0))
- goto parse_bracket_exp_espace;
-
- /* Then join them by ALT node. */
- work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
- if (BE (work_tree == NULL, 0))
- goto parse_bracket_exp_espace;
- }
- else
+ if (sbc_idx == BITSET_UINTS)
{
re_free (sbcset);
- work_tree = mbc_tree;
+ dfa->nodes[work_tree->node_idx].type = COMPLEX_BRACKET;
+ dfa->nodes[work_tree->node_idx].opr.mbcset = mbcset;
+ return work_tree;
}
+ br_token.type = COMPLEX_BRACKET;
+ br_token.opr.mbcset = mbcset;
+ mbc_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
+ if (BE (mbc_tree == NULL, 0))
+ goto parse_bracket_exp_espace;
+ /* Then join them by ALT node. */
+ alt_token.type = OP_ALT;
+ dfa->has_plural_match = 1;
+ work_tree = re_dfa_add_tree_node (dfa, work_tree, mbc_tree, &alt_token);
+ if (BE (mbc_tree != NULL, 1))
+ return work_tree;
}
else
-#endif /* not RE_ENABLE_I18N */
{
-#ifdef RE_ENABLE_I18N
free_charset (mbcset);
-#endif
- /* Build a tree for simple bracket. */
- br_token.type = SIMPLE_BRACKET;
- br_token.opr.sbcset = sbcset;
- work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
- if (BE (work_tree == NULL, 0))
- goto parse_bracket_exp_espace;
+ return work_tree;
}
+#else /* not RE_ENABLE_I18N */
return work_tree;
+#endif /* not RE_ENABLE_I18N */
parse_bracket_exp_espace:
*err = REG_ESPACE;
@@ -3255,9 +3347,15 @@ parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
/* Parse an element in the bracket expression. */
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, int accept_hyphen)
+parse_bracket_element (elem, regexp, token, token_len, dfa, syntax,
+ accept_hyphen)
+ bracket_elem_t *elem;
+ re_string_t *regexp;
+ re_token_t *token;
+ int token_len;
+ re_dfa_t *dfa;
+ reg_syntax_t syntax;
+ int accept_hyphen;
{
#ifdef RE_ENABLE_I18N
int cur_char_size;
@@ -3295,8 +3393,10 @@ parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
[=<equivalent_class>=]. */
static reg_errcode_t
-parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
- re_token_t *token)
+parse_bracket_symbol (elem, regexp, token)
+ bracket_elem_t *elem;
+ re_string_t *regexp;
+ re_token_t *token;
{
unsigned char ch, delim = token->opr.c;
int i = 0;
@@ -3343,13 +3443,16 @@ parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
static reg_errcode_t
#ifdef RE_ENABLE_I18N
-build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
- int *equiv_class_alloc, const unsigned char *name)
+build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)
+ re_charset_t *mbcset;
+ int *equiv_class_alloc;
#else /* not RE_ENABLE_I18N */
-build_equiv_class (bitset_t sbcset, const unsigned char *name)
+build_equiv_class (sbcset, name)
#endif /* not RE_ENABLE_I18N */
+ re_bitset_ptr_t sbcset;
+ const unsigned char *name;
{
-#ifdef _LIBC
+#if defined _LIBC
uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
if (nrules != 0)
{
@@ -3435,13 +3538,16 @@ build_equiv_class (bitset_t sbcset, const unsigned char *name)
static reg_errcode_t
#ifdef RE_ENABLE_I18N
-build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
- re_charset_t *mbcset, int *char_class_alloc,
- const unsigned char *class_name, reg_syntax_t syntax)
+build_charclass (trans, sbcset, mbcset, char_class_alloc, class_name, syntax)
+ re_charset_t *mbcset;
+ int *char_class_alloc;
#else /* not RE_ENABLE_I18N */
-build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
- const unsigned char *class_name, reg_syntax_t syntax)
+build_charclass (trans, sbcset, class_name, syntax)
#endif /* not RE_ENABLE_I18N */
+ unsigned RE_TRANSLATE_TYPE trans;
+ re_bitset_ptr_t sbcset;
+ const unsigned char *class_name;
+ reg_syntax_t syntax;
{
int i;
const char *name = (const char *) class_name;
@@ -3471,45 +3577,39 @@ build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
#endif /* RE_ENABLE_I18N */
#define BUILD_CHARCLASS_LOOP(ctype_func) \
- do { \
- if (BE (trans != NULL, 0)) \
- { \
- for (i = 0; i < SBC_MAX; ++i) \
- if (ctype_func (i)) \
- bitset_set (sbcset, trans[i]); \
- } \
- else \
+ for (i = 0; i < SBC_MAX; ++i) \
{ \
- for (i = 0; i < SBC_MAX; ++i) \
- if (ctype_func (i)) \
- bitset_set (sbcset, i); \
- } \
- } while (0)
+ if (ctype_func (i)) \
+ { \
+ int ch = trans ? trans[i] : i; \
+ bitset_set (sbcset, ch); \
+ } \
+ }
if (strcmp (name, "alnum") == 0)
- BUILD_CHARCLASS_LOOP (isalnum);
+ BUILD_CHARCLASS_LOOP (isalnum)
else if (strcmp (name, "cntrl") == 0)
- BUILD_CHARCLASS_LOOP (iscntrl);
+ BUILD_CHARCLASS_LOOP (iscntrl)
else if (strcmp (name, "lower") == 0)
- BUILD_CHARCLASS_LOOP (islower);
+ BUILD_CHARCLASS_LOOP (islower)
else if (strcmp (name, "space") == 0)
- BUILD_CHARCLASS_LOOP (isspace);
+ BUILD_CHARCLASS_LOOP (isspace)
else if (strcmp (name, "alpha") == 0)
- BUILD_CHARCLASS_LOOP (isalpha);
+ BUILD_CHARCLASS_LOOP (isalpha)
else if (strcmp (name, "digit") == 0)
- BUILD_CHARCLASS_LOOP (isdigit);
+ BUILD_CHARCLASS_LOOP (isdigit)
else if (strcmp (name, "print") == 0)
- BUILD_CHARCLASS_LOOP (isprint);
+ BUILD_CHARCLASS_LOOP (isprint)
else if (strcmp (name, "upper") == 0)
- BUILD_CHARCLASS_LOOP (isupper);
+ BUILD_CHARCLASS_LOOP (isupper)
else if (strcmp (name, "blank") == 0)
- BUILD_CHARCLASS_LOOP (isblank);
+ BUILD_CHARCLASS_LOOP (isblank)
else if (strcmp (name, "graph") == 0)
- BUILD_CHARCLASS_LOOP (isgraph);
+ BUILD_CHARCLASS_LOOP (isgraph)
else if (strcmp (name, "punct") == 0)
- BUILD_CHARCLASS_LOOP (ispunct);
+ BUILD_CHARCLASS_LOOP (ispunct)
else if (strcmp (name, "xdigit") == 0)
- BUILD_CHARCLASS_LOOP (isxdigit);
+ BUILD_CHARCLASS_LOOP (isxdigit)
else
return REG_ECTYPE;
@@ -3517,10 +3617,13 @@ build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
}
static bin_tree_t *
-build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
- const unsigned char *class_name,
- const unsigned char *extra, int non_match,
- reg_errcode_t *err)
+build_charclass_op (dfa, trans, class_name, extra, non_match, err)
+ re_dfa_t *dfa;
+ unsigned RE_TRANSLATE_TYPE trans;
+ const unsigned char *class_name;
+ const unsigned char *extra;
+ int non_match;
+ reg_errcode_t *err;
{
re_bitset_ptr_t sbcset;
#ifdef RE_ENABLE_I18N
@@ -3531,7 +3634,7 @@ build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
re_token_t br_token;
bin_tree_t *tree;
- sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
+ sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
#ifdef RE_ENABLE_I18N
mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
#endif /* RE_ENABLE_I18N */
@@ -3549,6 +3652,10 @@ build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
if (non_match)
{
#ifdef RE_ENABLE_I18N
+ /*
+ if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
+ bitset_set(cset->sbcset, '\0');
+ */
mbcset->non_match = 1;
#endif /* not RE_ENABLE_I18N */
}
@@ -3586,23 +3693,26 @@ build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
/* Build a tree for simple bracket. */
br_token.type = SIMPLE_BRACKET;
br_token.opr.sbcset = sbcset;
- tree = create_token_tree (dfa, NULL, NULL, &br_token);
+ tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
if (BE (tree == NULL, 0))
goto build_word_op_espace;
#ifdef RE_ENABLE_I18N
if (dfa->mb_cur_max > 1)
{
+ re_token_t alt_token;
bin_tree_t *mbc_tree;
/* Build a tree for complex bracket. */
br_token.type = COMPLEX_BRACKET;
br_token.opr.mbcset = mbcset;
dfa->has_mb_node = 1;
- mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
+ mbc_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
if (BE (mbc_tree == NULL, 0))
goto build_word_op_espace;
/* Then join them by ALT node. */
- tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
+ alt_token.type = OP_ALT;
+ dfa->has_plural_match = 1;
+ tree = re_dfa_add_tree_node (dfa, tree, mbc_tree, &alt_token);
if (BE (mbc_tree != NULL, 1))
return tree;
}
@@ -3630,7 +3740,10 @@ build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
Return -2, If an error is occured. */
static int
-fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
+fetch_number (input, token, syntax)
+ re_string_t *input;
+ re_token_t *token;
+ reg_syntax_t syntax;
{
int num = -1;
unsigned char c;
@@ -3670,17 +3783,12 @@ free_charset (re_charset_t *cset)
/* Create a tree node. */
static bin_tree_t *
-create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
- re_token_type_t type)
-{
- re_token_t t;
- t.type = type;
- return create_token_tree (dfa, left, right, &t);
-}
-
-static bin_tree_t *
-create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
- const re_token_t *token)
+create_tree (dfa, left, right, type, index)
+ re_dfa_t *dfa;
+ bin_tree_t *left;
+ bin_tree_t *right;
+ re_token_type_t type;
+ int index;
{
bin_tree_t *tree;
if (BE (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE, 0))
@@ -3698,12 +3806,11 @@ create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
tree->parent = NULL;
tree->left = left;
tree->right = right;
- tree->token = *token;
- tree->token.duplicated = 0;
- tree->token.opt_subexp = 0;
- tree->first = NULL;
- tree->next = NULL;
- tree->node_idx = -1;
+ tree->type = type;
+ tree->node_idx = index;
+ tree->first = -1;
+ tree->next = -1;
+ re_node_set_init_empty (&tree->eclosure);
if (left != NULL)
left->parent = tree;
@@ -3712,85 +3819,103 @@ create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
return tree;
}
-/* Mark the tree SRC as an optional subexpression.
- To be called from preorder or postorder. */
+/* Create both a DFA node and a tree for it. */
-static reg_errcode_t
-mark_opt_subexp (void *extra, bin_tree_t *node)
+static bin_tree_t *
+re_dfa_add_tree_node (dfa, left, right, token)
+ re_dfa_t *dfa;
+ bin_tree_t *left;
+ bin_tree_t *right;
+ const re_token_t *token;
{
- int idx = (int) (long) extra;
- if (node->token.type == SUBEXP && node->token.opr.idx == idx)
- node->token.opt_subexp = 1;
+ int new_idx = re_dfa_add_node (dfa, *token, 0);
- return REG_NOERROR;
+ if (new_idx == -1)
+ return NULL;
+
+ return create_tree (dfa, left, right, 0, new_idx);
}
-/* Free the allocated memory inside NODE. */
+/* Mark the tree SRC as an optional subexpression. */
static void
-free_token (re_token_t *node)
+mark_opt_subexp (src, dfa)
+ const bin_tree_t *src;
+ re_dfa_t *dfa;
{
-#ifdef RE_ENABLE_I18N
- if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
- free_charset (node->opr.mbcset);
- else
-#endif /* RE_ENABLE_I18N */
- if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
- re_free (node->opr.sbcset);
+ /* Pass an OPT_SUBEXP_IDX which is != 1 if the duplicated tree is
+ a subexpression. */
+ if (src->type == CONCAT
+ && src->left->type == NON_TYPE
+ && dfa->nodes[src->left->node_idx].type == OP_OPEN_SUBEXP)
+ mark_opt_subexp_iter (src, dfa, dfa->nodes[src->left->node_idx].opr.idx);
}
-/* Worker function for tree walking. Free the allocated memory inside NODE
- and its children. */
-static reg_errcode_t
-free_tree (void *extra, bin_tree_t *node)
+/* Recursive tree walker for mark_opt_subexp. */
+
+static void
+mark_opt_subexp_iter (src, dfa, idx)
+ const bin_tree_t *src;
+ re_dfa_t *dfa;
+ int idx;
{
- free_token (&node->token);
- return REG_NOERROR;
+ int node_idx;
+
+ if (src->type == NON_TYPE)
+ {
+ node_idx = src->node_idx;
+ if ((dfa->nodes[node_idx].type == OP_OPEN_SUBEXP
+ || dfa->nodes[node_idx].type == OP_CLOSE_SUBEXP)
+ && dfa->nodes[node_idx].opr.idx == idx)
+ dfa->nodes[node_idx].opt_subexp = 1;
+ }
+
+ if (src->left != NULL)
+ mark_opt_subexp_iter (src->left, dfa, idx);
+
+ if (src->right != NULL)
+ mark_opt_subexp_iter (src->right, dfa, idx);
}
-/* Duplicate the node SRC, and return new node. This is a preorder
- visit similar to the one implemented by the generic visitor, but
- we need more infrastructure to maintain two parallel trees --- so,
- it's easier to duplicate. */
+/* Duplicate the node SRC, and return new node. */
static bin_tree_t *
-duplicate_tree (const bin_tree_t *root, re_dfa_t *dfa)
+duplicate_tree (src, dfa)
+ const bin_tree_t *src;
+ re_dfa_t *dfa;
{
- const bin_tree_t *node;
- bin_tree_t *dup_root;
- bin_tree_t **p_new = &dup_root, *dup_node = root->parent;
+ bin_tree_t *left = NULL, *right = NULL, *new_tree;
+ int new_node_idx;
+ /* Since node indies must be according to Post-order of the tree,
+ we must duplicate the left at first. */
+ if (src->left != NULL)
+ {
+ left = duplicate_tree (src->left, dfa);
+ if (left == NULL)
+ return NULL;
+ }
- for (node = root; ; )
+ /* Secondaly, duplicate the right. */
+ if (src->right != NULL)
{
- /* Create a new tree and link it back to the current parent. */
- *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
- if (*p_new == NULL)
+ right = duplicate_tree (src->right, dfa);
+ if (right == NULL)
return NULL;
- (*p_new)->parent = dup_node;
- (*p_new)->token.duplicated = 1;
- dup_node = *p_new;
+ }
- /* Go to the left node, or up and to the right. */
- if (node->left)
- {
- node = node->left;
- p_new = &dup_node->left;
- }
- else
- {
- const bin_tree_t *prev = NULL;
- while (node->right == prev || node->right == NULL)
- {
- prev = node;
- node = node->parent;
- dup_node = dup_node->parent;
- if (!node)
- return dup_root;
- }
- node = node->right;
- p_new = &dup_node->right;
- }
+ /* At last, duplicate itself. */
+ if (src->type == NON_TYPE)
+ {
+ 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))
+ return NULL;
}
+ else
+ new_node_idx = src->type;
+
+ new_tree = create_tree (dfa, left, right, src->type, new_node_idx);
+ return new_tree;
}