diff options
Diffstat (limited to 'posix')
| -rw-r--r-- | posix/Makefile | 13 | ||||
| -rw-r--r-- | posix/bug-regex19.c | 22 | ||||
| -rw-r--r-- | posix/execl.c | 50 | ||||
| -rw-r--r-- | posix/execle.c | 53 | ||||
| -rw-r--r-- | posix/execlp.c | 50 | ||||
| -rw-r--r-- | posix/execvp.c | 98 | ||||
| -rw-r--r-- | posix/getconf.c | 4 | ||||
| -rw-r--r-- | posix/regcomp.c | 970 | ||||
| -rw-r--r-- | posix/regex_internal.c | 72 | ||||
| -rw-r--r-- | posix/regex_internal.h | 33 | ||||
| -rw-r--r-- | posix/regexec.c | 50 | ||||
| -rw-r--r-- | posix/rxspencer/tests | 9 | ||||
| -rw-r--r-- | posix/tst-rxspencer.c | 20 | ||||
| -rw-r--r-- | posix/unistd.h | 2 |
14 files changed, 749 insertions, 697 deletions
diff --git a/posix/Makefile b/posix/Makefile index 149283c65d..3af9e6681d 100644 --- a/posix/Makefile +++ b/posix/Makefile @@ -1,4 +1,4 @@ -# Copyright (C) 1991-1999, 2000-2003, 2004 Free Software Foundation, Inc. +# Copyright (C) 1991-1999, 2000-2003, 2004, 2005 Free Software Foundation, Inc. # This file is part of the GNU C Library. # The GNU C Library is free software; you can redistribute it and/or @@ -140,16 +140,27 @@ CFLAGS-waitid.c = -fexceptions CFLAGS-waitpid.c = -fexceptions -fasynchronous-unwind-tables CFLAGS-getopt.c = -fexceptions CFLAGS-wordexp.c = -fexceptions +CFLAGS-wordexp.os = -fomit-frame-pointer CFLAGS-sysconf.c = -fexceptions -DGETCONF_DIR='"$(libexecdir)/getconf"' CFLAGS-pathconf.c = -fexceptions CFLAGS-fpathconf.c = -fexceptions CFLAGS-spawn.c = -fexceptions +CFLAGS-spawn.os = -fomit-frame-pointer CFLAGS-spawnp.c = -fexceptions +CFLAGS-spawnp.os = -fomit-frame-pointer CFLAGS-spawni.c = -fexceptions +CFLAGS-spawni.os = -fomit-frame-pointer CFLAGS-pause.c = -fexceptions CFLAGS-glob.c = $(uses-callbacks) -fexceptions CFLAGS-glob64.c = $(uses-callbacks) -fexceptions CFLAGS-getconf.c = -DGETCONF_DIR='"$(libexecdir)/getconf"' +CFLAGS-execve.os = -fomit-frame-pointer +CFLAGS-fexecve.os = -fomit-frame-pointer +CFLAGS-execv.os = -fomit-frame-pointer +CFLAGS-execle.os = -fomit-frame-pointer +CFLAGS-execl.os = -fomit-frame-pointer +CFLAGS-execvp.os = -fomit-frame-pointer +CFLAGS-execlp.os = -fomit-frame-pointer tstgetopt-ARGS = -a -b -cfoobar --required foobar --optional=bazbug \ --none random --col --color --colour diff --git a/posix/bug-regex19.c b/posix/bug-regex19.c index 4000b19b4d..3a173a6ca0 100644 --- a/posix/bug-regex19.c +++ b/posix/bug-regex19.c @@ -1,5 +1,5 @@ /* Regular expression tests. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2005 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Jakub Jelinek <jakub@redhat.com>, 2003. @@ -170,22 +170,22 @@ static struct test_s {ERE, "[^k]\\B[^k]", "kBk", 0, -1}, {ERE, "[^C]\\B[^C]", "CCCABA", 0, 3}, {ERE, "[^C]\\B[^C]", "CBC", 0, -1}, - {ERE, ".(\\b|\\B).", "=~AB", 0, 1}, + {ERE, ".(\\b|\\B).", "=~AB", 0, 0}, {ERE, ".(\\b|\\B).", "A=C", 0, 0}, {ERE, ".(\\b|\\B).", "ABC", 0, 0}, - {ERE, ".(\\b|\\B).", "=~\\!", 0, -1}, - {ERE, "[^k](\\b|\\B)[^k]", "=~AB", 0, 1}, + {ERE, ".(\\b|\\B).", "=~\\!", 0, 0}, + {ERE, "[^k](\\b|\\B)[^k]", "=~AB", 0, 0}, {ERE, "[^k](\\b|\\B)[^k]", "A=C", 0, 0}, {ERE, "[^k](\\b|\\B)[^k]", "ABC", 0, 0}, - {ERE, "[^k](\\b|\\B)[^k]", "=~kBD", 0, 3}, - {ERE, "[^k](\\b|\\B)[^k]", "=~\\!", 0, -1}, - {ERE, "[^k](\\b|\\B)[^k]", "=~kB", 0, -1}, - {ERE, "[^C](\\b|\\B)[^C]", "=~AB", 0, 1}, + {ERE, "[^k](\\b|\\B)[^k]", "=~kBD", 0, 0}, + {ERE, "[^k](\\b|\\B)[^k]", "=~\\!", 0, 0}, + {ERE, "[^k](\\b|\\B)[^k]", "=~kB", 0, 0}, + {ERE, "[^C](\\b|\\B)[^C]", "=~AB", 0, 0}, {ERE, "[^C](\\b|\\B)[^C]", "A=C", 0, 0}, {ERE, "[^C](\\b|\\B)[^C]", "ABC", 0, 0}, - {ERE, "[^C](\\b|\\B)[^C]", "=~CBD", 0, 3}, - {ERE, "[^C](\\b|\\B)[^C]", "=~\\!", 0, -1}, - {ERE, "[^C](\\b|\\B)[^C]", "=~CB", 0, -1}, + {ERE, "[^C](\\b|\\B)[^C]", "=~CBD", 0, 0}, + {ERE, "[^C](\\b|\\B)[^C]", "=~\\!", 0, 0}, + {ERE, "[^C](\\b|\\B)[^C]", "=~CB", 0, 0}, {ERE, "\\b([A]|[!]|.B)", "A=AC", 0, 0}, {ERE, "\\b([A]|[!]|.B)", "=AC", 0, 1}, {ERE, "\\b([A]|[!]|.B)", "!AC", 0, 1}, diff --git a/posix/execl.c b/posix/execl.c index 62fd45db58..12b59f9de3 100644 --- a/posix/execl.c +++ b/posix/execl.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991,92,94,97,98,99,2002 Free Software Foundation, Inc. +/* Copyright (C) 1991,92,94,97,98,99,2002,2005 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -16,10 +16,10 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ -#include <alloca.h> #include <unistd.h> #include <stdarg.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include <stackinfo.h> @@ -33,46 +33,44 @@ int execl (const char *path, const char *arg, ...) { - size_t argv_max = 1024; - const char **argv = alloca (argv_max * sizeof (const char *)); - unsigned int i; +#define INITIAL_ARGV_MAX 1024 + size_t argv_max = INITIAL_ARGV_MAX; + const char *initial_argv[INITIAL_ARGV_MAX]; + const char **argv = initial_argv; va_list args; argv[0] = arg; va_start (args, arg); - i = 0; + unsigned int i = 0; while (argv[i++] != NULL) { if (i == argv_max) { - const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *)); - -#ifndef _STACK_GROWS_UP - if ((char *) nptr + argv_max == (char *) argv) + argv_max *= 2; + const char **nptr = realloc (argv == initial_argv ? NULL : argv, + argv_max * sizeof (const char *)); + if (nptr == NULL) { - /* Stack grows down. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); - argv_max += i; + if (argv != initial_argv) + free (argv); + return -1; } - else -#endif -#ifndef _STACK_GROWS_DOWN - if ((char *) argv + i == (char *) nptr) - /* Stack grows up. */ - argv_max += i; - else -#endif - /* We have a hole in the stack. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); + if (argv == initial_argv) + /* We have to copy the already filled-in data ourselves. */ + memcpy (nptr, argv, i * sizeof (const char *)); + + argv = nptr; } argv[i] = va_arg (args, const char *); } va_end (args); - return __execve (path, (char *const *) argv, __environ); + int ret = __execve (path, (char *const *) argv, __environ); + if (argv != initial_argv) + free (argv); + + return ret; } libc_hidden_def (execl) diff --git a/posix/execle.c b/posix/execle.c index 2199ebeb74..70522ad2e5 100644 --- a/posix/execle.c +++ b/posix/execle.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991,97,98,99,2002 Free Software Foundation, Inc. +/* Copyright (C) 1991,97,98,99,2002,2005 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -16,10 +16,10 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ -#include <alloca.h> #include <unistd.h> #include <stdarg.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include <stackinfo.h> @@ -29,48 +29,45 @@ int execle (const char *path, const char *arg, ...) { - size_t argv_max = 1024; - const char **argv = alloca (argv_max * sizeof (const char *)); - const char *const *envp; - unsigned int i; +#define INITIAL_ARGV_MAX 1024 + size_t argv_max = INITIAL_ARGV_MAX; + const char *initial_argv[INITIAL_ARGV_MAX]; + const char **argv = initial_argv; va_list args; argv[0] = arg; va_start (args, arg); - i = 0; + unsigned int i = 0; while (argv[i++] != NULL) { if (i == argv_max) { - const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *)); - -#ifndef _STACK_GROWS_UP - if ((char *) nptr + argv_max == (char *) argv) + argv_max *= 2; + const char **nptr = realloc (argv == initial_argv ? NULL : argv, + argv_max * sizeof (const char *)); + if (nptr == NULL) { - /* Stack grows down. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); - argv_max += i; + if (argv != initial_argv) + free (argv); + return -1; } - else -#endif -#ifndef _STACK_GROWS_DOWN - if ((char *) argv + i == (char *) nptr) - /* Stack grows up. */ - argv_max += i; - else -#endif - /* We have a hole in the stack. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); + if (argv == initial_argv) + /* We have to copy the already filled-in data ourselves. */ + memcpy (nptr, argv, i * sizeof (const char *)); + + argv = nptr; } argv[i] = va_arg (args, const char *); } - envp = va_arg (args, const char *const *); + const char *const *envp = va_arg (args, const char *const *); va_end (args); - return __execve (path, (char *const *) argv, (char *const *) envp); + int ret = __execve (path, (char *const *) argv, (char *const *) envp); + if (argv != initial_argv) + free (argv); + + return ret; } libc_hidden_def (execle) diff --git a/posix/execlp.c b/posix/execlp.c index ba8fc74c90..66996a9367 100644 --- a/posix/execlp.c +++ b/posix/execlp.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991,93,96,97,98,99,2002 Free Software Foundation, Inc. +/* Copyright (C) 1991,93,96,97,98,99,2002,2005 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -16,10 +16,10 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ -#include <alloca.h> #include <unistd.h> #include <stdarg.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include <stackinfo.h> @@ -30,46 +30,44 @@ int execlp (const char *file, const char *arg, ...) { - size_t argv_max = 1024; - const char **argv = alloca (argv_max * sizeof (const char *)); - unsigned int i; +#define INITIAL_ARGV_MAX 1024 + size_t argv_max = INITIAL_ARGV_MAX; + const char *initial_argv[INITIAL_ARGV_MAX]; + const char **argv = initial_argv; va_list args; argv[0] = arg; va_start (args, arg); - i = 0; + unsigned int i = 0; while (argv[i++] != NULL) { if (i == argv_max) { - const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *)); - -#ifndef _STACK_GROWS_UP - if ((char *) nptr + argv_max == (char *) argv) + argv_max *= 2; + const char **nptr = realloc (argv == initial_argv ? NULL : argv, + argv_max * sizeof (const char *)); + if (nptr == NULL) { - /* Stack grows down. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); - argv_max += i; + if (argv != initial_argv) + free (argv); + return -1; } - else -#endif -#ifndef _STACK_GROWS_DOWN - if ((char *) argv + i == (char *) nptr) - /* Stack grows up. */ - argv_max += i; - else -#endif - /* We have a hole in the stack. */ - argv = (const char **) memcpy (nptr, argv, - i * sizeof (const char *)); + if (argv == initial_argv) + /* We have to copy the already filled-in data ourselves. */ + memcpy (nptr, argv, i * sizeof (const char *)); + + argv = nptr; } argv[i] = va_arg (args, const char *); } va_end (args); - return execvp (file, (char *const *) argv); + int ret = execvp (file, (char *const *) argv); + if (argv != initial_argv) + free (argv); + + return ret; } libc_hidden_def (execlp) diff --git a/posix/execvp.c b/posix/execvp.c index d6f60c02e7..9ccfd7fc22 100644 --- a/posix/execvp.c +++ b/posix/execvp.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991,92,1995-99,2002,2004 Free Software Foundation, Inc. +/* Copyright (C) 1991,92,1995-99,2002,2004,2005 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -18,6 +18,7 @@ #include <unistd.h> #include <stdarg.h> +#include <stdbool.h> #include <stdlib.h> #include <string.h> #include <errno.h> @@ -26,9 +27,9 @@ /* The file is accessible but it is not an executable file. Invoke the shell to interpret it as a script. */ -static void +static char ** internal_function -script_execute (const char *file, char *const argv[]) +allocate_scripts_argv (const char *file, char *const argv[]) { /* Count the arguments. */ int argc = 0; @@ -36,19 +37,19 @@ script_execute (const char *file, char *const argv[]) ; /* Construct an argument list for the shell. */ - { - char *new_argv[argc + 1]; - new_argv[0] = (char *) _PATH_BSHELL; - new_argv[1] = (char *) file; - while (argc > 1) - { - new_argv[argc] = argv[argc - 1]; - --argc; - } - - /* Execute the shell. */ - __execve (new_argv[0], new_argv, __environ); - } + char **new_argv = (char **) malloc ((argc + 1) * sizeof (char *)); + if (new_argv != NULL) + { + new_argv[0] = (char *) _PATH_BSHELL; + new_argv[1] = (char *) file; + while (argc > 1) + { + new_argv[argc] = argv[argc - 1]; + --argc; + } + } + + return new_argv; } @@ -66,42 +67,58 @@ execvp (file, argv) return -1; } + char **script_argv = NULL; + if (strchr (file, '/') != NULL) { /* Don't search when it contains a slash. */ __execve (file, argv, __environ); if (errno == ENOEXEC) - script_execute (file, argv); + { + script_argv = allocate_scripts_argv (file, argv); + if (script_argv != NULL) + { + __execve (script_argv[0], script_argv, __environ); + + free (script_argv); + } + } } else { - int got_eacces = 0; - char *path, *p, *name; - size_t len; - size_t pathlen; - - path = getenv ("PATH"); + char *path = getenv ("PATH"); + bool path_malloc = false; if (path == NULL) { /* There is no `PATH' in the environment. The default search path is the current directory followed by the path `confstr' returns for `_CS_PATH'. */ - len = confstr (_CS_PATH, (char *) NULL, 0); - path = (char *) __alloca (1 + len); + size_t len = confstr (_CS_PATH, (char *) NULL, 0); + path = (char *) malloc (1 + len); + if (path == NULL) + return -1; path[0] = ':'; (void) confstr (_CS_PATH, path + 1, len); + path_malloc = true; } - len = strlen (file) + 1; - pathlen = strlen (path); - name = __alloca (pathlen + len + 1); + size_t len = strlen (file) + 1; + size_t pathlen = strlen (path); + char *name = malloc (pathlen + len + 1); + if (name == NULL) + { + if (path_malloc) + free (path); + return -1; + } /* Copy the file name at the top. */ name = (char *) memcpy (name + pathlen + 1, file, len); /* And add the slash. */ *--name = '/'; - p = path; + bool got_eacces = false; + char *p = path; do { char *startp; @@ -120,7 +137,21 @@ execvp (file, argv) __execve (startp, argv, __environ); if (errno == ENOEXEC) - script_execute (startp, argv); + { + if (script_argv == NULL) + { + script_argv = allocate_scripts_argv (file, argv); + if (script_argv == NULL) + { + /* A possible EACCES error is not as important as + the ENOMEM. */ + got_eacces = false; + break; + } + } + + __execve (script_argv[0], script_argv, __environ); + } switch (errno) { @@ -128,7 +159,7 @@ execvp (file, argv) /* Record the we got a `Permission denied' error. If we end up finding no executable we can use, we want to diagnose that we did find one but were denied access. */ - got_eacces = 1; + got_eacces = true; case ENOENT: case ESTALE: case ENOTDIR: @@ -156,6 +187,11 @@ execvp (file, argv) /* At least one failure was due to permissions, so report that error. */ __set_errno (EACCES); + + free (script_argv); + free (name); + if (path_malloc) + free (path); } /* Return the error from the last attempt (probably ENOENT). */ diff --git a/posix/getconf.c b/posix/getconf.c index 4ce4f8e413..0cc0c0d7b5 100644 --- a/posix/getconf.c +++ b/posix/getconf.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991, 92, 1995-2003, 2004 Free Software Foundation, Inc. +/* Copyright (C) 1991, 92, 1995-2003, 2004, 2005 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -964,7 +964,7 @@ main (int argc, char *argv[]) Copyright (C) %s Free Software Foundation, Inc.\n\ This is free software; see the source for copying conditions. There is NO\n\ warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\ -"), "2004"); +"), "2005"); fprintf (stderr, gettext ("Written by %s.\n"), "Roland McGrath"); return 0; } diff --git a/posix/regcomp.c b/posix/regcomp.c index 5de5bf725a..1a5f7952c3 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 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>. @@ -33,19 +33,21 @@ static reg_errcode_t create_initial_state (re_dfa_t *dfa); #ifdef RE_ENABLE_I18N static void optimize_utf8 (re_dfa_t *dfa); #endif -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 analyze (regex_t *preg); +static reg_errcode_t create_initial_state (re_dfa_t *dfa); +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 reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node, int root_node, unsigned int constraint); @@ -56,7 +58,7 @@ static int search_duplicated_node (re_dfa_t *dfa, int org_node, 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 void calc_inveclosure (re_dfa_t *dfa); +static reg_errcode_t 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, @@ -138,14 +140,14 @@ static bin_tree_t *build_charclass_op (re_dfa_t *dfa, 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, 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)); + 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); static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa); -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); +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); /* 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. @@ -598,16 +600,7 @@ free_dfa_content (re_dfa_t *dfa) if (dfa->nodes) for (i = 0; i < dfa->nodes_len; ++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); - } + free_token (dfa->nodes + i); re_free (dfa->nexts); for (i = 0; i < dfa->nodes_len; ++i) { @@ -811,29 +804,17 @@ re_compile_internal (preg, pattern, length, syntax) 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); @@ -894,9 +875,9 @@ init_dfa (dfa, pat_len) codeset_name = nl_langinfo (CODESET); # else codeset_name = getenv ("LC_ALL"); - if (codeset_name == NULL || codeset[0] == '\0') + if (codeset_name == NULL || codeset_name[0] == '\0') codeset_name = getenv ("LC_CTYPE"); - if (codeset_name == NULL || codeset[0] == '\0') + if (codeset_name == NULL || codeset_name[0] == '\0') codeset_name = getenv ("LANG"); if (codeset_name == NULL) codeset_name = ""; @@ -998,7 +979,7 @@ create_initial_state (dfa) /* Initial states have the epsilon closure of the node which is the first node of the regular expression. */ - first = dfa->str_tree->first; + first = dfa->str_tree->first->node_idx; dfa->init_node = first; err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first); if (BE (err != REG_NOERROR, 0)) @@ -1104,10 +1085,11 @@ optimize_utf8 (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. */ for (i = 0x80 / UINT_BITS; i < BITSET_UINTS; ++i) @@ -1115,7 +1097,7 @@ optimize_utf8 (dfa) return; break; default: - return; + abort (); } if (mb_chars || has_period) @@ -1135,90 +1117,14 @@ optimize_utf8 (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 (dfa) - re_dfa_t *dfa; +analyze (preg) + regex_t *preg; { - int i; + re_dfa_t *dfa = (re_dfa_t *) preg->buffer; reg_errcode_t ret; /* Allocate arrays. */ @@ -1226,225 +1132,321 @@ analyze (dfa) 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 || dfa->inveclosures == NULL, 0)) + || dfa->eclosures == NULL, 0)) return REG_ESPACE; - /* Initialize them. */ - for (i = 0; i < dfa->nodes_len; ++i) + + dfa->subexp_map = re_malloc (int, preg->re_nsub); + if (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); + 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; + } } - ret = analyze_tree (dfa, dfa->str_tree); - if (BE (ret == REG_NOERROR, 1)) + 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 = calc_eclosure (dfa); - if (ret == REG_NOERROR) - calc_inveclosure (dfa); + dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len); + if (BE (dfa->inveclosures == NULL, 0)) + return REG_ESPACE; + ret = calc_inveclosure (dfa); } + return ret; } -/* Helper functions for analyze. - This function calculate "first", "next", and "edest" for the subtree - whose root is NODE. */ +/* 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 (root, fn, extra) + 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 -analyze_tree (dfa, node) - re_dfa_t *dfa; +preorder (root, fn, extra) + 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; + + /* 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 (extra, node) + void *extra; bin_tree_t *node; { - reg_errcode_t ret; - if (node->first == -1) - calc_first (dfa, node); - if (node->next == -1) - calc_next (dfa, node); - calc_epsdest (dfa, node); + re_dfa_t *dfa = (re_dfa_t *) extra; - /* Calculate "first" etc. for the left child. */ - if (node->left != NULL) + if (node->token.type == OP_BACK_REF && dfa->subexp_map) { - ret = analyze_tree (dfa, node->left); - if (BE (ret != REG_NOERROR, 0)) - return ret; + int idx = node->token.opr.idx; + node->token.opr.idx = dfa->subexp_map[idx]; + dfa->used_bkref_map |= 1 << node->token.opr.idx; } - /* Calculate "first" etc. for the right child. */ - if (node->right != NULL) + + else if (node->token.type == SUBEXP + && node->left && node->left->token.type == SUBEXP) { - ret = analyze_tree (dfa, node->right); - if (BE (ret != REG_NOERROR, 0)) - return ret; + 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 < 8 * sizeof (dfa->used_bkref_map)) + dfa->used_bkref_map &= ~(1 << other_idx); } + return REG_NOERROR; } -/* Calculate "first" for the node NODE. */ -static void -calc_first (dfa, node) - re_dfa_t *dfa; +/* 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 (extra, node) + void *extra; bin_tree_t *node; { - int idx, type; - idx = node->node_idx; - type = (node->type == 0) ? dfa->nodes[idx].type : node->type; + regex_t *preg = (regex_t *) extra; + reg_errcode_t err = REG_NOERROR; - switch (type) + if (node->left && node->left->token.type == SUBEXP) { -#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; + node->left = lower_subexp (&err, preg, node->left); + if (node->left) + node->left->parent = node; + } + if (node->right && node->right->token.type == SUBEXP) + { + node->right = lower_subexp (&err, preg, node->right); + if (node->right) + node->right->parent = node; } -} -/* Calculate "next" for the node NODE. */ + return err; +} -static void -calc_next (dfa, node) - re_dfa_t *dfa; +static bin_tree_t * +lower_subexp (err, preg, node) + reg_errcode_t *err; + regex_t *preg; bin_tree_t *node; { - int idx, type; - bin_tree_t *parent = node->parent; - if (parent == NULL) + 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 + && (node->token.opr.idx >= 8 * sizeof (dfa->used_bkref_map) + || !(dfa->used_bkref_map & (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)) { - node->next = -1; - idx = node->node_idx; - if (node->type == 0) - dfa->nexts[idx] = node->next; - return; + *err = REG_ESPACE; + return NULL; } - idx = parent->node_idx; - type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type; + 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; +} - switch (type) +/* Pass 1 in building the NFA: compute FIRST and create unlinked automaton + nodes. Requires a postorder visit. */ +static reg_errcode_t +calc_first (extra, node) + void *extra; + bin_tree_t *node; +{ + re_dfa_t *dfa = (re_dfa_t *) extra; + if (node->token.type == CONCAT) + { + node->first = node->left->first; + node->node_idx = node->left->node_idx; + } + 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 (extra, node) + void *extra; + bin_tree_t *node; +{ + switch (node->token.type) { case OP_DUP_ASTERISK: - node->next = idx; + node->left->next = node; break; case CONCAT: - if (parent->left == node) - { - if (parent->right->first == -1) - calc_first (dfa, parent->right); - node->next = parent->right->first; - break; - } - /* else fall through */ + node->left->next = node->right->first; + node->right->next = node->next; + break; default: - if (parent->next == -1) - calc_next (dfa, parent); - node->next = parent->next; + if (node->left) + node->left->next = node->next; + if (node->right) + node->right->next = node->next; break; } - idx = node->node_idx; - if (node->type == 0) - dfa->nexts[idx] = node->next; + return REG_NOERROR; } -/* Calculate "edest" for the node NODE. */ - -static void -calc_epsdest (dfa, node) - re_dfa_t *dfa; +/* Pass 3: link all DFA nodes to their NEXT node (any order will do). */ +static reg_errcode_t +link_nfa_nodes (extra, node) + void *extra; bin_tree_t *node; { - int idx; - idx = node->node_idx; - if (node->type == 0) + re_dfa_t *dfa = (re_dfa_t *) extra; + int idx = node->node_idx; + reg_errcode_t err = REG_NOERROR; + + switch (node->token.type) { - 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)); + 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; } + + return err; } /* Duplicate the epsilon closure of the node ROOT_NODE. @@ -1520,7 +1522,7 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node, else /* dfa->edests[org_node].nelem == 2 */ { /* In case of the node can epsilon-transit, and it has two - destinations. E.g. '|', '*', '+', '?'. */ + destinations. In the bin_tree_t and DFA, that's '|' and '*'. */ 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. */ @@ -1591,16 +1593,13 @@ duplicate_node (new_idx, dfa, org_idx, constraint) int *new_idx, org_idx; unsigned int constraint; { - int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx], 1); + int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]); 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; @@ -1608,21 +1607,26 @@ duplicate_node (new_idx, dfa, org_idx, constraint) return REG_NOERROR; } -static void +static reg_errcode_t calc_inveclosure (dfa) re_dfa_t *dfa; { - int src, idx, dest; + int src, idx, ret; + for (idx = 0; idx < dfa->nodes_len; ++idx) + re_node_set_init_empty (dfa->inveclosures + idx); + for (src = 0; src < dfa->nodes_len; ++src) { - if (dfa->nodes[src].type == OP_DELETED_SUBEXP) - continue; + int *elems = dfa->eclosures[src].elems; for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx) { - dest = dfa->eclosures[src].elems[idx]; - re_node_set_insert_last (dfa->inveclosures + dest, src); + ret = re_node_set_insert_last (dfa->inveclosures + elems[idx], src); + if (BE (ret == -1, 0)) + return REG_ESPACE; } } + + return REG_NOERROR; } /* Calculate "eclosure" for all the node in DFA. */ @@ -1652,8 +1656,6 @@ calc_eclosure (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) @@ -1859,7 +1861,7 @@ peek_token (token, input, syntax) if (!(syntax & RE_NO_GNU_OPS)) { token->type = ANCHOR; - token->opr.ctx_type = INSIDE_WORD; + token->opr.ctx_type = NOT_WORD_DELIM; } break; case 'w': @@ -2124,9 +2126,9 @@ parse (regexp, preg, syntax, err) tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err); if (BE (*err != REG_NOERROR && tree == NULL, 0)) return NULL; - eor = re_dfa_add_tree_node (dfa, NULL, NULL, ¤t_token); + eor = create_tree (dfa, NULL, NULL, END_OF_RE); if (tree != NULL) - root = create_tree (dfa, tree, eor, CONCAT, 0); + root = create_tree (dfa, tree, eor, CONCAT); else root = eor; if (BE (eor == NULL || root == NULL, 0)) @@ -2163,7 +2165,6 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err) 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)) @@ -2174,13 +2175,12 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err) } else branch = NULL; - tree = re_dfa_add_tree_node (dfa, tree, branch, &alt_token); + tree = create_tree (dfa, tree, branch, OP_ALT); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; return NULL; } - dfa->has_plural_match = 1; } return tree; } @@ -2219,7 +2219,7 @@ parse_branch (regexp, preg, token, syntax, nest, err) } if (tree != NULL && exp != NULL) { - tree = create_tree (dfa, tree, exp, CONCAT, 0); + tree = create_tree (dfa, tree, exp, CONCAT); if (tree == NULL) { *err = REG_ESPACE; @@ -2253,7 +2253,7 @@ parse_expression (regexp, preg, token, syntax, nest, err) switch (token->type) { case CHARACTER: - tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); + tree = create_token_tree (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; @@ -2267,8 +2267,8 @@ parse_expression (regexp, preg, token, syntax, nest, err) { bin_tree_t *mbc_remain; fetch_token (token, regexp, syntax); - mbc_remain = re_dfa_add_tree_node (dfa, NULL, NULL, token); - tree = create_tree (dfa, tree, mbc_remain, CONCAT, 0); + mbc_remain = create_token_tree (dfa, NULL, NULL, token); + tree = create_tree (dfa, tree, mbc_remain, CONCAT); if (BE (mbc_remain == NULL || tree == NULL, 0)) { *err = REG_ESPACE; @@ -2295,7 +2295,7 @@ parse_expression (regexp, preg, token, syntax, nest, err) return NULL; } dfa->used_bkref_map |= 1 << token->opr.idx; - tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); + tree = create_token_tree (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; @@ -2340,7 +2340,7 @@ parse_expression (regexp, preg, token, syntax, nest, err) token->type = CHARACTER; /* mb_partial and word_char bits should be initialized already by peek_token. */ - tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); + tree = create_token_tree (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; @@ -2349,18 +2349,27 @@ parse_expression (regexp, preg, token, syntax, nest, err) break; case ANCHOR: if ((token->opr.ctx_type - & (WORD_DELIM | INSIDE_WORD | WORD_FIRST | WORD_LAST)) + & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST)) && dfa->word_ops_used == 0) init_word_char (dfa); - if (token->opr.ctx_type == WORD_DELIM) + if (token->opr.ctx_type == WORD_DELIM + || token->opr.ctx_type == NOT_WORD_DELIM) { bin_tree_t *tree_first, *tree_last; - 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 (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); if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0)) { *err = REG_ESPACE; @@ -2369,7 +2378,7 @@ parse_expression (regexp, preg, token, syntax, nest, err) } else { - tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); + tree = create_token_tree (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; @@ -2383,7 +2392,7 @@ parse_expression (regexp, preg, token, syntax, nest, err) fetch_token (token, regexp, syntax); return tree; case OP_PERIOD: - tree = re_dfa_add_tree_node (dfa, NULL, NULL, token); + tree = create_token_tree (dfa, NULL, NULL, token); if (BE (tree == NULL, 0)) { *err = REG_ESPACE; @@ -2439,7 +2448,6 @@ parse_expression (regexp, preg, token, syntax, nest, err) *err = REG_BADRPT; return NULL; } - dfa->has_plural_match = 1; } return tree; @@ -2462,17 +2470,10 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) reg_errcode_t *err; { re_dfa_t *dfa = (re_dfa_t *) preg->buffer; - bin_tree_t *tree, *left_par, *right_par; + bin_tree_t *tree; 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. */ @@ -2481,26 +2482,20 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err) else { tree = parse_reg_exp (regexp, preg, token, syntax, nest, err); - if (BE (*err != REG_NOERROR && tree == NULL, 0)) + if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0)) + *err = REG_EPAREN; + if (BE (*err != REG_NOERROR, 0)) return NULL; } - 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)) + + tree = create_tree (dfa, tree, NULL, SUBEXP); + if (BE (tree == NULL, 0)) { *err = REG_ESPACE; return NULL; } - dfa->nodes[right_par->node_idx].opr.idx = cur_nsub; - + tree->token.opr.idx = cur_nsub; return tree; } @@ -2515,7 +2510,6 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err) 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; @@ -2578,9 +2572,13 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err) fetch_token (token, regexp, syntax); - /* Treat "<re>{0}*" etc. as "<re>{0}". */ - if (BE (elem == NULL || (start == 0 && end == 0), 0)) + if (BE (elem == NULL, 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)) @@ -2589,7 +2587,7 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err) for (i = 2; i <= start; ++i) { elem = duplicate_tree (elem, dfa); - tree = create_tree (dfa, tree, elem, CONCAT, 0); + tree = create_tree (dfa, tree, elem, CONCAT); if (BE (elem == NULL || tree == NULL, 0)) goto parse_dup_op_espace; } @@ -2604,9 +2602,10 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err) else old_tree = NULL; - 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 (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)); if (BE (tree == NULL, 0)) goto parse_dup_op_espace; @@ -2616,17 +2615,17 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err) for (i = start + 2; i <= end; ++i) { elem = duplicate_tree (elem, dfa); - tree = create_tree (dfa, tree, elem, CONCAT, 0); + tree = create_tree (dfa, tree, elem, CONCAT); if (BE (elem == NULL || tree == NULL, 0)) goto parse_dup_op_espace; - tree = re_dfa_add_tree_node (dfa, tree, NULL, &dup_token); + tree = create_tree (dfa, tree, NULL, OP_ALT); if (BE (tree == NULL, 0)) goto parse_dup_op_espace; } if (old_tree) - tree = create_tree (dfa, old_tree, tree, CONCAT, 0); + tree = create_tree (dfa, old_tree, tree, CONCAT); return tree; @@ -3282,57 +3281,59 @@ parse_bracket_exp (regexp, dfa, token, syntax, err) /* 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_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_UINTS) + if (sbc_idx < BITSET_UINTS) + { + /* 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 { re_free (sbcset); - dfa->nodes[work_tree->node_idx].type = COMPLEX_BRACKET; - dfa->nodes[work_tree->node_idx].opr.mbcset = mbcset; - return work_tree; + work_tree = mbc_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); - return work_tree; +#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; } -#else /* not RE_ENABLE_I18N */ return work_tree; -#endif /* not RE_ENABLE_I18N */ parse_bracket_exp_espace: *err = REG_ESPACE; @@ -3693,26 +3694,23 @@ build_charclass_op (dfa, trans, class_name, extra, non_match, err) /* Build a tree for simple bracket. */ br_token.type = SIMPLE_BRACKET; br_token.opr.sbcset = sbcset; - tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token); + tree = create_token_tree (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 = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token); + mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token); if (BE (mbc_tree == NULL, 0)) goto build_word_op_espace; /* Then join them by ALT node. */ - alt_token.type = OP_ALT; - dfa->has_plural_match = 1; - tree = re_dfa_add_tree_node (dfa, tree, mbc_tree, &alt_token); + tree = create_tree (dfa, tree, mbc_tree, OP_ALT); if (BE (mbc_tree != NULL, 1)) return tree; } @@ -3783,12 +3781,23 @@ free_charset (re_charset_t *cset) /* Create a tree node. */ static bin_tree_t * -create_tree (dfa, left, right, type, index) +create_tree (dfa, left, right, type) re_dfa_t *dfa; bin_tree_t *left; bin_tree_t *right; re_token_type_t type; - int index; +{ + re_token_t t; + t.type = type; + return create_token_tree (dfa, left, right, &t); +} + +static bin_tree_t * +create_token_tree (dfa, left, right, token) + re_dfa_t *dfa; + bin_tree_t *left; + bin_tree_t *right; + const re_token_t *token; { bin_tree_t *tree; if (BE (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE, 0)) @@ -3806,11 +3815,12 @@ create_tree (dfa, left, right, type, index) tree->parent = NULL; tree->left = left; tree->right = right; - tree->type = type; - tree->node_idx = index; - tree->first = -1; - tree->next = -1; - re_node_set_init_empty (&tree->eclosure); + tree->token = *token; + tree->token.duplicated = 0; + tree->token.opt_subexp = 0; + tree->first = NULL; + tree->next = NULL; + tree->node_idx = -1; if (left != NULL) left->parent = tree; @@ -3819,103 +3829,89 @@ create_tree (dfa, left, right, type, index) return tree; } -/* Create both a DFA node and a tree for it. */ +/* Mark the tree SRC as an optional subexpression. + To be called from preorder or postorder. */ -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; +static reg_errcode_t +mark_opt_subexp (extra, node) + void *extra; + bin_tree_t *node; { - int new_idx = re_dfa_add_node (dfa, *token, 0); + int idx = (int) (long) extra; + if (node->token.type == SUBEXP && node->token.opr.idx == idx) + node->token.opt_subexp = 1; - if (new_idx == -1) - return NULL; - - return create_tree (dfa, left, right, 0, new_idx); + return REG_NOERROR; } -/* Mark the tree SRC as an optional subexpression. */ +/* Free the allocated memory inside NODE. */ static void -mark_opt_subexp (src, dfa) - const bin_tree_t *src; - re_dfa_t *dfa; +free_token (re_token_t *node) { - /* 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); +#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); } +/* Worker function for tree walking. Free the allocated memory inside NODE + and its children. */ -/* 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; +static reg_errcode_t +free_tree (void *extra, bin_tree_t *node) { - 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); + free_token (&node->token); + return REG_NOERROR; } -/* Duplicate the node SRC, and return new node. */ +/* 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. */ static bin_tree_t * -duplicate_tree (src, dfa) - const bin_tree_t *src; +duplicate_tree (root, dfa) + const bin_tree_t *root; re_dfa_t *dfa; { - 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; - } + const bin_tree_t *node; + bin_tree_t *dup_root; + bin_tree_t **p_new = &dup_root, *dup_node = root->parent; - /* Secondaly, duplicate the right. */ - if (src->right != NULL) + for (node = root; ; ) { - right = duplicate_tree (src->right, dfa); - if (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) return NULL; - } + (*p_new)->parent = dup_node; + (*p_new)->token.duplicated = 1; + dup_node = *p_new; - /* 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; + /* 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; + } } - else - new_node_idx = src->type; - - new_tree = create_tree (dfa, left, right, src->type, new_node_idx); - return new_tree; } diff --git a/posix/regex_internal.c b/posix/regex_internal.c index f15cb575eb..c3295a851c 100644 --- a/posix/regex_internal.c +++ b/posix/regex_internal.c @@ -1330,47 +1330,44 @@ re_node_set_remove_at (set, idx) Or return -1, if an error will be occured. */ static int -re_dfa_add_node (dfa, token, mode) +re_dfa_add_node (dfa, token) re_dfa_t *dfa; re_token_t token; - int mode; { + int type = token.type; if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0)) { int new_nodes_alloc = dfa->nodes_alloc * 2; + int *new_nexts, *new_indices; + re_node_set *new_edests, *new_eclosures; + re_token_t *new_array = re_realloc (dfa->nodes, re_token_t, new_nodes_alloc); if (BE (new_array == NULL, 0)) return -1; dfa->nodes = new_array; - if (mode) - { - int *new_nexts, *new_indices; - re_node_set *new_edests, *new_eclosures, *new_inveclosures; - - new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc); - new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc); - new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc); - new_eclosures = re_realloc (dfa->eclosures, re_node_set, - new_nodes_alloc); - new_inveclosures = re_realloc (dfa->inveclosures, re_node_set, - new_nodes_alloc); - if (BE (new_nexts == NULL || new_indices == NULL - || new_edests == NULL || new_eclosures == NULL - || new_inveclosures == NULL, 0)) - return -1; - dfa->nexts = new_nexts; - dfa->org_indices = new_indices; - dfa->edests = new_edests; - dfa->eclosures = new_eclosures; - dfa->inveclosures = new_inveclosures; - } + new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc); + new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc); + new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc); + new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc); + if (BE (new_nexts == NULL || new_indices == NULL + || new_edests == NULL || new_eclosures == NULL, 0)) + return -1; + dfa->nexts = new_nexts; + dfa->org_indices = new_indices; + dfa->edests = new_edests; + dfa->eclosures = new_eclosures; dfa->nodes_alloc = new_nodes_alloc; } dfa->nodes[dfa->nodes_len] = token; - dfa->nodes[dfa->nodes_len].opt_subexp = 0; - dfa->nodes[dfa->nodes_len].duplicated = 0; dfa->nodes[dfa->nodes_len].constraint = 0; +#ifdef RE_ENABLE_I18N + dfa->nodes[dfa->nodes_len].accept_mb = + (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET; +#endif + dfa->nexts[dfa->nodes_len] = -1; + re_node_set_init_empty (dfa->edests + dfa->nodes_len); + re_node_set_init_empty (dfa->eclosures + dfa->nodes_len); return dfa->nodes_len++; } @@ -1551,16 +1548,13 @@ create_ci_newstate (dfa, nodes, hash) re_token_type_t type = node->type; if (type == CHARACTER && !node->constraint) continue; +#ifdef RE_ENABLE_I18N + newstate->accept_mb |= node->accept_mb; +#endif /* RE_ENABLE_I18N */ /* If the state has the halt node, the state is a halt state. */ - else if (type == END_OF_RE) + if (type == END_OF_RE) newstate->halt = 1; -#ifdef RE_ENABLE_I18N - else if (type == COMPLEX_BRACKET - || type == OP_UTF8_PERIOD - || (type == OP_PERIOD && dfa->mb_cur_max > 1)) - newstate->accept_mb = 1; -#endif /* RE_ENABLE_I18N */ else if (type == OP_BACK_REF) newstate->has_backref = 1; else if (type == ANCHOR || node->constraint) @@ -1611,15 +1605,13 @@ create_cd_newstate (dfa, nodes, context, hash) if (type == CHARACTER && !constraint) continue; - /* If the state has the halt node, the state is a halt state. */ - else if (type == END_OF_RE) - newstate->halt = 1; #ifdef RE_ENABLE_I18N - else if (type == COMPLEX_BRACKET - || type == OP_UTF8_PERIOD - || (type == OP_PERIOD && dfa->mb_cur_max > 1)) - newstate->accept_mb = 1; + newstate->accept_mb |= node->accept_mb; #endif /* RE_ENABLE_I18N */ + + /* If the state has the halt node, the state is a halt state. */ + if (type == END_OF_RE) + newstate->halt = 1; else if (type == OP_BACK_REF) newstate->has_backref = 1; else if (type == ANCHOR) diff --git a/posix/regex_internal.h b/posix/regex_internal.h index 23765c970e..f065cf449d 100644 --- a/posix/regex_internal.h +++ b/posix/regex_internal.h @@ -1,5 +1,5 @@ /* Extended regular expression matching and search library. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>. @@ -143,18 +143,21 @@ static inline void bitset_mask (bitset dest, const bitset src); #define NEXT_NEWLINE_CONSTRAINT 0x0020 #define PREV_BEGBUF_CONSTRAINT 0x0040 #define NEXT_ENDBUF_CONSTRAINT 0x0080 -#define DUMMY_CONSTRAINT 0x0100 +#define WORD_DELIM_CONSTRAINT 0x0100 +#define NOT_WORD_DELIM_CONSTRAINT 0x0200 typedef enum { INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT, WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT, WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT, + INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT, LINE_FIRST = PREV_NEWLINE_CONSTRAINT, LINE_LAST = NEXT_NEWLINE_CONSTRAINT, BUF_FIRST = PREV_BEGBUF_CONSTRAINT, BUF_LAST = NEXT_ENDBUF_CONSTRAINT, - WORD_DELIM = DUMMY_CONSTRAINT + WORD_DELIM = WORD_DELIM_CONSTRAINT, + NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT } re_context_type; typedef struct @@ -186,16 +189,16 @@ typedef enum OP_CLOSE_SUBEXP = EPSILON_BIT | 1, OP_ALT = EPSILON_BIT | 2, OP_DUP_ASTERISK = EPSILON_BIT | 3, - OP_DUP_PLUS = EPSILON_BIT | 4, - OP_DUP_QUESTION = EPSILON_BIT | 5, - ANCHOR = EPSILON_BIT | 6, - OP_DELETED_SUBEXP = EPSILON_BIT | 7, + ANCHOR = EPSILON_BIT | 4, /* Tree type, these are used only by tree. */ CONCAT = 16, + SUBEXP = 17, /* Token type, these are used only by token. */ - OP_OPEN_BRACKET = 17, + OP_DUP_PLUS = 18, + OP_DUP_QUESTION, + OP_OPEN_BRACKET, OP_CLOSE_BRACKET, OP_CHARSET_RANGE, OP_OPEN_DUP_NUM, @@ -284,6 +287,7 @@ typedef struct unsigned int duplicated : 1; unsigned int opt_subexp : 1; #ifdef RE_ENABLE_I18N + unsigned int accept_mb : 1; /* These 2 bits can be moved into the union if needed (e.g. if running out of bits; move opr.c to opr.c.c and move the flags to opr.c.flags). */ unsigned int mb_partial : 1; @@ -292,8 +296,6 @@ typedef struct } re_token_t; #define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT) -#define ACCEPT_MB_NODE(type) \ - ((type) >= OP_PERIOD && (type) <= OP_UTF8_PERIOD) struct re_string_t { @@ -429,15 +431,14 @@ struct bin_tree_t struct bin_tree_t *parent; struct bin_tree_t *left; struct bin_tree_t *right; + struct bin_tree_t *first; + struct bin_tree_t *next; + + re_token_t token; /* `node_idx' is the index in dfa->nodes, if `type' == 0. Otherwise `type' indicate the type of this node. */ - re_token_type_t type; int node_idx; - - int first; - int next; - re_node_set eclosure; }; typedef struct bin_tree_t bin_tree_t; @@ -677,7 +678,7 @@ static void re_node_set_remove_at (re_node_set *set, int idx) internal_function; (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1)) #define re_node_set_empty(p) ((p)->nelem = 0) #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) internal_function; +static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token) internal_function; static re_dfastate_t *re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) internal_function; static re_dfastate_t *re_acquire_state_context (reg_errcode_t *err, diff --git a/posix/regexec.c b/posix/regexec.c index 1b21b699e9..636396e6f7 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -605,6 +605,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, re_dfa_t *dfa = (re_dfa_t *)preg->buffer; int left_lim, right_lim, incr; int fl_longest_match, match_first, match_kind, match_last = -1; + int extra_nmatch; int sb, ch; #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L) re_match_context_t mctx = { .dfa = dfa }; @@ -620,6 +621,9 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, mctx.dfa = dfa; #endif + extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0; + nmatch -= extra_nmatch; + /* 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 @@ -882,11 +886,14 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, pmatch[reg_idx].rm_so += match_first; pmatch[reg_idx].rm_eo += match_first; } + for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx) + { + pmatch[nmatch + reg_idx].rm_so = -1; + pmatch[nmatch + reg_idx].rm_eo = -1; + } if (dfa->subexp_map) - for (reg_idx = 0; - reg_idx + 1 < nmatch && reg_idx < preg->re_nsub; - reg_idx++) + for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++) if (dfa->subexp_map[reg_idx] != reg_idx) { pmatch[reg_idx + 1].rm_so @@ -1262,7 +1269,7 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs) re_token_type_t type = dfa->nodes[node].type; #ifdef RE_ENABLE_I18N - if (ACCEPT_MB_NODE (type)) + if (dfa->nodes[node].accept_mb) naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx); else #endif /* RE_ENABLE_I18N */ @@ -1371,7 +1378,7 @@ set_regs (preg, mctx, nmatch, pmatch, fl_backtrack) int fl_backtrack; { re_dfa_t *dfa = (re_dfa_t *) preg->buffer; - int idx, cur_node, real_nmatch; + int idx, cur_node; re_node_set eps_via_nodes; struct re_fail_stack_t *fs; struct re_fail_stack_t fs_body = { 0, 2, NULL }; @@ -1392,15 +1399,14 @@ set_regs (preg, mctx, nmatch, pmatch, fl_backtrack) fs = NULL; cur_node = dfa->init_node; - real_nmatch = (nmatch <= preg->re_nsub) ? nmatch : preg->re_nsub + 1; re_node_set_init_empty (&eps_via_nodes); - prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * real_nmatch); - memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * real_nmatch); + prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * nmatch); + memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch); for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;) { - update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, real_nmatch); + update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch); if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node) { @@ -1624,15 +1630,13 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest) int naccepted = 0; int ret; -#if defined DEBUG || defined RE_ENABLE_I18N - re_token_type_t type = dfa->nodes[prev_node].type; -#endif #ifdef DEBUG + re_token_type_t type = dfa->nodes[prev_node].type; assert (!IS_EPSILON_NODE (type)); #endif #ifdef RE_ENABLE_I18N /* If the node may accept `multi byte'. */ - if (ACCEPT_MB_NODE (type)) + if (dfa->nodes[prev_node].accept_mb) naccepted = sift_states_iter_mb (mctx, sctx, prev_node, str_idx, sctx->last_str_idx); #endif /* RE_ENABLE_I18N */ @@ -2471,10 +2475,13 @@ transit_state_mb (mctx, pstate) { re_node_set dest_nodes, *new_nodes; int cur_node_idx = pstate->nodes.elems[i]; - int naccepted = 0, dest_idx; + int naccepted, dest_idx; unsigned int context; re_dfastate_t *dest_state; + if (!dfa->nodes[cur_node_idx].accept_mb) + continue; + if (dfa->nodes[cur_node_idx].constraint) { context = re_string_context_at (&mctx->input, @@ -2486,9 +2493,8 @@ transit_state_mb (mctx, pstate) } /* How many bytes the node can accept? */ - if (ACCEPT_MB_NODE (dfa->nodes[cur_node_idx].type)) - naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input, - re_string_cur_idx (&mctx->input)); + naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input, + re_string_cur_idx (&mctx->input)); if (naccepted == 0) continue; @@ -2502,9 +2508,7 @@ transit_state_mb (mctx, pstate) #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. */ - new_nodes = dfa->eclosures + dfa->nexts[pstate->nodes.elems[i]]; + new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx]; dest_state = mctx->state_log[dest_idx]; if (dest_state == NULL) @@ -3020,15 +3024,13 @@ check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes) { int naccepted = 0; int cur_node = cur_nodes->elems[cur_idx]; -#if defined DEBUG || defined RE_ENABLE_I18N - re_token_type_t type = dfa->nodes[cur_node].type; -#endif #ifdef DEBUG + re_token_type_t type = dfa->nodes[cur_node].type; assert (!IS_EPSILON_NODE (type)); #endif #ifdef RE_ENABLE_I18N /* If the node may accept `multi byte'. */ - if (ACCEPT_MB_NODE (type)) + if (dfa->nodes[cur_node].accept_mb) { naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input, str_idx); diff --git a/posix/rxspencer/tests b/posix/rxspencer/tests index a724252d8c..a8b6e4baa8 100644 --- a/posix/rxspencer/tests +++ b/posix/rxspencer/tests @@ -526,3 +526,12 @@ a((b+|((c)*)))+d - abcd abcd c,c,c,c (((\b))){0} - x @x -,-,- a(((.*)))b((\2)){0}c - abc abc @bc,@bc,@bc,-,- a(((.*)))b((\1)){0}c - axbc axbc x,x,x,-,- + +\b & SaT @aT +\b & aT @aT +a.*\b & abT ab +\b & STSS +\B & abc @bc +\B & aSbTc +\B & SaT @SaT +\B & aSTSb @TSb diff --git a/posix/tst-rxspencer.c b/posix/tst-rxspencer.c index cb40421797..a68bab2de9 100644 --- a/posix/tst-rxspencer.c +++ b/posix/tst-rxspencer.c @@ -1,5 +1,5 @@ /* Regular expression tests. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2005 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Jakub Jelinek <jakub@redhat.com>, 2003. @@ -127,14 +127,15 @@ mb_frob_string (const char *str, const char *letters) } /* Like mb_frob_string, but don't replace anything between - [: and :], [. and .] or [= and =]. */ + [: and :], [. and .] or [= and =] or characters escaped + with a backslash. */ static char * mb_frob_pattern (const char *str, const char *letters) { char *ret, *dst; const char *src; - int in_class = 0; + int in_class = 0, escaped = 0; if (str == NULL) return NULL; @@ -144,7 +145,18 @@ mb_frob_pattern (const char *str, const char *letters) return NULL; for (src = str, dst = ret; *src; ++src) - if (!in_class && strchr (letters, *src)) + if (*src == '\\') + { + escaped ^= 1; + *dst++ = *src; + } + else if (escaped) + { + escaped = 0; + *dst++ = *src; + continue; + } + else if (!in_class && strchr (letters, *src)) dst = mb_replace (dst, *src); else { diff --git a/posix/unistd.h b/posix/unistd.h index 06c8ca7c21..744c10c50b 100644 --- a/posix/unistd.h +++ b/posix/unistd.h @@ -468,7 +468,7 @@ extern char *getwd (char *__buf) extern int dup (int __fd) __THROW __wur; /* Duplicate FD to FD2, closing FD2 and making it open on the same file. */ -extern int dup2 (int __fd, int __fd2) __THROW __wur; +extern int dup2 (int __fd, int __fd2) __THROW; /* NULL-terminated array of "NAME=VALUE" environment variables. */ extern char **__environ; |