diff options
Diffstat (limited to 'lib/wrappers/tre/tre_all.c')
| -rw-r--r-- | lib/wrappers/tre/tre_all.c | 8873 |
1 files changed, 8873 insertions, 0 deletions
diff --git a/lib/wrappers/tre/tre_all.c b/lib/wrappers/tre/tre_all.c new file mode 100644 index 000000000..8272657a3 --- /dev/null +++ b/lib/wrappers/tre/tre_all.c @@ -0,0 +1,8873 @@ +/* + regcomp.c - TRE POSIX compatible regex compilation functions. + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* config.h. Generated from config.h.in by configure. */ +/* config.h.in. Generated from configure.ac by autoheader. */ + +/* Define to one of `_getb67', `GETB67', `getb67' for Cray-2 and Cray-YMP + systems. This function is required for `alloca.c' support on those systems. + */ +/* #undef CRAY_STACKSEG_END */ + +/* Define to 1 if using `alloca.c'. */ +/* #undef C_ALLOCA */ + +/* Define to 1 if translation of program messages to the user's native + language is requested. */ +#define ENABLE_NLS 1 + +/* Define to 1 if you have `alloca', as a function or macro. */ +/* #undef HAVE_ALLOCA */ + +/* Define to 1 if you have <alloca.h> and it should be used (not on Ultrix). + */ +/* #undef HAVE_ALLOCA_H */ + +/* Define to 1 if you have the MacOS X function CFLocaleCopyCurrent in the + CoreFoundation framework. */ +#define HAVE_CFLOCALECOPYCURRENT 1 + +/* Define to 1 if you have the MacOS X function CFPreferencesCopyAppValue in + the CoreFoundation framework. */ +#define HAVE_CFPREFERENCESCOPYAPPVALUE 1 + +/* Define if the GNU dcgettext() function is already present or preinstalled. + */ +#define HAVE_DCGETTEXT 1 + +/* Define to 1 if you have the <dlfcn.h> header file. */ +#define HAVE_DLFCN_H 1 + +/* Define to 1 if you have the <getopt.h> header file. */ +#define HAVE_GETOPT_H 1 + +/* Define to 1 if you have the `getopt_long' function. */ +#define HAVE_GETOPT_LONG 1 + +/* Define if the GNU gettext() function is already present or preinstalled. */ +#define HAVE_GETTEXT 1 + +/* Define if you have the iconv() function and it works. */ +#define HAVE_ICONV 1 + +/* Define to 1 if you have the <inttypes.h> header file. */ +/* #undef HAVE_INTTYPES_H */ + +/* Define to 1 if you have the `isascii' function. */ +#define HAVE_ISASCII 1 + +/* Define to 1 if you have the `isblank' function. */ +#define HAVE_ISBLANK 1 + +/* Define to 1 if you have the `iswascii' function or macro. */ +/* #undef HAVE_ISWASCII */ + +/* Define to 1 if you have the `iswblank' function or macro. */ +/* #undef HAVE_ISWBLANK */ + +/* Define to 1 if you have the `iswctype' function or macro. */ +/* #undef HAVE_ISWCTYPE */ + +/* Define to 1 if you have the `iswlower' function or macro. */ +/* #undef HAVE_ISWLOWER */ + +/* Define to 1 if you have the `iswupper' function or macro. */ +/* #undef HAVE_ISWUPPER */ + +/* Define to 1 if you have the <libutf8.h> header file. */ +/* #undef HAVE_LIBUTF8_H */ + +/* Define to 1 if you have the `mbrtowc' function or macro. */ +/* #undef HAVE_MBRTOWC */ + +/* Define to 1 if the system has the type `mbstate_t'. */ +/* #undef HAVE_MBSTATE_T */ + +/* Define to 1 if you have the `mbtowc' function or macro. */ +/* #undef HAVE_MBTOWC */ + +/* Define to 1 if you have the <memory.h> header file. */ +/* #undef HAVE_MEMORY_H */ + +/* Define to 1 if you have the <regex.h> header file. */ +/* #undef HAVE_REGEX_H */ + +/* Define to 1 if the system has the type `reg_errcode_t'. */ +/* #undef HAVE_REG_ERRCODE_T */ + +/* Define to 1 if you have the <stdint.h> header file. */ +/* #undef HAVE_STDINT_H */ + +/* Define to 1 if you have the <stdlib.h> header file. */ +/* #undef HAVE_STDLIB_H */ + +/* Define to 1 if you have the <strings.h> header file. */ +/* #undef HAVE_STRINGS_H */ + +/* Define to 1 if you have the <string.h> header file. */ +/* #undef HAVE_STRING_H */ + +/* Define to 1 if you have the <sys/stat.h> header file. */ +/* #undef HAVE_SYS_STAT_H */ + +/* Define to 1 if you have the <sys/types.h> header file. */ +/* #undef HAVE_SYS_TYPES_H */ + +/* Define to 1 if you have the `towlower' function or macro. */ +/* #undef HAVE_TOWLOWER */ + +/* Define to 1 if you have the `towupper' function or macro. */ +/* #undef HAVE_TOWUPPER */ + +/* Define to 1 if you have the <unistd.h> header file. */ +/* #undef HAVE_UNISTD_H */ + +/* Define to 1 if you have the <wchar.h> header file. */ +/* #undef HAVE_WCHAR_H */ + +/* Define to 1 if the system has the type `wchar_t'. */ +/* #undef HAVE_WCHAR_T */ + +/* Define to 1 if you have the `wcschr' function or macro. */ +/* #undef HAVE_WCSCHR */ + +/* Define to 1 if you have the `wcscpy' function or macro. */ +/* #undef HAVE_WCSCPY */ + +/* Define to 1 if you have the `wcslen' function or macro. */ +/* #undef HAVE_WCSLEN */ + +/* Define to 1 if you have the `wcsncpy' function or macro. */ +/* #undef HAVE_WCSNCPY */ + +/* Define to 1 if you have the `wcsrtombs' function or macro. */ +/* #undef HAVE_WCSRTOMBS */ + +/* Define to 1 if you have the `wcstombs' function or macro. */ +/* #undef HAVE_WCSTOMBS */ + +/* Define to 1 if you have the `wctype' function or macro. */ +/* #undef HAVE_WCTYPE */ + +/* Define to 1 if you have the <wctype.h> header file. */ +/* #undef HAVE_WCTYPE_H */ + +/* Define to 1 if the system has the type `wint_t'. */ +/* #undef HAVE_WINT_T */ + +/* Define if you want to disable debug assertions. */ +#define NDEBUG 1 + +/* Define to 1 if your C compiler doesn't accept -c and -o together. */ +/* #undef NO_MINUS_C_MINUS_O */ + +/* Name of package */ +#define PACKAGE "tre" + +/* Define to the address where bug reports for this package should be sent. */ +#define PACKAGE_BUGREPORT "tre-general@lists.laurikari.net" + +/* Define to the full name of this package. */ +#define PACKAGE_NAME "TRE" + +/* Define to the full name and version of this package. */ +#define PACKAGE_STRING "TRE 0.7.6" + +/* Define to the one symbol short name of this package. */ +#define PACKAGE_TARNAME "tre" + +/* Define to the version of this package. */ +#define PACKAGE_VERSION "0.7.6" + +/* If using the C implementation of alloca, define if you know the + direction of stack growth for your system; otherwise it will be + automatically deduced at runtime. + STACK_DIRECTION > 0 => grows toward higher addresses + STACK_DIRECTION < 0 => grows toward lower addresses + STACK_DIRECTION = 0 => direction of growth unknown */ +/* #undef STACK_DIRECTION */ + +/* Define to 1 if you have the ANSI C header files. */ +#define STDC_HEADERS 1 + +/* Define if you want to enable approximate matching functionality. */ +/* #undef TRE_APPROX */ + +/* Define if you want TRE to print debug messages to stdout. */ +/* #undef TRE_DEBUG */ + +/* Define to enable multibyte character set support. */ +/* #undef TRE_MULTIBYTE */ + +/* Define to a field in the regex_t struct where TRE should store a pointer to + the internal tre_tnfa_t structure */ +#define TRE_REGEX_T_FIELD value + +/* Define to the absolute path to the system regex.h */ +/* #undef TRE_SYSTEM_REGEX_H_PATH */ + +/* Define if you want TRE to use alloca() instead of malloc() when allocating + memory needed for regexec operations. */ +/* #undef TRE_USE_ALLOCA */ + +/* Define to include the system regex.h from TRE regex.h */ +/* #undef TRE_USE_SYSTEM_REGEX_H */ + +/* TRE version string. */ +#define TRE_VERSION "0.7.6" + +/* TRE version level 1. */ +#define TRE_VERSION_1 0 + +/* TRE version level 2. */ +#define TRE_VERSION_2 7 + +/* TRE version level 3. */ +#define TRE_VERSION_3 6 + +/* Define to enable wide character (wchar_t) support. */ +/* #undef TRE_WCHAR */ + +/* Version number of package */ +#define VERSION "0.7.6" + +/* Define to the maximum value of wchar_t if not already defined elsewhere */ +/* #undef WCHAR_MAX */ + +/* Define if wchar_t is signed */ +/* #undef WCHAR_T_SIGNED */ + +/* Define if wchar_t is unsigned */ +/* #undef WCHAR_T_UNSIGNED */ + +/* Number of bits in a file offset, on hosts where this is settable. */ +/* #undef _FILE_OFFSET_BITS */ + +/* Define to enable GNU extensions in glibc */ +#define _GNU_SOURCE 1 + +/* Define for large files, on AIX-style hosts. */ +/* #undef _LARGE_FILES */ + +/* Define on IRIX */ +/* #undef _REGCOMP_INTERNAL */ + +/* Define to empty if `const' does not conform to ANSI C. */ +/* #undef const */ + +/* Define to `__inline__' or `__inline' if that's what the C compiler + calls it, or to nothing if 'inline' is not supported under any name. */ + + +#include <string.h> +#include <errno.h> +#include <stdlib.h> + +/* + regex.h - POSIX.2 compatible regexp interface and TRE extensions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifndef TRE_REGEX_H +#define TRE_REGEX_H 1 + +/* lib/tre-config.h. Generated from tre-config.h.in by configure. */ +/* tre-config.h.in. This file has all definitions that are needed in + `regex.h'. Note that this file must contain only the bare minimum + of definitions without the TRE_ prefix to avoid conflicts between + definitions here and definitions included from somewhere else. */ + +/* Define to 1 if you have the <libutf8.h> header file. */ +/* #undef HAVE_LIBUTF8_H */ + +/* Define to 1 if the system has the type `reg_errcode_t'. */ +/* #undef HAVE_REG_ERRCODE_T */ + +/* Define to 1 if you have the <sys/types.h> header file. */ +/* #undef HAVE_SYS_TYPES_H */ + +/* Define to 1 if you have the <wchar.h> header file. */ +/* #undef HAVE_WCHAR_H */ + +/* Define if you want to enable approximate matching functionality. */ +/* #undef TRE_APPROX */ + +/* Define to enable multibyte character set support. */ +/* #undef TRE_MULTIBYTE */ + +/* Define to the absolute path to the system regex.h */ +/* #undef TRE_SYSTEM_REGEX_H_PATH */ + +/* Define to include the system regex.h from TRE regex.h */ +/* #undef TRE_USE_SYSTEM_REGEX_H */ + +/* Define to enable wide character (wchar_t) support. */ +/* #undef TRE_WCHAR */ + +/* TRE version string. */ +#define TRE_VERSION "0.7.6" + +/* TRE version level 1. */ +#define TRE_VERSION_1 0 + +/* TRE version level 2. */ +#define TRE_VERSION_2 7 + +/* TRE version level 3. */ +#define TRE_VERSION_3 6 + +#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif /* HAVE_SYS_TYPES_H */ + +#ifdef HAVE_LIBUTF8_H +#include <libutf8.h> +#endif /* HAVE_LIBUTF8_H */ + +#ifdef TRE_USE_SYSTEM_REGEX_H +/* Include the system regex.h to make TRE ABI compatible with the + system regex. */ +#include TRE_SYSTEM_REGEX_H_PATH +#endif /* TRE_USE_SYSTEM_REGEX_H */ + +#ifdef __cplusplus +extern "C" { +#endif + +#ifdef TRE_USE_SYSTEM_REGEX_H + +#ifndef REG_OK +#define REG_OK 0 +#endif /* !REG_OK */ + +#ifndef HAVE_REG_ERRCODE_T +typedef int reg_errcode_t; +#endif /* !HAVE_REG_ERRCODE_T */ + +#if !defined(REG_NOSPEC) && !defined(REG_LITERAL) +#define REG_LITERAL 0x1000 +#endif + +/* Extra regcomp() flags. */ +#ifndef REG_BASIC +#define REG_BASIC 0 +#endif /* !REG_BASIC */ +#define REG_RIGHT_ASSOC (REG_LITERAL << 1) +#define REG_UNGREEDY (REG_RIGHT_ASSOC << 1) + +/* Extra regexec() flags. */ +#define REG_APPROX_MATCHER 0x1000 +#define REG_BACKTRACKING_MATCHER (REG_APPROX_MATCHER << 1) + +#else /* !TRE_USE_SYSTEM_REGEX_H */ + +/* If the we're not using system regex.h, we need to define the + structs and enums ourselves. */ + +typedef int regoff_t; +typedef struct { + size_t re_nsub; /* Number of parenthesized subexpressions. */ + void *value; /* For internal use only. */ +} regex_t; + +typedef struct { + regoff_t rm_so; + regoff_t rm_eo; +} regmatch_t; + + +typedef enum { + REG_OK = 0, /* No error. */ + /* POSIX regcomp() return error codes. (In the order listed in the + standard.) */ + REG_NOMATCH, /* No match. */ + REG_BADPAT, /* Invalid regexp. */ + REG_ECOLLATE, /* Unknown collating element. */ + REG_ECTYPE, /* Unknown character class name. */ + REG_EESCAPE, /* Trailing backslash. */ + REG_ESUBREG, /* Invalid back reference. */ + REG_EBRACK, /* "[]" imbalance */ + REG_EPAREN, /* "\(\)" or "()" imbalance */ + REG_EBRACE, /* "\{\}" or "{}" imbalance */ + REG_BADBR, /* Invalid content of {} */ + REG_ERANGE, /* Invalid use of range operator */ + REG_ESPACE, /* Out of memory. */ + REG_BADRPT /* Invalid use of repetition operators. */ +} reg_errcode_t; + +/* POSIX regcomp() flags. */ +#define REG_EXTENDED 1 +#define REG_ICASE (REG_EXTENDED << 1) +#define REG_NEWLINE (REG_ICASE << 1) +#define REG_NOSUB (REG_NEWLINE << 1) + +/* Extra regcomp() flags. */ +#define REG_BASIC 0 +#define REG_LITERAL (REG_NOSUB << 1) +#define REG_RIGHT_ASSOC (REG_LITERAL << 1) +#define REG_UNGREEDY (REG_RIGHT_ASSOC << 1) + +/* POSIX regexec() flags. */ +#define REG_NOTBOL 1 +#define REG_NOTEOL (REG_NOTBOL << 1) + +/* Extra regexec() flags. */ +#define REG_APPROX_MATCHER (REG_NOTEOL << 1) +#define REG_BACKTRACKING_MATCHER (REG_APPROX_MATCHER << 1) + +#endif /* !TRE_USE_SYSTEM_REGEX_H */ + +/* REG_NOSPEC and REG_LITERAL mean the same thing. */ +#if defined(REG_LITERAL) && !defined(REG_NOSPEC) +#define REG_NOSPEC REG_LITERAL +#elif defined(REG_NOSPEC) && !defined(REG_LITERAL) +#define REG_LITERAL REG_NOSPEC +#endif /* defined(REG_NOSPEC) */ + +/* The maximum number of iterations in a bound expression. */ +#undef RE_DUP_MAX +#define RE_DUP_MAX 255 + +/* The POSIX.2 regexp functions */ +extern int +regcomp(regex_t *preg, const char *regex, int cflags); + +extern int +regexec(const regex_t *preg, const char *string, size_t nmatch, + regmatch_t pmatch[], int eflags); + +extern size_t +regerror(int errcode, const regex_t *preg, char *errbuf, + size_t errbuf_size); + +extern void +regfree(regex_t *preg); + +#ifdef TRE_WCHAR +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ + +/* Wide character versions (not in POSIX.2). */ +extern int +regwcomp(regex_t *preg, const wchar_t *regex, int cflags); + +extern int +regwexec(const regex_t *preg, const wchar_t *string, + size_t nmatch, regmatch_t pmatch[], int eflags); +#endif /* TRE_WCHAR */ + +/* Versions with a maximum length argument and therefore the capability to + handle null characters in the middle of the strings (not in POSIX.2). */ +extern int +regncomp(regex_t *preg, const char *regex, size_t len, int cflags); + +extern int +regnexec(const regex_t *preg, const char *string, size_t len, + size_t nmatch, regmatch_t pmatch[], int eflags); + +#ifdef TRE_WCHAR +extern int +regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags); + +extern int +regwnexec(const regex_t *preg, const wchar_t *string, size_t len, + size_t nmatch, regmatch_t pmatch[], int eflags); +#endif /* TRE_WCHAR */ + + +/* Approximate matching parameter struct. */ +typedef struct { + int cost_ins; /* Default cost of an inserted character. */ + int cost_del; /* Default cost of a deleted character. */ + int cost_subst; /* Default cost of a substituted character. */ + int max_cost; /* Maximum allowed cost of a match. */ + + int max_ins; /* Maximum allowed number of inserts. */ + int max_del; /* Maximum allowed number of deletes. */ + int max_subst; /* Maximum allowed number of substitutes. */ + int max_err; /* Maximum allowed number of errors total. */ +} regaparams_t; + +/* Approximate matching result struct. */ +typedef struct { + size_t nmatch; /* Length of pmatch[] array. */ + regmatch_t *pmatch; /* Submatch data. */ + int cost; /* Cost of the match. */ + int num_ins; /* Number of inserts in the match. */ + int num_del; /* Number of deletes in the match. */ + int num_subst; /* Number of substitutes in the match. */ +} regamatch_t; + +#ifdef TRE_APPROX + +/* Approximate matching functions. */ +extern int +regaexec(const regex_t *preg, const char *string, + regamatch_t *match, regaparams_t params, int eflags); + +extern int +reganexec(const regex_t *preg, const char *string, size_t len, + regamatch_t *match, regaparams_t params, int eflags); +#ifdef TRE_WCHAR +/* Wide character approximate matching. */ +extern int +regawexec(const regex_t *preg, const wchar_t *string, + regamatch_t *match, regaparams_t params, int eflags); + +extern int +regawnexec(const regex_t *preg, const wchar_t *string, size_t len, + regamatch_t *match, regaparams_t params, int eflags); +#endif /* TRE_WCHAR */ + +/* Sets the parameters to default values. */ +extern void +regaparams_default(regaparams_t *params); +#endif /* TRE_APPROX */ + +#ifdef TRE_WCHAR +typedef wchar_t tre_char_t; +#else /* !TRE_WCHAR */ +typedef unsigned char tre_char_t; +#endif /* !TRE_WCHAR */ + +typedef struct { + int (*get_next_char)(tre_char_t *c, unsigned int *pos_add, void *context); + void (*rewind)(size_t pos, void *context); + int (*compare)(size_t pos1, size_t pos2, size_t len, void *context); + void *context; +} tre_str_source; + +extern int +reguexec(const regex_t *preg, const tre_str_source *string, + size_t nmatch, regmatch_t pmatch[], int eflags); + +/* Returns the version string. The returned string is static. */ +extern char * +tre_version(void); + +/* Returns the value for a config parameter. The type to which `result' + must point to depends of the value of `query', see documentation for + more details. */ +extern int +tre_config(int query, void *result); + +enum { + TRE_CONFIG_APPROX, + TRE_CONFIG_WCHAR, + TRE_CONFIG_MULTIBYTE, + TRE_CONFIG_SYSTEM_ABI, + TRE_CONFIG_VERSION +}; + +/* Returns 1 if the compiled pattern has back references, 0 if not. */ +extern int +tre_have_backrefs(const regex_t *preg); + +/* Returns 1 if the compiled pattern uses approximate matching features, + 0 if not. */ +extern int +tre_have_approx(const regex_t *preg); + +#ifdef __cplusplus +} +#endif +#endif /* TRE_REGEX_H */ + +/* EOF */ +/* + tre-internal.h - TRE internal definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifndef TRE_INTERNAL_H +#define TRE_INTERNAL_H 1 + +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ + +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* !HAVE_WCTYPE_H */ + +#include <ctype.h> + +#ifdef TRE_DEBUG +#include <stdio.h> +#define DPRINT(msg) do {printf msg; fflush(stdout);} while(/*CONSTCOND*/0) +#else /* !TRE_DEBUG */ +#define DPRINT(msg) do { } while(/*CONSTCOND*/0) +#endif /* !TRE_DEBUG */ + +#define elementsof(x) ( sizeof(x) / sizeof(x[0]) ) + +#ifdef HAVE_MBRTOWC +#define tre_mbrtowc(pwc, s, n, ps) (mbrtowc((pwc), (s), (n), (ps))) +#else /* !HAVE_MBRTOWC */ +#ifdef HAVE_MBTOWC +#define tre_mbrtowc(pwc, s, n, ps) (mbtowc((pwc), (s), (n))) +#endif /* HAVE_MBTOWC */ +#endif /* !HAVE_MBRTOWC */ + +#ifdef TRE_MULTIBYTE +#ifdef HAVE_MBSTATE_T +#define TRE_MBSTATE +#endif /* TRE_MULTIBYTE */ +#endif /* HAVE_MBSTATE_T */ + +/* Define the character types and functions. */ +#ifdef TRE_WCHAR + +/* Wide characters. */ +typedef wint_t tre_cint_t; +#define TRE_CHAR_MAX WCHAR_MAX + +#ifdef TRE_MULTIBYTE +#define TRE_MB_CUR_MAX MB_CUR_MAX +#else /* !TRE_MULTIBYTE */ +#define TRE_MB_CUR_MAX 1 +#endif /* !TRE_MULTIBYTE */ + +#define tre_isalnum iswalnum +#define tre_isalpha iswalpha +#ifdef HAVE_ISWBLANK +#define tre_isblank iswblank +#endif /* HAVE_ISWBLANK */ +#define tre_iscntrl iswcntrl +#define tre_isdigit iswdigit +#define tre_isgraph iswgraph +#define tre_islower iswlower +#define tre_isprint iswprint +#define tre_ispunct iswpunct +#define tre_isspace iswspace +#define tre_isupper iswupper +#define tre_isxdigit iswxdigit + +#define tre_tolower towlower +#define tre_toupper towupper +#define tre_strlen wcslen + +#else /* !TRE_WCHAR */ + +/* 8 bit characters. */ +typedef short tre_cint_t; +#define TRE_CHAR_MAX 255 +#define TRE_MB_CUR_MAX 1 + +#define tre_isalnum isalnum +#define tre_isalpha isalpha +#ifdef HAVE_ISASCII +#define tre_isascii isascii +#endif /* HAVE_ISASCII */ +#ifdef HAVE_ISBLANK +#define tre_isblank isblank +#endif /* HAVE_ISBLANK */ +#define tre_iscntrl iscntrl +#define tre_isdigit isdigit +#define tre_isgraph isgraph +#define tre_islower islower +#define tre_isprint isprint +#define tre_ispunct ispunct +#define tre_isspace isspace +#define tre_isupper isupper +#define tre_isxdigit isxdigit + +#define tre_tolower(c) (tre_cint_t)(tolower(c)) +#define tre_toupper(c) (tre_cint_t)(toupper(c)) +#define tre_strlen(s) (strlen((const char*)s)) + +#endif /* !TRE_WCHAR */ + +#if defined(TRE_WCHAR) && defined(HAVE_ISWCTYPE) && defined(HAVE_WCTYPE) +#define TRE_USE_SYSTEM_WCTYPE 1 +#endif + +#ifdef TRE_USE_SYSTEM_WCTYPE +/* Use system provided iswctype() and wctype(). */ +typedef wctype_t tre_ctype_t; +#define tre_isctype iswctype +#define tre_ctype wctype +#else /* !TRE_USE_SYSTEM_WCTYPE */ +/* Define our own versions of iswctype() and wctype(). */ +typedef int (*tre_ctype_t)(tre_cint_t); +#define tre_isctype(c, type) ( (type)(c) ) +tre_ctype_t tre_ctype(const char *name); +#endif /* !TRE_USE_SYSTEM_WCTYPE */ + +typedef enum { STR_WIDE, STR_BYTE, STR_MBS, STR_USER } tre_str_type_t; + +/* Returns number of bytes to add to (char *)ptr to make it + properly aligned for the type. */ +#define ALIGN(ptr, type) \ + ((((long)ptr) % sizeof(type)) \ + ? (sizeof(type) - (((long)ptr) % sizeof(type))) \ + : 0) + +#undef MAX +#undef MIN +#define MAX(a, b) (((a) >= (b)) ? (a) : (b)) +#define MIN(a, b) (((a) <= (b)) ? (a) : (b)) + +/* Define STRF to the correct printf formatter for strings. */ +#ifdef TRE_WCHAR +#define STRF "ls" +#else /* !TRE_WCHAR */ +#define STRF "s" +#endif /* !TRE_WCHAR */ + +/* TNFA transition type. A TNFA state is an array of transitions, + the terminator is a transition with NULL `state'. */ +typedef struct tnfa_transition tre_tnfa_transition_t; + +struct tnfa_transition { + /* Range of accepted characters. */ + tre_cint_t code_min; + tre_cint_t code_max; + /* Pointer to the destination state. */ + tre_tnfa_transition_t *state; + /* ID number of the destination state. */ + int state_id; + /* -1 terminated array of tags (or NULL). */ + int *tags; + /* Matching parameters settings (or NULL). */ + int *params; + /* Assertion bitmap. */ + int assertions; + /* Assertion parameters. */ + union { + /* Character class assertion. */ + tre_ctype_t class; + /* Back reference assertion. */ + int backref; + } u; + /* Negative character class assertions. */ + tre_ctype_t *neg_classes; +}; + + +/* Assertions. */ +#define ASSERT_AT_BOL 1 /* Beginning of line. */ +#define ASSERT_AT_EOL 2 /* End of line. */ +#define ASSERT_CHAR_CLASS 4 /* Character class in `class'. */ +#define ASSERT_CHAR_CLASS_NEG 8 /* Character classes in `neg_classes'. */ +#define ASSERT_AT_BOW 16 /* Beginning of word. */ +#define ASSERT_AT_EOW 32 /* End of word. */ +#define ASSERT_AT_WB 64 /* Word boundary. */ +#define ASSERT_AT_WB_NEG 128 /* Not a word boundary. */ +#define ASSERT_BACKREF 256 /* A back reference in `backref'. */ +#define ASSERT_LAST 256 + +/* Tag directions. */ +typedef enum { + TRE_TAG_MINIMIZE = 0, + TRE_TAG_MAXIMIZE = 1 +} tre_tag_direction_t; + +/* Parameters that can be changed dynamically while matching. */ +typedef enum { + TRE_PARAM_COST_INS = 0, + TRE_PARAM_COST_DEL = 1, + TRE_PARAM_COST_SUBST = 2, + TRE_PARAM_COST_MAX = 3, + TRE_PARAM_MAX_INS = 4, + TRE_PARAM_MAX_DEL = 5, + TRE_PARAM_MAX_SUBST = 6, + TRE_PARAM_MAX_ERR = 7, + TRE_PARAM_DEPTH = 8, + TRE_PARAM_LAST = 9 +} tre_param_t; + +/* Unset matching parameter */ +#define TRE_PARAM_UNSET -1 + +/* Signifies the default matching parameter value. */ +#define TRE_PARAM_DEFAULT -2 + +/* Instructions to compute submatch register values from tag values + after a successful match. */ +struct tre_submatch_data { + /* Tag that gives the value for rm_so (submatch start offset). */ + int so_tag; + /* Tag that gives the value for rm_eo (submatch end offset). */ + int eo_tag; + /* List of submatches this submatch is contained in. */ + int *parents; +}; + +typedef struct tre_submatch_data tre_submatch_data_t; + + +/* TNFA definition. */ +typedef struct tnfa tre_tnfa_t; + +struct tnfa { + tre_tnfa_transition_t *transitions; + unsigned int num_transitions; + tre_tnfa_transition_t *initial; + tre_tnfa_transition_t *final; + tre_submatch_data_t *submatch_data; + char *firstpos_chars; + int first_char; + unsigned int num_submatches; + tre_tag_direction_t *tag_directions; + int *minimal_tags; + int num_tags; + int num_minimals; + int end_tag; + int num_states; + int cflags; + int have_backrefs; + int have_approx; + int params_depth; +}; + +int +tre_compile(regex_t *preg, const tre_char_t *regex, size_t n, int cflags); + +void +tre_free(regex_t *preg); + +void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, int *tags, int match_eo); + +reg_errcode_t +tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, int len, + tre_str_type_t type, int *match_tags, int eflags, + int *match_end_ofs); + +reg_errcode_t +tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, int len, + tre_str_type_t type, int *match_tags, int eflags, + int *match_end_ofs); + +reg_errcode_t +tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, + int len, tre_str_type_t type, int *match_tags, + int eflags, int *match_end_ofs); + +#ifdef TRE_APPROX +reg_errcode_t +tre_tnfa_run_approx(const tre_tnfa_t *tnfa, const void *string, int len, + tre_str_type_t type, int *match_tags, + regamatch_t *match, regaparams_t params, + int eflags, int *match_end_ofs); +#endif /* TRE_APPROX */ + +#endif /* TRE_INTERNAL_H */ + +/* EOF */ +/* + xmalloc.h - Simple malloc debugging library API + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifndef _XMALLOC_H +#define _XMALLOC_H 1 + +void *xmalloc_impl(size_t size, const char *file, int line, const char *func); +void *xcalloc_impl(size_t nmemb, size_t size, const char *file, int line, + const char *func); +void xfree_impl(void *ptr, const char *file, int line, const char *func); +void *xrealloc_impl(void *ptr, size_t new_size, const char *file, int line, + const char *func); +int xmalloc_dump_leaks(void); +void xmalloc_configure(int fail_after); + + +#ifndef XMALLOC_INTERNAL +#ifdef MALLOC_DEBUGGING + +/* Version 2.4 and later of GCC define a magical variable `__PRETTY_FUNCTION__' + which contains the name of the function currently being defined. +# define __XMALLOC_FUNCTION __PRETTY_FUNCTION__ + This is broken in G++ before version 2.6. + C9x has a similar variable called __func__, but prefer the GCC one since + it demangles C++ function names. */ +# ifdef __GNUC__ +# if __GNUC__ > 2 || (__GNUC__ == 2 \ + && __GNUC_MINOR__ >= (defined __cplusplus ? 6 : 4)) +# define __XMALLOC_FUNCTION __PRETTY_FUNCTION__ +# else +# define __XMALLOC_FUNCTION ((const char *) 0) +# endif +# else +# if defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L +# define __XMALLOC_FUNCTION __func__ +# else +# define __XMALLOC_FUNCTION ((const char *) 0) +# endif +# endif + +#define xmalloc(size) xmalloc_impl(size, __FILE__, __LINE__, \ + __XMALLOC_FUNCTION) +#define xcalloc(nmemb, size) xcalloc_impl(nmemb, size, __FILE__, __LINE__, \ + __XMALLOC_FUNCTION) +#define xfree(ptr) xfree_impl(ptr, __FILE__, __LINE__, __XMALLOC_FUNCTION) +#define xrealloc(ptr, new_size) xrealloc_impl(ptr, new_size, __FILE__, \ + __LINE__, __XMALLOC_FUNCTION) +#undef malloc +#undef calloc +#undef free +#undef realloc + +#define malloc USE_XMALLOC_INSTEAD_OF_MALLOC +#define calloc USE_XCALLOC_INSTEAD_OF_CALLOC +#define free USE_XFREE_INSTEAD_OF_FREE +#define realloc USE_XREALLOC_INSTEAD_OF_REALLOC + +#else /* !MALLOC_DEBUGGING */ + +#include <stdlib.h> + +#define xmalloc(size) malloc(size) +#define xcalloc(nmemb, size) calloc(nmemb, size) +#define xfree(ptr) free(ptr) +#define xrealloc(ptr, new_size) realloc(ptr, new_size) + +#endif /* !MALLOC_DEBUGGING */ +#endif /* !XMALLOC_INTERNAL */ + +#endif /* _XMALLOC_H */ + +/* EOF */ + +int +regncomp(regex_t *preg, const char *regex, size_t n, int cflags) +{ + int ret; +#if TRE_WCHAR + tre_char_t *wregex; + int wlen; + + wregex = xmalloc(sizeof(tre_char_t) * (n + 1)); + if (wregex == NULL) + return REG_ESPACE; + + /* If the current locale uses the standard single byte encoding of + characters, we don't do a multibyte string conversion. If we did, + many applications which use the default locale would break since + the default "C" locale uses the 7-bit ASCII character set, and + all characters with the eighth bit set would be considered invalid. */ +#if TRE_MULTIBYTE + if (TRE_MB_CUR_MAX == 1) +#endif /* TRE_MULTIBYTE */ + { + unsigned int i; + const unsigned char *str = (const unsigned char *)regex; + tre_char_t *wstr = wregex; + + for (i = 0; i < n; i++) + *(wstr++) = *(str++); + wlen = n; + } +#if TRE_MULTIBYTE + else + { + int consumed; + tre_char_t *wcptr = wregex; +#ifdef HAVE_MBSTATE_T + mbstate_t state; + memset(&state, '\0', sizeof(state)); +#endif /* HAVE_MBSTATE_T */ + while (n > 0) + { + consumed = tre_mbrtowc(wcptr, regex, n, &state); + + switch (consumed) + { + case 0: + if (*regex == '\0') + consumed = 1; + else + { + xfree(wregex); + return REG_BADPAT; + } + break; + case -1: + DPRINT(("mbrtowc: error %d: %s.\n", errno, strerror(errno))); + xfree(wregex); + return REG_BADPAT; + case -2: + /* The last character wasn't complete. Let's not call it a + fatal error. */ + consumed = n; + break; + } + regex += consumed; + n -= consumed; + wcptr++; + } + wlen = wcptr - wregex; + } +#endif /* TRE_MULTIBYTE */ + + wregex[wlen] = L'\0'; + ret = tre_compile(preg, wregex, (unsigned)wlen, cflags); + xfree(wregex); +#else /* !TRE_WCHAR */ + ret = tre_compile(preg, (const tre_char_t *)regex, n, cflags); +#endif /* !TRE_WCHAR */ + + return ret; +} + +int +regcomp(regex_t *preg, const char *regex, int cflags) +{ + return regncomp(preg, regex, regex ? strlen(regex) : 0, cflags); +} + + +#ifdef TRE_WCHAR +int +regwncomp(regex_t *preg, const wchar_t *regex, size_t n, int cflags) +{ + return tre_compile(preg, regex, n, cflags); +} + +int +regwcomp(regex_t *preg, const wchar_t *regex, int cflags) +{ + return tre_compile(preg, regex, regex ? wcslen(regex) : 0, cflags); +} +#endif /* TRE_WCHAR */ + +void +regfree(regex_t *preg) +{ + tre_free(preg); +} + +/* EOF */ +/* + regerror.c - POSIX regerror() implementation for TRE. + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +#include <string.h> +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* HAVE_WCTYPE_H */ + +#define dgettext(p, s) s +#define gettext(s) s + +#define _(String) dgettext(PACKAGE, String) +#define gettext_noop(String) String + +/* Error message strings for error codes listed in `regex.h'. This list + needs to be in sync with the codes listed there, naturally. */ +static const char *tre_error_messages[] = + { gettext_noop("No error"), /* REG_OK */ + gettext_noop("No match"), /* REG_NOMATCH */ + gettext_noop("Invalid regexp"), /* REG_BADPAT */ + gettext_noop("Unknown collating element"), /* REG_ECOLLATE */ + gettext_noop("Unknown character class name"), /* REG_ECTYPE */ + gettext_noop("Trailing backslash"), /* REG_EESCAPE */ + gettext_noop("Invalid back reference"), /* REG_ESUBREG */ + gettext_noop("Missing ']'"), /* REG_EBRACK */ + gettext_noop("Missing ')'"), /* REG_EPAREN */ + gettext_noop("Missing '}'"), /* REG_EBRACE */ + gettext_noop("Invalid contents of {}"), /* REG_BADBR */ + gettext_noop("Invalid character range"), /* REG_ERANGE */ + gettext_noop("Out of memory"), /* REG_ESPACE */ + gettext_noop("Invalid use of repetition operators") /* REG_BADRPT */ + }; + +size_t +regerror(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size) +{ + const char *err; + size_t err_len; + + /*LINTED*/(void)&preg; + if (errcode >= 0 + && errcode < (int)(sizeof(tre_error_messages) + / sizeof(*tre_error_messages))) + err = gettext(tre_error_messages[errcode]); + else + err = gettext("Unknown error"); + + err_len = strlen(err) + 1; + if (errbuf_size > 0 && errbuf != NULL) + { + if (err_len > errbuf_size) + { + strncpy(errbuf, err, errbuf_size - 1); + errbuf[errbuf_size - 1] = '\0'; + } + else + { + strcpy(errbuf, err); + } + } + return err_len; +} + +/* EOF */ +/* + regexec.c - TRE POSIX compatible matching functions (and more). + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +#ifdef TRE_USE_ALLOCA +/* AIX requires this to be the first thing in the file. */ +#ifndef __GNUC__ +# if HAVE_ALLOCA_H +# include <alloca.h> +# else +# ifdef _AIX + #pragma alloca +# else +# ifndef alloca /* predefined by HP cc +Olibcalls */ +char *alloca (); +# endif +# endif +# endif +#endif +#endif /* TRE_USE_ALLOCA */ + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* HAVE_WCTYPE_H */ +#ifndef TRE_WCHAR +#include <ctype.h> +#endif /* !TRE_WCHAR */ +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif /* HAVE_MALLOC_H */ +#include <limits.h> + + + +/* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match + endpoint values. */ +void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, int *tags, int match_eo) +{ + tre_submatch_data_t *submatch_data; + unsigned int i, j; + int *parents; + + i = 0; + if (match_eo >= 0 && !(cflags & REG_NOSUB)) + { + /* Construct submatch offsets from the tags. */ + DPRINT(("end tag = t%d = %d\n", tnfa->end_tag, match_eo)); + submatch_data = tnfa->submatch_data; + while (i < tnfa->num_submatches && i < nmatch) + { + if (submatch_data[i].so_tag == tnfa->end_tag) + pmatch[i].rm_so = match_eo; + else + pmatch[i].rm_so = tags[submatch_data[i].so_tag]; + + if (submatch_data[i].eo_tag == tnfa->end_tag) + pmatch[i].rm_eo = match_eo; + else + pmatch[i].rm_eo = tags[submatch_data[i].eo_tag]; + + /* If either of the endpoints were not used, this submatch + was not part of the match. */ + if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + + DPRINT(("pmatch[%d] = {t%d = %d, t%d = %d}\n", i, + submatch_data[i].so_tag, pmatch[i].rm_so, + submatch_data[i].eo_tag, pmatch[i].rm_eo)); + i++; + } + /* Reset all submatches that are not within all of their parent + submatches. */ + i = 0; + while (i < tnfa->num_submatches && i < nmatch) + { + if (pmatch[i].rm_eo == -1) + assert(pmatch[i].rm_so == -1); + assert(pmatch[i].rm_so <= pmatch[i].rm_eo); + + parents = submatch_data[i].parents; + if (parents != NULL) + for (j = 0; parents[j] >= 0; j++) + { + DPRINT(("pmatch[%d] parent %d\n", i, parents[j])); + if (pmatch[i].rm_so < pmatch[parents[j]].rm_so + || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + } + i++; + } + } + + while (i < nmatch) + { + pmatch[i].rm_so = -1; + pmatch[i].rm_eo = -1; + i++; + } +} + + +/* + Wrapper functions for POSIX compatible regexp matching. +*/ + +int +tre_have_backrefs(const regex_t *preg) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + return tnfa->have_backrefs; +} + +int +tre_have_approx(const regex_t *preg) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + return tnfa->have_approx; +} + +static int +tre_match(const tre_tnfa_t *tnfa, const void *string, size_t len, + tre_str_type_t type, size_t nmatch, regmatch_t pmatch[], + int eflags) +{ + reg_errcode_t status; + int *tags = NULL, eo; + if (tnfa->num_tags > 0 && nmatch > 0) + { +#ifdef TRE_USE_ALLOCA + tags = alloca(sizeof(*tags) * tnfa->num_tags); +#else /* !TRE_USE_ALLOCA */ + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); +#endif /* !TRE_USE_ALLOCA */ + if (tags == NULL) + return REG_ESPACE; + } + + /* Dispatch to the appropriate matcher. */ + if (tnfa->have_backrefs || eflags & REG_BACKTRACKING_MATCHER) + { + /* The regex has back references, use the backtracking matcher. */ + if (type == STR_USER) + { + const tre_str_source *source = string; + if (source->rewind == NULL || source->compare == NULL) + /* The backtracking matcher requires rewind and compare + capabilities from the input stream. */ + return REG_BADPAT; + } + status = tre_tnfa_run_backtrack(tnfa, string, (int)len, type, + tags, eflags, &eo); + } +#ifdef TRE_APPROX + else if (tnfa->have_approx || eflags & REG_APPROX_MATCHER) + { + /* The regex uses approximate matching, use the approximate matcher. */ + regamatch_t match; + regaparams_t params; + regaparams_default(¶ms); + params.max_err = 0; + params.max_cost = 0; + status = tre_tnfa_run_approx(tnfa, string, (int)len, type, tags, + &match, params, eflags, &eo); + } +#endif /* TRE_APPROX */ + else + { + /* Exact matching, no back references, use the parallel matcher. */ + status = tre_tnfa_run_parallel(tnfa, string, (int)len, type, + tags, eflags, &eo); + } + + if (status == REG_OK) + /* A match was found, so fill the submatch registers. */ + tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo); +#ifndef TRE_USE_ALLOCA + if (tags) + xfree(tags); +#endif /* !TRE_USE_ALLOCA */ + return status; +} + +int +regnexec(const regex_t *preg, const char *str, size_t len, + size_t nmatch, regmatch_t pmatch[], int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + tre_str_type_t type = (TRE_MB_CUR_MAX == 1) ? STR_BYTE : STR_MBS; + + return tre_match(tnfa, str, len, type, nmatch, pmatch, eflags); +} + +int +regexec(const regex_t *preg, const char *str, + size_t nmatch, regmatch_t pmatch[], int eflags) +{ + return regnexec(preg, str, (unsigned)-1, nmatch, pmatch, eflags); +} + + +#ifdef TRE_WCHAR + +int +regwnexec(const regex_t *preg, const wchar_t *str, size_t len, + size_t nmatch, regmatch_t pmatch[], int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + return tre_match(tnfa, str, len, STR_WIDE, nmatch, pmatch, eflags); +} + +int +regwexec(const regex_t *preg, const wchar_t *str, + size_t nmatch, regmatch_t pmatch[], int eflags) +{ + return regwnexec(preg, str, (unsigned)-1, nmatch, pmatch, eflags); +} + +#endif /* TRE_WCHAR */ + +int +reguexec(const regex_t *preg, const tre_str_source *str, + size_t nmatch, regmatch_t pmatch[], int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + return tre_match(tnfa, str, (unsigned)-1, STR_USER, nmatch, pmatch, eflags); +} + + +#ifdef TRE_APPROX + +/* + Wrapper functions for approximate regexp matching. +*/ + +static int +tre_match_approx(const tre_tnfa_t *tnfa, const void *string, size_t len, + tre_str_type_t type, regamatch_t *match, regaparams_t params, + int eflags) +{ + reg_errcode_t status; + int *tags = NULL, eo; + + /* If the regexp does not use approximate matching features, the + maximum cost is zero, and the approximate matcher isn't forced, + use the exact matcher instead. */ + if (params.max_cost == 0 && !tnfa->have_approx + && !(eflags & REG_APPROX_MATCHER)) + return tre_match(tnfa, string, len, type, match->nmatch, match->pmatch, + eflags); + + /* Back references are not supported by the approximate matcher. */ + if (tnfa->have_backrefs) + return REG_BADPAT; + + if (tnfa->num_tags > 0 && match->nmatch > 0) + { +#if TRE_USE_ALLOCA + tags = alloca(sizeof(*tags) * tnfa->num_tags); +#else /* !TRE_USE_ALLOCA */ + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); +#endif /* !TRE_USE_ALLOCA */ + if (tags == NULL) + return REG_ESPACE; + } + status = tre_tnfa_run_approx(tnfa, string, (int)len, type, tags, + match, params, eflags, &eo); + if (status == REG_OK) + tre_fill_pmatch(match->nmatch, match->pmatch, tnfa->cflags, tnfa, tags, eo); +#ifndef TRE_USE_ALLOCA + if (tags) + xfree(tags); +#endif /* !TRE_USE_ALLOCA */ + return status; +} + +int +reganexec(const regex_t *preg, const char *str, size_t len, + regamatch_t *match, regaparams_t params, int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + tre_str_type_t type = (TRE_MB_CUR_MAX == 1) ? STR_BYTE : STR_MBS; + + return tre_match_approx(tnfa, str, len, type, match, params, eflags); +} + +int +regaexec(const regex_t *preg, const char *str, + regamatch_t *match, regaparams_t params, int eflags) +{ + return reganexec(preg, str, (unsigned)-1, match, params, eflags); +} + +#ifdef TRE_WCHAR + +int +regawnexec(const regex_t *preg, const wchar_t *str, size_t len, + regamatch_t *match, regaparams_t params, int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + return tre_match_approx(tnfa, str, len, STR_WIDE, + match, params, eflags); +} + +int +regawexec(const regex_t *preg, const wchar_t *str, + regamatch_t *match, regaparams_t params, int eflags) +{ + return regawnexec(preg, str, (unsigned)-1, match, params, eflags); +} + +#endif /* TRE_WCHAR */ + +void +regaparams_default(regaparams_t *params) +{ + memset(params, 0, sizeof(*params)); + params->cost_ins = 1; + params->cost_del = 1; + params->cost_subst = 1; + params->max_cost = INT_MAX; + params->max_ins = INT_MAX; + params->max_del = INT_MAX; + params->max_subst = INT_MAX; + params->max_err = INT_MAX; +} + +#endif /* TRE_APPROX */ + +/* EOF */ +/* + tre-ast.c - Abstract syntax tree (AST) routines + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ +#include <assert.h> + +/* + tre-ast.h - Abstract syntax tree (AST) definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + + +#ifndef TRE_AST_H +#define TRE_AST_H 1 + +/* + tre-mem.h - TRE memory allocator interface + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifndef TRE_MEM_H +#define TRE_MEM_H 1 + +#include <stdlib.h> + +#define TRE_MEM_BLOCK_SIZE 1024 + +typedef struct tre_list { + void *data; + struct tre_list *next; +} tre_list_t; + +typedef struct tre_mem_struct { + tre_list_t *blocks; + tre_list_t *current; + char *ptr; + size_t n; + int failed; + void **provided; +} *tre_mem_t; + + +tre_mem_t tre_mem_new_impl(int provided, void *provided_block); +void *tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block, + int zero, size_t size); + +/* Returns a new memory allocator or NULL if out of memory. */ +#define tre_mem_new() tre_mem_new_impl(0, NULL) + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. */ +#define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size) + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. The memory + is set to zero. */ +#define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size) + +#ifdef TRE_USE_ALLOCA +/* alloca() versions. Like above, but memory is allocated with alloca() + instead of malloc(). */ + +#define tre_mem_newa() \ + tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct))) + +#define tre_mem_alloca(mem, size) \ + ((mem)->n >= (size) \ + ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size)) \ + : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size))) +#endif /* TRE_USE_ALLOCA */ + + +/* Frees the memory allocator and all memory allocated with it. */ +void tre_mem_destroy(tre_mem_t mem); + +#endif /* TRE_MEM_H */ + +/* EOF */ +/* + tre-compile.h: Regex compilation definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + + +#ifndef TRE_COMPILE_H +#define TRE_COMPILE_H 1 + +typedef struct { + int position; + int code_min; + int code_max; + int *tags; + int assertions; + tre_ctype_t class; + tre_ctype_t *neg_classes; + int backref; + int *params; +} tre_pos_and_tags_t; + +#endif /* TRE_COMPILE_H */ + +/* EOF */ + +/* The different AST node types. */ +typedef enum { + LITERAL, + CATENATION, + ITERATION, + UNION +} tre_ast_type_t; + +/* Special subtypes of TRE_LITERAL. */ +#define EMPTY -1 /* Empty leaf (denotes empty string). */ +#define ASSERTION -2 /* Assertion leaf. */ +#define TAG -3 /* Tag leaf. */ +#define BACKREF -4 /* Back reference leaf. */ +#define PARAMETER -5 /* Parameter. */ + +#define IS_SPECIAL(x) ((x)->code_min < 0) +#define IS_EMPTY(x) ((x)->code_min == EMPTY) +#define IS_ASSERTION(x) ((x)->code_min == ASSERTION) +#define IS_TAG(x) ((x)->code_min == TAG) +#define IS_BACKREF(x) ((x)->code_min == BACKREF) +#define IS_PARAMETER(x) ((x)->code_min == PARAMETER) + + +/* A generic AST node. All AST nodes consist of this node on the top + level with `obj' pointing to the actual content. */ +typedef struct { + tre_ast_type_t type; /* Type of the node. */ + void *obj; /* Pointer to actual node. */ + int nullable; + int submatch_id; + int num_submatches; + int num_tags; + tre_pos_and_tags_t *firstpos; + tre_pos_and_tags_t *lastpos; +} tre_ast_node_t; + + +/* A "literal" node. These are created for assertions, back references, + tags, matching parameter settings, and all expressions that match one + character. */ +typedef struct { + long code_min; + long code_max; + int position; + union { + tre_ctype_t class; + int *params; + } u; + tre_ctype_t *neg_classes; +} tre_literal_t; + +/* A "catenation" node. These are created when two regexps are concatenated. + If there are more than one subexpressions in sequence, the `left' part + holds all but the last, and `right' part holds the last subexpression + (catenation is left associative). */ +typedef struct { + tre_ast_node_t *left; + tre_ast_node_t *right; +} tre_catenation_t; + +/* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}" + operators. */ +typedef struct { + /* Subexpression to match. */ + tre_ast_node_t *arg; + /* Minimum number of consecutive matches. */ + int min; + /* Maximum number of consecutive matches. */ + int max; + /* If 0, match as many characters as possible, if 1 match as few as + possible. Note that this does not always mean the same thing as + matching as many/few repetitions as possible. */ + unsigned int minimal:1; + /* Approximate matching parameters (or NULL). */ + int *params; +} tre_iteration_t; + +/* An "union" node. These are created for the "|" operator. */ +typedef struct { + tre_ast_node_t *left; + tre_ast_node_t *right; +} tre_union_t; + +tre_ast_node_t * +tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size); + +tre_ast_node_t * +tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position); + +tre_ast_node_t * +tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, + int minimal); + +tre_ast_node_t * +tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right); + +tre_ast_node_t * +tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, + tre_ast_node_t *right); + +#ifdef TRE_DEBUG +void +tre_ast_print(tre_ast_node_t *tree); + +/* XXX - rethink AST printing API */ +void +tre_print_params(int *params); +#endif /* TRE_DEBUG */ + +#endif /* TRE_AST_H */ + +/* EOF */ + +tre_ast_node_t * +tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size) +{ + tre_ast_node_t *node; + + node = tre_mem_calloc(mem, sizeof(*node)); + if (!node) + return NULL; + node->obj = tre_mem_calloc(mem, size); + if (!node->obj) + return NULL; + node->type = type; + node->nullable = -1; + node->submatch_id = -1; + + return node; +} + +tre_ast_node_t * +tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position) +{ + tre_ast_node_t *node; + tre_literal_t *lit; + + node = tre_ast_new_node(mem, LITERAL, sizeof(tre_literal_t)); + if (!node) + return NULL; + lit = node->obj; + lit->code_min = code_min; + lit->code_max = code_max; + lit->position = position; + + return node; +} + +tre_ast_node_t * +tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, + int minimal) +{ + tre_ast_node_t *node; + tre_iteration_t *iter; + + node = tre_ast_new_node(mem, ITERATION, sizeof(tre_iteration_t)); + if (!node) + return NULL; + iter = node->obj; + iter->arg = arg; + iter->min = min; + iter->max = max; + iter->minimal = minimal; + node->num_submatches = arg->num_submatches; + + return node; +} + +tre_ast_node_t * +tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right) +{ + tre_ast_node_t *node; + + node = tre_ast_new_node(mem, UNION, sizeof(tre_union_t)); + if (node == NULL) + return NULL; + ((tre_union_t *)node->obj)->left = left; + ((tre_union_t *)node->obj)->right = right; + node->num_submatches = left->num_submatches + right->num_submatches; + + return node; +} + +tre_ast_node_t * +tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, + tre_ast_node_t *right) +{ + tre_ast_node_t *node; + + node = tre_ast_new_node(mem, CATENATION, sizeof(tre_catenation_t)); + if (node == NULL) + return NULL; + ((tre_catenation_t *)node->obj)->left = left; + ((tre_catenation_t *)node->obj)->right = right; + node->num_submatches = left->num_submatches + right->num_submatches; + + return node; +} + +#ifdef TRE_DEBUG + +static void +tre_findent(FILE *stream, int i) +{ + while (i-- > 0) + fputc(' ', stream); +} + +void +tre_print_params(int *params) +{ + int i; + if (params) + { + DPRINT(("params [")); + for (i = 0; i < TRE_PARAM_LAST; i++) + { + if (params[i] == TRE_PARAM_UNSET) + DPRINT(("unset")); + else if (params[i] == TRE_PARAM_DEFAULT) + DPRINT(("default")); + else + DPRINT(("%d", params[i])); + if (i < TRE_PARAM_LAST - 1) + DPRINT((", ")); + } + DPRINT(("]")); + } +} + +static void +tre_do_print(FILE *stream, tre_ast_node_t *ast, int indent) +{ + int code_min, code_max, pos; + int num_tags = ast->num_tags; + tre_literal_t *lit; + tre_iteration_t *iter; + + tre_findent(stream, indent); + switch (ast->type) + { + case LITERAL: + lit = ast->obj; + code_min = lit->code_min; + code_max = lit->code_max; + pos = lit->position; + if (IS_EMPTY(lit)) + { + fprintf(stream, "literal empty\n"); + } + else if (IS_ASSERTION(lit)) + { + int i; + char *assertions[] = { "bol", "eol", "ctype", "!ctype", + "bow", "eow", "wb", "!wb" }; + if (code_max >= ASSERT_LAST << 1) + assert(0); + fprintf(stream, "assertions: "); + for (i = 0; (1 << i) <= ASSERT_LAST; i++) + if (code_max & (1 << i)) + fprintf(stream, "%s ", assertions[i]); + fprintf(stream, "\n"); + } + else if (IS_TAG(lit)) + { + fprintf(stream, "tag %d\n", code_max); + } + else if (IS_BACKREF(lit)) + { + fprintf(stream, "backref %d, pos %d\n", code_max, pos); + } + else if (IS_PARAMETER(lit)) + { + tre_print_params(lit->u.params); + fprintf(stream, "\n"); + } + else + { + fprintf(stream, "literal (%c, %c) (%d, %d), pos %d, sub %d, " + "%d tags\n", code_min, code_max, code_min, code_max, pos, + ast->submatch_id, num_tags); + } + break; + case ITERATION: + iter = ast->obj; + fprintf(stream, "iteration {%d, %d}, sub %d, %d tags, %s\n", + iter->min, iter->max, ast->submatch_id, num_tags, + iter->minimal ? "minimal" : "greedy"); + tre_do_print(stream, iter->arg, indent + 2); + break; + case UNION: + fprintf(stream, "union, sub %d, %d tags\n", ast->submatch_id, num_tags); + tre_do_print(stream, ((tre_union_t *)ast->obj)->left, indent + 2); + tre_do_print(stream, ((tre_union_t *)ast->obj)->right, indent + 2); + break; + case CATENATION: + fprintf(stream, "catenation, sub %d, %d tags\n", ast->submatch_id, + num_tags); + tre_do_print(stream, ((tre_catenation_t *)ast->obj)->left, indent + 2); + tre_do_print(stream, ((tre_catenation_t *)ast->obj)->right, indent + 2); + break; + default: + assert(0); + break; + } +} + +static void +tre_ast_fprint(FILE *stream, tre_ast_node_t *ast) +{ + tre_do_print(stream, ast, 0); +} + +void +tre_ast_print(tre_ast_node_t *tree) +{ + printf("AST:\n"); + tre_ast_fprint(stdout, tree); +} + +#endif /* TRE_DEBUG */ + +/* EOF */ +/* + tre-compile.c - TRE regex compiler + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + TODO: + - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive + function calls. +*/ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ +#include <stdio.h> +#include <assert.h> +#include <string.h> + +/* + tre-stack.h: Stack definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + + +#ifndef TRE_STACK_H +#define TRE_STACK_H 1 + + +typedef struct tre_stack_rec tre_stack_t; + +/* Creates a new stack object. `size' is initial size in bytes, `max_size' + is maximum size, and `increment' specifies how much more space will be + allocated with realloc() if all space gets used up. Returns the stack + object or NULL if out of memory. */ +tre_stack_t * +tre_stack_new(int size, int max_size, int increment); + +/* Frees the stack object. */ +void +tre_stack_destroy(tre_stack_t *s); + +/* Returns the current number of objects in the stack. */ +int +tre_stack_num_objects(tre_stack_t *s); + +/* Each tre_stack_push_*(tre_stack_t *s, <type> value) function pushes + `value' on top of stack `s'. Returns REG_ESPACE if out of memory. + This tries to realloc() more space before failing if maximum size + has not yet been reached. Returns REG_OK if successful. */ +#define declare_pushf(typetag, type) \ + reg_errcode_t tre_stack_push_ ## typetag(tre_stack_t *s, type value) + +declare_pushf(voidptr, void *); +declare_pushf(int, int); + +/* Each tre_stack_pop_*(tre_stack_t *s) function pops the topmost + element off of stack `s' and returns it. The stack must not be + empty. */ +#define declare_popf(typetag, type) \ + type tre_stack_pop_ ## typetag(tre_stack_t *s) + +declare_popf(voidptr, void *); +declare_popf(int, int); + +/* Just to save some typing. */ +#define STACK_PUSH(s, typetag, value) \ + do \ + { \ + status = tre_stack_push_ ## typetag(s, value); \ + } \ + while (/*CONSTCOND*/0) + +#define STACK_PUSHX(s, typetag, value) \ + { \ + status = tre_stack_push_ ## typetag(s, value); \ + if (status != REG_OK) \ + break; \ + } + +#define STACK_PUSHR(s, typetag, value) \ + { \ + reg_errcode_t _status; \ + _status = tre_stack_push_ ## typetag(s, value); \ + if (_status != REG_OK) \ + return _status; \ + } + +#endif /* TRE_STACK_H */ + +/* EOF */ +/* + tre-parse.c - Regexp parser definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifndef TRE_PARSE_H +#define TRE_PARSE_H 1 + +/* Parse context. */ +typedef struct { + /* Memory allocator. The AST is allocated using this. */ + tre_mem_t mem; + /* Stack used for keeping track of regexp syntax. */ + tre_stack_t *stack; + /* The parse result. */ + tre_ast_node_t *result; + /* The regexp to parse and its length. */ + const tre_char_t *re; + /* The first character of the entire regexp. */ + const tre_char_t *re_start; + /* The first character after the end of the regexp. */ + const tre_char_t *re_end; + int len; + /* Current submatch ID. */ + int submatch_id; + /* Current position (number of literal). */ + int position; + /* The highest back reference or -1 if none seen so far. */ + int max_backref; + /* This flag is set if the regexp uses approximate matching. */ + int have_approx; + /* Compilation flags. */ + int cflags; + /* If this flag is set the top-level submatch is not captured. */ + int nofirstsub; + /* The currently set approximate matching parameters. */ + int params[TRE_PARAM_LAST]; +} tre_parse_ctx_t; + +/* Parses a wide character regexp pattern into a syntax tree. This parser + handles both syntaxes (BRE and ERE), including the TRE extensions. */ +reg_errcode_t +tre_parse(tre_parse_ctx_t *ctx); + +#endif /* TRE_PARSE_H */ + +/* EOF */ + +/* + Algorithms to setup tags so that submatch addressing can be done. +*/ + + +/* Inserts a catenation node to the root of the tree given in `node'. + As the left child a new tag with number `tag_id' to `node' is added, + and the right child is the old root. */ +static reg_errcode_t +tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id) +{ + tre_catenation_t *c; + + DPRINT(("add_tag_left: tag %d\n", tag_id)); + + c = tre_mem_alloc(mem, sizeof(*c)); + if (c == NULL) + return REG_ESPACE; + c->left = tre_ast_new_literal(mem, TAG, tag_id, -1); + if (c->left == NULL) + return REG_ESPACE; + c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t)); + if (c->right == NULL) + return REG_ESPACE; + + c->right->obj = node->obj; + c->right->type = node->type; + c->right->nullable = -1; + c->right->submatch_id = -1; + c->right->firstpos = NULL; + c->right->lastpos = NULL; + c->right->num_tags = 0; + node->obj = c; + node->type = CATENATION; + return REG_OK; +} + +/* Inserts a catenation node to the root of the tree given in `node'. + As the right child a new tag with number `tag_id' to `node' is added, + and the left child is the old root. */ +static reg_errcode_t +tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id) +{ + tre_catenation_t *c; + + DPRINT(("tre_add_tag_right: tag %d\n", tag_id)); + + c = tre_mem_alloc(mem, sizeof(*c)); + if (c == NULL) + return REG_ESPACE; + c->right = tre_ast_new_literal(mem, TAG, tag_id, -1); + if (c->right == NULL) + return REG_ESPACE; + c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t)); + if (c->left == NULL) + return REG_ESPACE; + + c->left->obj = node->obj; + c->left->type = node->type; + c->left->nullable = -1; + c->left->submatch_id = -1; + c->left->firstpos = NULL; + c->left->lastpos = NULL; + c->left->num_tags = 0; + node->obj = c; + node->type = CATENATION; + return REG_OK; +} + +typedef enum { + ADDTAGS_RECURSE, + ADDTAGS_AFTER_ITERATION, + ADDTAGS_AFTER_UNION_LEFT, + ADDTAGS_AFTER_UNION_RIGHT, + ADDTAGS_AFTER_CAT_LEFT, + ADDTAGS_AFTER_CAT_RIGHT, + ADDTAGS_SET_SUBMATCH_END +} tre_addtags_symbol_t; + + +typedef struct { + int tag; + int next_tag; +} tre_tag_states_t; + + +/* Go through `regset' and set submatch data for submatches that are + using this tag. */ +static void +tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag) +{ + int i; + + for (i = 0; regset[i] >= 0; i++) + { + int id = regset[i] / 2; + int start = !(regset[i] % 2); + DPRINT((" Using tag %d for %s offset of " + "submatch %d\n", tag, + start ? "start" : "end", id)); + if (start) + tnfa->submatch_data[id].so_tag = tag; + else + tnfa->submatch_data[id].eo_tag = tag; + } + regset[0] = -1; +} + + +/* Adds tags to appropriate locations in the parse tree in `tree', so that + subexpressions marked for submatch addressing can be traced. */ +static reg_errcode_t +tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, + tre_tnfa_t *tnfa) +{ + reg_errcode_t status = REG_OK; + tre_addtags_symbol_t symbol; + tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */ + int bottom = tre_stack_num_objects(stack); + /* True for first pass (counting number of needed tags) */ + int first_pass = (mem == NULL || tnfa == NULL); + int *regset, *orig_regset; + int num_tags = 0; /* Total number of tags. */ + int num_minimals = 0; /* Number of special minimal tags. */ + int tag = 0; /* The tag that is to be added next. */ + int next_tag = 1; /* Next tag to use after this one. */ + int *parents; /* Stack of submatches the current submatch is + contained in. */ + int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */ + tre_tag_states_t *saved_states; + + tre_tag_direction_t direction = TRE_TAG_MINIMIZE; + if (!first_pass) + { + tnfa->end_tag = 0; + tnfa->minimal_tags[0] = -1; + } + + regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2)); + if (regset == NULL) + return REG_ESPACE; + regset[0] = -1; + orig_regset = regset; + + parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1)); + if (parents == NULL) + { + xfree(regset); + return REG_ESPACE; + } + parents[0] = -1; + + saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1)); + if (saved_states == NULL) + { + xfree(regset); + xfree(parents); + return REG_ESPACE; + } + else + { + unsigned int i; + for (i = 0; i <= tnfa->num_submatches; i++) + saved_states[i].tag = -1; + } + + STACK_PUSH(stack, voidptr, node); + STACK_PUSH(stack, int, ADDTAGS_RECURSE); + + while (tre_stack_num_objects(stack) > bottom) + { + if (status != REG_OK) + break; + + symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack); + switch (symbol) + { + + case ADDTAGS_SET_SUBMATCH_END: + { + int id = tre_stack_pop_int(stack); + int i; + + /* Add end of this submatch to regset. */ + for (i = 0; regset[i] >= 0; i++); + regset[i] = id * 2 + 1; + regset[i + 1] = -1; + + /* Pop this submatch from the parents stack. */ + for (i = 0; parents[i] >= 0; i++); + parents[i - 1] = -1; + break; + } + + case ADDTAGS_RECURSE: + node = tre_stack_pop_voidptr(stack); + + if (node->submatch_id >= 0) + { + int id = node->submatch_id; + int i; + + + /* Add start of this submatch to regset. */ + for (i = 0; regset[i] >= 0; i++); + regset[i] = id * 2; + regset[i + 1] = -1; + + if (!first_pass) + { + for (i = 0; parents[i] >= 0; i++); + tnfa->submatch_data[id].parents = NULL; + if (i > 0) + { + int *p = xmalloc(sizeof(*p) * (i + 1)); + if (p == NULL) + { + status = REG_ESPACE; + break; + } + assert(tnfa->submatch_data[id].parents == NULL); + tnfa->submatch_data[id].parents = p; + for (i = 0; parents[i] >= 0; i++) + p[i] = parents[i]; + p[i] = -1; + } + } + + /* Add end of this submatch to regset after processing this + node. */ + STACK_PUSHX(stack, int, node->submatch_id); + STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END); + } + + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = node->obj; + + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + int i; + DPRINT(("Literal %d-%d\n", + (int)lit->code_min, (int)lit->code_max)); + if (regset[0] >= 0) + { + /* Regset is not empty, so add a tag before the + literal or backref. */ + if (!first_pass) + { + status = tre_add_tag_left(mem, node, tag); + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + DPRINT(("Minimal %d, %d\n", minimal_tag, tag)); + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + else + { + DPRINT((" num_tags = 1\n")); + node->num_tags = 1; + } + + DPRINT((" num_tags++\n")); + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + } + else + { + assert(!IS_TAG(lit)); + } + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + tre_ast_node_t *left = cat->left; + tre_ast_node_t *right = cat->right; + int reserved_tag = -1; + DPRINT(("Catenation, next_tag = %d\n", next_tag)); + + + /* After processing right child. */ + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT); + + /* Process right child. */ + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* After processing left child. */ + STACK_PUSHX(stack, int, next_tag + left->num_tags); + DPRINT((" Pushing %d for after left\n", + next_tag + left->num_tags)); + if (left->num_tags > 0 && right->num_tags > 0) + { + /* Reserve the next tag to the right child. */ + DPRINT((" Reserving next_tag %d to right child\n", + next_tag)); + reserved_tag = next_tag; + next_tag++; + } + STACK_PUSHX(stack, int, reserved_tag); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT); + + /* Process left child. */ + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + } + break; + case ITERATION: + { + tre_iteration_t *iter = node->obj; + DPRINT(("Iteration\n")); + + if (first_pass) + { + STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal); + } + else + { + STACK_PUSHX(stack, int, tag); + STACK_PUSHX(stack, int, iter->minimal); + } + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION); + + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* Regset is not empty, so add a tag here. */ + if (regset[0] >= 0 || iter->minimal) + { + if (!first_pass) + { + int i; + status = tre_add_tag_left(mem, node, tag); + if (iter->minimal) + tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE; + else + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + DPRINT(("Minimal %d, %d\n", minimal_tag, tag)); + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + + DPRINT((" num_tags++\n")); + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + direction = TRE_TAG_MINIMIZE; + } + break; + case UNION: + { + tre_union_t *uni = node->obj; + tre_ast_node_t *left = uni->left; + tre_ast_node_t *right = uni->right; + int left_tag; + int right_tag; + + if (regset[0] >= 0) + { + left_tag = next_tag; + right_tag = next_tag + 1; + } + else + { + left_tag = tag; + right_tag = next_tag; + } + + DPRINT(("Union\n")); + + /* After processing right child. */ + STACK_PUSHX(stack, int, right_tag); + STACK_PUSHX(stack, int, left_tag); + STACK_PUSHX(stack, voidptr, regset); + STACK_PUSHX(stack, int, regset[0] >= 0); + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT); + + /* Process right child. */ + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* After processing left child. */ + STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT); + + /* Process left child. */ + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* Regset is not empty, so add a tag here. */ + if (regset[0] >= 0) + { + if (!first_pass) + { + int i; + status = tre_add_tag_left(mem, node, tag); + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + DPRINT(("Minimal %d, %d\n", minimal_tag, tag)); + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + + DPRINT((" num_tags++\n")); + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + + if (node->num_submatches > 0) + { + /* The next two tags are reserved for markers. */ + next_tag++; + tag = next_tag; + next_tag++; + } + + break; + } + } + + if (node->submatch_id >= 0) + { + int i; + /* Push this submatch on the parents stack. */ + for (i = 0; parents[i] >= 0; i++); + parents[i] = node->submatch_id; + parents[i + 1] = -1; + } + + break; /* end case: ADDTAGS_RECURSE */ + + case ADDTAGS_AFTER_ITERATION: + { + int minimal = 0; + int enter_tag; + node = tre_stack_pop_voidptr(stack); + if (first_pass) + { + node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags + + tre_stack_pop_int(stack); + minimal_tag = -1; + } + else + { + minimal = tre_stack_pop_int(stack); + enter_tag = tre_stack_pop_int(stack); + if (minimal) + minimal_tag = enter_tag; + } + + DPRINT(("After iteration\n")); + if (!first_pass) + { + DPRINT((" Setting direction to %s\n", + minimal ? "minimize" : "maximize")); + if (minimal) + direction = TRE_TAG_MINIMIZE; + else + direction = TRE_TAG_MAXIMIZE; + } + break; + } + + case ADDTAGS_AFTER_CAT_LEFT: + { + int new_tag = tre_stack_pop_int(stack); + next_tag = tre_stack_pop_int(stack); + DPRINT(("After cat left, tag = %d, next_tag = %d\n", + tag, next_tag)); + if (new_tag >= 0) + { + DPRINT((" Setting tag to %d\n", new_tag)); + tag = new_tag; + } + break; + } + + case ADDTAGS_AFTER_CAT_RIGHT: + DPRINT(("After cat right\n")); + node = tre_stack_pop_voidptr(stack); + if (first_pass) + node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags + + ((tre_catenation_t *)node->obj)->right->num_tags; + break; + + case ADDTAGS_AFTER_UNION_LEFT: + DPRINT(("After union left\n")); + /* Lift the bottom of the `regset' array so that when processing + the right operand the items currently in the array are + invisible. The original bottom was saved at ADDTAGS_UNION and + will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */ + while (*regset >= 0) + regset++; + break; + + case ADDTAGS_AFTER_UNION_RIGHT: + { + int added_tags, tag_left, tag_right; + tre_ast_node_t *left = tre_stack_pop_voidptr(stack); + tre_ast_node_t *right = tre_stack_pop_voidptr(stack); + DPRINT(("After union right\n")); + node = tre_stack_pop_voidptr(stack); + added_tags = tre_stack_pop_int(stack); + if (first_pass) + { + node->num_tags = ((tre_union_t *)node->obj)->left->num_tags + + ((tre_union_t *)node->obj)->right->num_tags + added_tags + + ((node->num_submatches > 0) ? 2 : 0); + } + regset = tre_stack_pop_voidptr(stack); + tag_left = tre_stack_pop_int(stack); + tag_right = tre_stack_pop_int(stack); + + /* Add tags after both children, the left child gets a smaller + tag than the right child. This guarantees that we prefer + the left child over the right child. */ + /* XXX - This is not always necessary (if the children have + tags which must be seen for every match of that child). */ + /* XXX - Check if this is the only place where tre_add_tag_right + is used. If so, use tre_add_tag_left (putting the tag before + the child as opposed after the child) and throw away + tre_add_tag_right. */ + if (node->num_submatches > 0) + { + if (!first_pass) + { + status = tre_add_tag_right(mem, left, tag_left); + tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE; + status = tre_add_tag_right(mem, right, tag_right); + tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE; + } + DPRINT((" num_tags += 2\n")); + num_tags += 2; + } + direction = TRE_TAG_MAXIMIZE; + break; + } + + default: + assert(0); + break; + + } /* end switch(symbol) */ + } /* end while(tre_stack_num_objects(stack) > bottom) */ + + if (!first_pass) + tre_purge_regset(regset, tnfa, tag); + + if (!first_pass && minimal_tag >= 0) + { + int i; + DPRINT(("Minimal %d, %d\n", minimal_tag, tag)); + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + + DPRINT(("tre_add_tags: %s complete. Number of tags %d.\n", + first_pass? "First pass" : "Second pass", num_tags)); + + assert(tree->num_tags == num_tags); + tnfa->end_tag = num_tags; + tnfa->num_tags = num_tags; + tnfa->num_minimals = num_minimals; + xfree(orig_regset); + xfree(parents); + xfree(saved_states); + return status; +} + + + +/* + AST to TNFA compilation routines. +*/ + +typedef enum { + COPY_RECURSE, + COPY_SET_RESULT_PTR +} tre_copyast_symbol_t; + +/* Flags for tre_copy_ast(). */ +#define COPY_REMOVE_TAGS 1 +#define COPY_MAXIMIZE_FIRST_TAG 2 + +static reg_errcode_t +tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, + int flags, int *pos_add, tre_tag_direction_t *tag_directions, + tre_ast_node_t **copy, int *max_pos) +{ + reg_errcode_t status = REG_OK; + int bottom = tre_stack_num_objects(stack); + int num_copied = 0; + int first_tag = 1; + tre_ast_node_t **result = copy; + tre_copyast_symbol_t symbol; + + STACK_PUSH(stack, voidptr, ast); + STACK_PUSH(stack, int, COPY_RECURSE); + + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + tre_ast_node_t *node; + if (status != REG_OK) + break; + + symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack); + switch (symbol) + { + case COPY_SET_RESULT_PTR: + result = tre_stack_pop_voidptr(stack); + break; + case COPY_RECURSE: + node = tre_stack_pop_voidptr(stack); + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = node->obj; + int pos = lit->position; + int min = lit->code_min; + int max = lit->code_max; + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + /* XXX - e.g. [ab] has only one position but two + nodes, so we are creating holes in the state space + here. Not fatal, just wastes memory. */ + pos += *pos_add; + num_copied++; + } + else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS)) + { + /* Change this tag to empty. */ + min = EMPTY; + max = pos = -1; + } + else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG) + && first_tag) + { + /* Maximize the first tag. */ + tag_directions[max] = TRE_TAG_MAXIMIZE; + first_tag = 0; + } + *result = tre_ast_new_literal(mem, min, max, pos); + if (*result == NULL) + status = REG_ESPACE; + + if (pos > *max_pos) + *max_pos = pos; + break; + } + case UNION: + { + tre_union_t *uni = node->obj; + tre_union_t *tmp; + *result = tre_ast_new_union(mem, uni->left, uni->right); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + tmp = (*result)->obj; + result = &tmp->left; + STACK_PUSHX(stack, voidptr, uni->right); + STACK_PUSHX(stack, int, COPY_RECURSE); + STACK_PUSHX(stack, voidptr, &tmp->right); + STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR); + STACK_PUSHX(stack, voidptr, uni->left); + STACK_PUSHX(stack, int, COPY_RECURSE); + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + tre_catenation_t *tmp; + *result = tre_ast_new_catenation(mem, cat->left, cat->right); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + tmp = (*result)->obj; + tmp->left = NULL; + tmp->right = NULL; + result = &tmp->left; + + STACK_PUSHX(stack, voidptr, cat->right); + STACK_PUSHX(stack, int, COPY_RECURSE); + STACK_PUSHX(stack, voidptr, &tmp->right); + STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, int, COPY_RECURSE); + break; + } + case ITERATION: + { + tre_iteration_t *iter = node->obj; + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, COPY_RECURSE); + *result = tre_ast_new_iter(mem, iter->arg, iter->min, + iter->max, iter->minimal); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + iter = (*result)->obj; + result = &iter->arg; + break; + } + default: + assert(0); + break; + } + break; + } + } + *pos_add += num_copied; + return status; +} + +typedef enum { + EXPAND_RECURSE, + EXPAND_AFTER_ITER +} tre_expand_ast_symbol_t; + +/* Expands each iteration node that has a finite nonzero minimum or maximum + iteration count to a catenated sequence of copies of the node. */ +static reg_errcode_t +tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, + int *position, tre_tag_direction_t *tag_directions, + int *max_depth) +{ + reg_errcode_t status = REG_OK; + int bottom = tre_stack_num_objects(stack); + int pos_add = 0; + int pos_add_total = 0; + int max_pos = 0; + /* Current approximate matching parameters. */ + int params[TRE_PARAM_LAST]; + /* Approximate parameter nesting level. */ + int params_depth = 0; + int iter_depth = 0; + int i; + + for (i = 0; i < TRE_PARAM_LAST; i++) + params[i] = TRE_PARAM_DEFAULT; + + STACK_PUSHR(stack, voidptr, ast); + STACK_PUSHR(stack, int, EXPAND_RECURSE); + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + tre_ast_node_t *node; + tre_expand_ast_symbol_t symbol; + + if (status != REG_OK) + break; + + DPRINT(("pos_add %d\n", pos_add)); + + symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack); + node = tre_stack_pop_voidptr(stack); + switch (symbol) + { + case EXPAND_RECURSE: + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit= node->obj; + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + lit->position += pos_add; + if (lit->position > max_pos) + max_pos = lit->position; + } + break; + } + case UNION: + { + tre_union_t *uni = node->obj; + STACK_PUSHX(stack, voidptr, uni->right); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + STACK_PUSHX(stack, voidptr, uni->left); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + STACK_PUSHX(stack, voidptr, cat->right); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + break; + } + case ITERATION: + { + tre_iteration_t *iter = node->obj; + STACK_PUSHX(stack, int, pos_add); + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, EXPAND_AFTER_ITER); + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + /* If we are going to expand this node at EXPAND_AFTER_ITER + then don't increase the `pos' fields of the nodes now, it + will get done when expanding. */ + if (iter->min > 1 || iter->max > 1) + pos_add = 0; + iter_depth++; + DPRINT(("iter\n")); + break; + } + default: + assert(0); + break; + } + break; + case EXPAND_AFTER_ITER: + { + tre_iteration_t *iter = node->obj; + int pos_add_last; + pos_add = tre_stack_pop_int(stack); + pos_add_last = pos_add; + if (iter->min > 1 || iter->max > 1) + { + tre_ast_node_t *seq1 = NULL, *seq2 = NULL; + int j; + int pos_add_save = pos_add; + + /* Create a catenated sequence of copies of the node. */ + for (j = 0; j < iter->min; j++) + { + tre_ast_node_t *copy; + /* Remove tags from all but the last copy. */ + int flags = ((j + 1 < iter->min) + ? COPY_REMOVE_TAGS + : COPY_MAXIMIZE_FIRST_TAG); + DPRINT((" pos_add %d\n", pos_add)); + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, flags, + &pos_add, tag_directions, ©, + &max_pos); + if (status != REG_OK) + return status; + if (seq1 != NULL) + seq1 = tre_ast_new_catenation(mem, seq1, copy); + else + seq1 = copy; + if (seq1 == NULL) + return REG_ESPACE; + } + + if (iter->max == -1) + { + /* No upper limit. */ + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, 0, + &pos_add, NULL, &seq2, &max_pos); + if (status != REG_OK) + return status; + seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0); + if (seq2 == NULL) + return REG_ESPACE; + } + else + { + for (j = iter->min; j < iter->max; j++) + { + tre_ast_node_t *tmp, *copy; + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, 0, + &pos_add, NULL, ©, &max_pos); + if (status != REG_OK) + return status; + if (seq2 != NULL) + seq2 = tre_ast_new_catenation(mem, copy, seq2); + else + seq2 = copy; + if (seq2 == NULL) + return REG_ESPACE; + tmp = tre_ast_new_literal(mem, EMPTY, -1, -1); + if (tmp == NULL) + return REG_ESPACE; + seq2 = tre_ast_new_union(mem, tmp, seq2); + if (seq2 == NULL) + return REG_ESPACE; + } + } + + pos_add = pos_add_save; + if (seq1 == NULL) + seq1 = seq2; + else if (seq2 != NULL) + seq1 = tre_ast_new_catenation(mem, seq1, seq2); + if (seq1 == NULL) + return REG_ESPACE; + node->obj = seq1->obj; + node->type = seq1->type; + } + + iter_depth--; + pos_add_total += pos_add - pos_add_last; + if (iter_depth == 0) + pos_add = pos_add_total; + + /* If approximate parameters are specified, surround the result + with two parameter setting nodes. The one on the left sets + the specified parameters, and the one on the right restores + the old parameters. */ + if (iter->params) + { + tre_ast_node_t *tmp_l, *tmp_r, *tmp_node, *node_copy; + int *old_params; + + tmp_l = tre_ast_new_literal(mem, PARAMETER, 0, -1); + if (!tmp_l) + return REG_ESPACE; + ((tre_literal_t *)tmp_l->obj)->u.params = iter->params; + iter->params[TRE_PARAM_DEPTH] = params_depth + 1; + tmp_r = tre_ast_new_literal(mem, PARAMETER, 0, -1); + if (!tmp_r) + return REG_ESPACE; + old_params = tre_mem_alloc(mem, sizeof(*old_params) + * TRE_PARAM_LAST); + if (!old_params) + return REG_ESPACE; + for (i = 0; i < TRE_PARAM_LAST; i++) + old_params[i] = params[i]; + ((tre_literal_t *)tmp_r->obj)->u.params = old_params; + old_params[TRE_PARAM_DEPTH] = params_depth; + /* XXX - this is the only place where ast_new_node is + needed -- should be moved inside AST module. */ + node_copy = tre_ast_new_node(mem, ITERATION, + sizeof(tre_iteration_t)); + if (!node_copy) + return REG_ESPACE; + node_copy->obj = node->obj; + tmp_node = tre_ast_new_catenation(mem, tmp_l, node_copy); + if (!tmp_node) + return REG_ESPACE; + tmp_node = tre_ast_new_catenation(mem, tmp_node, tmp_r); + if (!tmp_node) + return REG_ESPACE; + /* Replace the contents of `node' with `tmp_node'. */ + memcpy(node, tmp_node, sizeof(*node)); + node->obj = tmp_node->obj; + node->type = tmp_node->type; + params_depth++; + if (params_depth > *max_depth) + *max_depth = params_depth; + } + break; + } + default: + assert(0); + break; + } + } + + *position += pos_add_total; + + /* `max_pos' should never be larger than `*position' if the above + code works, but just an extra safeguard let's make sure + `*position' is set large enough so enough memory will be + allocated for the transition table. */ + if (max_pos > *position) + *position = max_pos; + +#ifdef TRE_DEBUG + DPRINT(("Expanded AST:\n")); + tre_ast_print(ast); + DPRINT(("*position %d, max_pos %d\n", *position, max_pos)); +#endif + + return status; +} + +static tre_pos_and_tags_t * +tre_set_empty(tre_mem_t mem) +{ + tre_pos_and_tags_t *new_set; + + new_set = tre_mem_calloc(mem, sizeof(*new_set)); + if (new_set == NULL) + return NULL; + + new_set[0].position = -1; + new_set[0].code_min = -1; + new_set[0].code_max = -1; + + return new_set; +} + +static tre_pos_and_tags_t * +tre_set_one(tre_mem_t mem, int position, int code_min, int code_max, + tre_ctype_t class, tre_ctype_t *neg_classes, int backref) +{ + tre_pos_and_tags_t *new_set; + + new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2); + if (new_set == NULL) + return NULL; + + new_set[0].position = position; + new_set[0].code_min = code_min; + new_set[0].code_max = code_max; + new_set[0].class = class; + new_set[0].neg_classes = neg_classes; + new_set[0].backref = backref; + new_set[1].position = -1; + new_set[1].code_min = -1; + new_set[1].code_max = -1; + + return new_set; +} + +static tre_pos_and_tags_t * +tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2, + int *tags, int assertions, int *params) +{ + int s1, s2, i, j; + tre_pos_and_tags_t *new_set; + int *new_tags; + int num_tags; + + for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++); + for (s1 = 0; set1[s1].position >= 0; s1++); + for (s2 = 0; set2[s2].position >= 0; s2++); + new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1)); + if (!new_set ) + return NULL; + + for (s1 = 0; set1[s1].position >= 0; s1++) + { + new_set[s1].position = set1[s1].position; + new_set[s1].code_min = set1[s1].code_min; + new_set[s1].code_max = set1[s1].code_max; + new_set[s1].assertions = set1[s1].assertions | assertions; + new_set[s1].class = set1[s1].class; + new_set[s1].neg_classes = set1[s1].neg_classes; + new_set[s1].backref = set1[s1].backref; + if (set1[s1].tags == NULL && tags == NULL) + new_set[s1].tags = NULL; + else + { + for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++); + new_tags = tre_mem_alloc(mem, (sizeof(*new_tags) + * (i + num_tags + 1))); + if (new_tags == NULL) + return NULL; + for (j = 0; j < i; j++) + new_tags[j] = set1[s1].tags[j]; + for (i = 0; i < num_tags; i++) + new_tags[j + i] = tags[i]; + new_tags[j + i] = -1; + new_set[s1].tags = new_tags; + } + if (set1[s1].params) + new_set[s1].params = set1[s1].params; + if (params) + { + if (!new_set[s1].params) + new_set[s1].params = params; + else + { + new_set[s1].params = tre_mem_alloc(mem, sizeof(*params) * + TRE_PARAM_LAST); + if (!new_set[s1].params) + return NULL; + for (i = 0; i < TRE_PARAM_LAST; i++) + if (params[i] != TRE_PARAM_UNSET) + new_set[s1].params[i] = params[i]; + } + } + } + + for (s2 = 0; set2[s2].position >= 0; s2++) + { + new_set[s1 + s2].position = set2[s2].position; + new_set[s1 + s2].code_min = set2[s2].code_min; + new_set[s1 + s2].code_max = set2[s2].code_max; + /* XXX - why not | assertions here as well? */ + new_set[s1 + s2].assertions = set2[s2].assertions; + new_set[s1 + s2].class = set2[s2].class; + new_set[s1 + s2].neg_classes = set2[s2].neg_classes; + new_set[s1 + s2].backref = set2[s2].backref; + if (set2[s2].tags == NULL) + new_set[s1 + s2].tags = NULL; + else + { + for (i = 0; set2[s2].tags[i] >= 0; i++); + new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1)); + if (new_tags == NULL) + return NULL; + for (j = 0; j < i; j++) + new_tags[j] = set2[s2].tags[j]; + new_tags[j] = -1; + new_set[s1 + s2].tags = new_tags; + } + if (set2[s2].params) + new_set[s1 + s2].params = set2[s2].params; + if (params) + { + if (!new_set[s1 + s2].params) + new_set[s1 + s2].params = params; + else + { + new_set[s1 + s2].params = tre_mem_alloc(mem, sizeof(*params) * + TRE_PARAM_LAST); + if (!new_set[s1 + s2].params) + return NULL; + for (i = 0; i < TRE_PARAM_LAST; i++) + if (params[i] != TRE_PARAM_UNSET) + new_set[s1 + s2].params[i] = params[i]; + } + } + } + new_set[s1 + s2].position = -1; + return new_set; +} + +/* Finds the empty path through `node' which is the one that should be + taken according to POSIX.2 rules, and adds the tags on that path to + `tags'. `tags' may be NULL. If `num_tags_seen' is not NULL, it is + set to the number of tags seen on the path. */ +static reg_errcode_t +tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags, + int *assertions, int *params, int *num_tags_seen, + int *params_seen) +{ + tre_literal_t *lit; + tre_union_t *uni; + tre_catenation_t *cat; + tre_iteration_t *iter; + int i; + int bottom = tre_stack_num_objects(stack); + reg_errcode_t status = REG_OK; + if (num_tags_seen) + *num_tags_seen = 0; + if (params_seen) + *params_seen = 0; + + status = tre_stack_push_voidptr(stack, node); + + /* Walk through the tree recursively. */ + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + node = tre_stack_pop_voidptr(stack); + + switch (node->type) + { + case LITERAL: + lit = (tre_literal_t *)node->obj; + switch (lit->code_min) + { + case TAG: + if (lit->code_max >= 0) + { + if (tags != NULL) + { + /* Add the tag to `tags'. */ + for (i = 0; tags[i] >= 0; i++) + if (tags[i] == lit->code_max) + break; + if (tags[i] < 0) + { + tags[i] = lit->code_max; + tags[i + 1] = -1; + } + } + if (num_tags_seen) + (*num_tags_seen)++; + } + break; + case ASSERTION: + assert(lit->code_max >= 1 + || lit->code_max <= ASSERT_LAST); + if (assertions != NULL) + *assertions |= lit->code_max; + break; + case PARAMETER: + if (params != NULL) + for (i = 0; i < TRE_PARAM_LAST; i++) + params[i] = lit->u.params[i]; + if (params_seen != NULL) + *params_seen = 1; + break; + case EMPTY: + break; + default: + assert(0); + break; + } + break; + + case UNION: + /* Subexpressions starting earlier take priority over ones + starting later, so we prefer the left subexpression over the + right subexpression. */ + uni = (tre_union_t *)node->obj; + if (uni->left->nullable) + STACK_PUSHX(stack, voidptr, uni->left) + else if (uni->right->nullable) + STACK_PUSHX(stack, voidptr, uni->right) + else + assert(0); + break; + + case CATENATION: + /* The path must go through both children. */ + cat = (tre_catenation_t *)node->obj; + assert(cat->left->nullable); + assert(cat->right->nullable); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, voidptr, cat->right); + break; + + case ITERATION: + /* A match with an empty string is preferred over no match at + all, so we go through the argument if possible. */ + iter = (tre_iteration_t *)node->obj; + if (iter->arg->nullable) + STACK_PUSHX(stack, voidptr, iter->arg); + break; + + default: + assert(0); + break; + } + } + + return status; +} + + +typedef enum { + NFL_RECURSE, + NFL_POST_UNION, + NFL_POST_CATENATION, + NFL_POST_ITERATION +} tre_nfl_stack_symbol_t; + + +/* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for + the nodes of the AST `tree'. */ +static reg_errcode_t +tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree) +{ + int bottom = tre_stack_num_objects(stack); + + STACK_PUSHR(stack, voidptr, tree); + STACK_PUSHR(stack, int, NFL_RECURSE); + + while (tre_stack_num_objects(stack) > bottom) + { + tre_nfl_stack_symbol_t symbol; + tre_ast_node_t *node; + + symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack); + node = tre_stack_pop_voidptr(stack); + switch (symbol) + { + case NFL_RECURSE: + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = (tre_literal_t *)node->obj; + if (IS_BACKREF(lit)) + { + /* Back references: nullable = false, firstpos = {i}, + lastpos = {i}. */ + node->nullable = 0; + node->firstpos = tre_set_one(mem, lit->position, 0, + TRE_CHAR_MAX, 0, NULL, -1); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_one(mem, lit->position, 0, + TRE_CHAR_MAX, 0, NULL, + (int)lit->code_max); + if (!node->lastpos) + return REG_ESPACE; + } + else if (lit->code_min < 0) + { + /* Tags, empty strings, params, and zero width assertions: + nullable = true, firstpos = {}, and lastpos = {}. */ + node->nullable = 1; + node->firstpos = tre_set_empty(mem); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_empty(mem); + if (!node->lastpos) + return REG_ESPACE; + } + else + { + /* Literal at position i: nullable = false, firstpos = {i}, + lastpos = {i}. */ + node->nullable = 0; + node->firstpos = + tre_set_one(mem, lit->position, (int)lit->code_min, + (int)lit->code_max, 0, NULL, -1); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_one(mem, lit->position, + (int)lit->code_min, + (int)lit->code_max, + lit->u.class, lit->neg_classes, + -1); + if (!node->lastpos) + return REG_ESPACE; + } + break; + } + + case UNION: + /* Compute the attributes for the two subtrees, and after that + for this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_UNION); + STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right); + STACK_PUSHR(stack, int, NFL_RECURSE); + STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + + case CATENATION: + /* Compute the attributes for the two subtrees, and after that + for this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_CATENATION); + STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right); + STACK_PUSHR(stack, int, NFL_RECURSE); + STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + + case ITERATION: + /* Compute the attributes for the subtree, and after that for + this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_ITERATION); + STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + } + break; /* end case: NFL_RECURSE */ + + case NFL_POST_UNION: + { + tre_union_t *uni = (tre_union_t *)node->obj; + node->nullable = uni->left->nullable || uni->right->nullable; + node->firstpos = tre_set_union(mem, uni->left->firstpos, + uni->right->firstpos, NULL, 0, NULL); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_union(mem, uni->left->lastpos, + uni->right->lastpos, NULL, 0, NULL); + if (!node->lastpos) + return REG_ESPACE; + break; + } + + case NFL_POST_ITERATION: + { + tre_iteration_t *iter = (tre_iteration_t *)node->obj; + + if (iter->min == 0 || iter->arg->nullable) + node->nullable = 1; + else + node->nullable = 0; + node->firstpos = iter->arg->firstpos; + node->lastpos = iter->arg->lastpos; + break; + } + + case NFL_POST_CATENATION: + { + int num_tags, *tags, assertions, params_seen; + int *params; + reg_errcode_t status; + tre_catenation_t *cat = node->obj; + node->nullable = cat->left->nullable && cat->right->nullable; + + /* Compute firstpos. */ + if (cat->left->nullable) + { + /* The left side matches the empty string. Make a first pass + with tre_match_empty() to get the number of tags and + parameters. */ + status = tre_match_empty(stack, cat->left, + NULL, NULL, NULL, &num_tags, + ¶ms_seen); + if (status != REG_OK) + return status; + /* Allocate arrays for the tags and parameters. */ + tags = xmalloc(sizeof(*tags) * (num_tags + 1)); + if (!tags) + return REG_ESPACE; + tags[0] = -1; + assertions = 0; + params = NULL; + if (params_seen) + { + params = tre_mem_alloc(mem, sizeof(*params) + * TRE_PARAM_LAST); + if (!params) + { + xfree(tags); + return REG_ESPACE; + } + } + /* Second pass with tre_mach_empty() to get the list of + tags and parameters. */ + status = tre_match_empty(stack, cat->left, tags, + &assertions, params, NULL, NULL); + if (status != REG_OK) + { + xfree(tags); + return status; + } + node->firstpos = + tre_set_union(mem, cat->right->firstpos, cat->left->firstpos, + tags, assertions, params); + xfree(tags); + if (!node->firstpos) + return REG_ESPACE; + } + else + { + node->firstpos = cat->left->firstpos; + } + + /* Compute lastpos. */ + if (cat->right->nullable) + { + /* The right side matches the empty string. Make a first pass + with tre_match_empty() to get the number of tags and + parameters. */ + status = tre_match_empty(stack, cat->right, + NULL, NULL, NULL, &num_tags, + ¶ms_seen); + if (status != REG_OK) + return status; + /* Allocate arrays for the tags and parameters. */ + tags = xmalloc(sizeof(int) * (num_tags + 1)); + if (!tags) + return REG_ESPACE; + tags[0] = -1; + assertions = 0; + params = NULL; + if (params_seen) + { + params = tre_mem_alloc(mem, sizeof(*params) + * TRE_PARAM_LAST); + if (!params) + { + xfree(tags); + return REG_ESPACE; + } + } + /* Second pass with tre_mach_empty() to get the list of + tags and parameters. */ + status = tre_match_empty(stack, cat->right, tags, + &assertions, params, NULL, NULL); + if (status != REG_OK) + { + xfree(tags); + return status; + } + node->lastpos = + tre_set_union(mem, cat->left->lastpos, cat->right->lastpos, + tags, assertions, params); + xfree(tags); + if (!node->lastpos) + return REG_ESPACE; + } + else + { + node->lastpos = cat->right->lastpos; + } + break; + } + + default: + assert(0); + break; + } + } + + return REG_OK; +} + + +/* Adds a transition from each position in `p1' to each position in `p2'. */ +static reg_errcode_t +tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2, + tre_tnfa_transition_t *transitions, + int *counts, int *offs) +{ + tre_pos_and_tags_t *orig_p2 = p2; + tre_tnfa_transition_t *trans; + int i, j, k, l, dup, prev_p2_pos; + + if (transitions != NULL) + while (p1->position >= 0) + { + p2 = orig_p2; + prev_p2_pos = -1; + while (p2->position >= 0) + { + /* Optimization: if this position was already handled, skip it. */ + if (p2->position == prev_p2_pos) + { + p2++; + continue; + } + prev_p2_pos = p2->position; + /* Set `trans' to point to the next unused transition from + position `p1->position'. */ + trans = transitions + offs[p1->position]; + while (trans->state != NULL) + { +#if 0 + /* If we find a previous transition from `p1->position' to + `p2->position', it is overwritten. This can happen only + if there are nested loops in the regexp, like in "((a)*)*". + In POSIX.2 repetition using the outer loop is always + preferred over using the inner loop. Therefore the + transition for the inner loop is useless and can be thrown + away. */ + /* XXX - The same position is used for all nodes in a bracket + expression, so this optimization cannot be used (it will + break bracket expressions) unless I figure out a way to + detect it here. */ + if (trans->state_id == p2->position) + { + DPRINT(("*")); + break; + } +#endif + trans++; + } + + if (trans->state == NULL) + (trans + 1)->state = NULL; + /* Use the character ranges, assertions, etc. from `p1' for + the transition from `p1' to `p2'. */ + trans->code_min = p1->code_min; + trans->code_max = p1->code_max; + trans->state = transitions + offs[p2->position]; + trans->state_id = p2->position; + trans->assertions = p1->assertions | p2->assertions + | (p1->class ? ASSERT_CHAR_CLASS : 0) + | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0); + if (p1->backref >= 0) + { + assert((trans->assertions & ASSERT_CHAR_CLASS) == 0); + assert(p2->backref < 0); + trans->u.backref = p1->backref; + trans->assertions |= ASSERT_BACKREF; + } + else + trans->u.class = p1->class; + if (p1->neg_classes != NULL) + { + for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++); + trans->neg_classes = + xmalloc(sizeof(*trans->neg_classes) * (i + 1)); + if (trans->neg_classes == NULL) + return REG_ESPACE; + for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++) + trans->neg_classes[i] = p1->neg_classes[i]; + trans->neg_classes[i] = (tre_ctype_t)0; + } + else + trans->neg_classes = NULL; + + /* Find out how many tags this transition has. */ + i = 0; + if (p1->tags != NULL) + while(p1->tags[i] >= 0) + i++; + j = 0; + if (p2->tags != NULL) + while(p2->tags[j] >= 0) + j++; + + /* If we are overwriting a transition, free the old tag array. */ + if (trans->tags != NULL) + xfree(trans->tags); + trans->tags = NULL; + + /* If there were any tags, allocate an array and fill it. */ + if (i + j > 0) + { + trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1)); + if (!trans->tags) + return REG_ESPACE; + i = 0; + if (p1->tags != NULL) + while(p1->tags[i] >= 0) + { + trans->tags[i] = p1->tags[i]; + i++; + } + l = i; + j = 0; + if (p2->tags != NULL) + while (p2->tags[j] >= 0) + { + /* Don't add duplicates. */ + dup = 0; + for (k = 0; k < i; k++) + if (trans->tags[k] == p2->tags[j]) + { + dup = 1; + break; + } + if (!dup) + trans->tags[l++] = p2->tags[j]; + j++; + } + trans->tags[l] = -1; + } + + /* Set the parameter array. If both `p2' and `p1' have same + parameters, the values in `p2' override those in `p1'. */ + if (p1->params || p2->params) + { + if (!trans->params) + trans->params = xmalloc(sizeof(*trans->params) + * TRE_PARAM_LAST); + if (!trans->params) + return REG_ESPACE; + for (i = 0; i < TRE_PARAM_LAST; i++) + { + trans->params[i] = TRE_PARAM_UNSET; + if (p1->params && p1->params[i] != TRE_PARAM_UNSET) + trans->params[i] = p1->params[i]; + if (p2->params && p2->params[i] != TRE_PARAM_UNSET) + trans->params[i] = p2->params[i]; + } + } + else + { + if (trans->params) + xfree(trans->params); + trans->params = NULL; + } + + +#ifdef TRE_DEBUG + { + int *tags; + + DPRINT((" %2d -> %2d on %3d", p1->position, p2->position, + p1->code_min)); + if (p1->code_max != p1->code_min) + DPRINT(("-%3d", p1->code_max)); + tags = trans->tags; + if (tags) + { + DPRINT((", tags [")); + while (*tags >= 0) + { + DPRINT(("%d", *tags)); + tags++; + if (*tags >= 0) + DPRINT((",")); + } + DPRINT(("]")); + } + if (trans->assertions) + DPRINT((", assert %d", trans->assertions)); + if (trans->assertions & ASSERT_BACKREF) + DPRINT((", backref %d", trans->u.backref)); + else if (trans->u.class) + DPRINT((", class %ld", (long)trans->u.class)); + if (trans->neg_classes) + DPRINT((", neg_classes %p", trans->neg_classes)); + if (trans->params) + { + DPRINT((", ")); + tre_print_params(trans->params); + } + DPRINT(("\n")); + } +#endif /* TRE_DEBUG */ + p2++; + } + p1++; + } + else + /* Compute a maximum limit for the number of transitions leaving + from each state. */ + while (p1->position >= 0) + { + p2 = orig_p2; + while (p2->position >= 0) + { + counts[p1->position]++; + p2++; + } + p1++; + } + return REG_OK; +} + +/* Converts the syntax tree to a TNFA. All the transitions in the TNFA are + labelled with one character range (there are no transitions on empty + strings). The TNFA takes O(n^2) space in the worst case, `n' is size of + the regexp. */ +static reg_errcode_t +tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, + int *counts, int *offs) +{ + tre_union_t *uni; + tre_catenation_t *cat; + tre_iteration_t *iter; + reg_errcode_t errcode = REG_OK; + + /* XXX - recurse using a stack!. */ + switch (node->type) + { + case LITERAL: + break; + case UNION: + uni = (tre_union_t *)node->obj; + errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs); + break; + + case CATENATION: + cat = (tre_catenation_t *)node->obj; + /* Add a transition from each position in cat->left->lastpos + to each position in cat->right->firstpos. */ + errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos, + transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs); + break; + + case ITERATION: + iter = (tre_iteration_t *)node->obj; + assert(iter->max == -1 || iter->max == 1); + + if (iter->max == -1) + { + assert(iter->min == 0 || iter->min == 1); + /* Add a transition from each last position in the iterated + expression to each first position. */ + errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos, + transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + } + errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs); + break; + } + return errcode; +} + + +#define ERROR_EXIT(err) \ + do \ + { \ + errcode = err; \ + if (/*CONSTCOND*/1) \ + goto error_exit; \ + } \ + while (/*CONSTCOND*/0) + + +int +tre_compile(regex_t *preg, const tre_char_t *regex, size_t n, int cflags) +{ + tre_stack_t *stack; + tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r; + tre_pos_and_tags_t *p; + int *counts = NULL, *offs = NULL; + int i, add = 0; + tre_tnfa_transition_t *transitions, *initial; + tre_tnfa_t *tnfa = NULL; + tre_submatch_data_t *submatch_data; + tre_tag_direction_t *tag_directions = NULL; + reg_errcode_t errcode; + tre_mem_t mem; + + /* Parse context. */ + tre_parse_ctx_t parse_ctx; + + /* Allocate a stack used throughout the compilation process for various + purposes. */ + stack = tre_stack_new(512, 10240, 128); + if (!stack) + return REG_ESPACE; + /* Allocate a fast memory allocator. */ + mem = tre_mem_new(); + if (!mem) + { + tre_stack_destroy(stack); + return REG_ESPACE; + } + + /* Parse the regexp. */ + memset(&parse_ctx, 0, sizeof(parse_ctx)); + parse_ctx.mem = mem; + parse_ctx.stack = stack; + parse_ctx.re = regex; + parse_ctx.len = n; + parse_ctx.cflags = cflags; + parse_ctx.max_backref = -1; + DPRINT(("tre_compile: parsing '%.*" STRF "'\n", (int)n, regex)); + errcode = tre_parse(&parse_ctx); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + preg->re_nsub = parse_ctx.submatch_id - 1; + tree = parse_ctx.result; + + /* Back references and approximate matching cannot currently be used + in the same regexp. */ + if (parse_ctx.max_backref >= 0 && parse_ctx.have_approx) + ERROR_EXIT(REG_BADPAT); + +#ifdef TRE_DEBUG + tre_ast_print(tree); +#endif /* TRE_DEBUG */ + + /* Referring to nonexistent subexpressions is illegal. */ + if (parse_ctx.max_backref > (int)preg->re_nsub) + ERROR_EXIT(REG_ESUBREG); + + /* Allocate the TNFA struct. */ + tnfa = xcalloc(1, sizeof(tre_tnfa_t)); + if (tnfa == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->have_backrefs = parse_ctx.max_backref >= 0; + tnfa->have_approx = parse_ctx.have_approx; + tnfa->num_submatches = parse_ctx.submatch_id; + + /* Set up tags for submatch addressing. If REG_NOSUB is set and the + regexp does not have back references, this can be skipped. */ + if (tnfa->have_backrefs || !(cflags & REG_NOSUB)) + { + DPRINT(("tre_compile: setting up tags\n")); + + /* Figure out how many tags we will need. */ + errcode = tre_add_tags(NULL, stack, tree, tnfa); + if (errcode != REG_OK) + ERROR_EXIT(errcode); +#ifdef TRE_DEBUG + tre_ast_print(tree); +#endif /* TRE_DEBUG */ + + if (tnfa->num_tags > 0) + { + tag_directions = xmalloc(sizeof(*tag_directions) + * (tnfa->num_tags + 1)); + if (tag_directions == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->tag_directions = tag_directions; + memset(tag_directions, -1, + sizeof(*tag_directions) * (tnfa->num_tags + 1)); + } + tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1, + sizeof(tnfa->minimal_tags)); + if (tnfa->minimal_tags == NULL) + ERROR_EXIT(REG_ESPACE); + + submatch_data = xcalloc((unsigned)parse_ctx.submatch_id, + sizeof(*submatch_data)); + if (submatch_data == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->submatch_data = submatch_data; + + errcode = tre_add_tags(mem, stack, tree, tnfa); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + +#ifdef TRE_DEBUG + for (i = 0; i < parse_ctx.submatch_id; i++) + DPRINT(("pmatch[%d] = {t%d, t%d}\n", + i, submatch_data[i].so_tag, submatch_data[i].eo_tag)); + for (i = 0; i < tnfa->num_tags; i++) + DPRINT(("t%d is %s\n", i, + tag_directions[i] == TRE_TAG_MINIMIZE ? + "minimized" : "maximized")); +#endif /* TRE_DEBUG */ + } + + /* Expand iteration nodes. */ + errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position, + tag_directions, &tnfa->params_depth); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + /* Add a dummy node for the final state. + XXX - For certain patterns this dummy node can be optimized away, + for example "a*" or "ab*". Figure out a simple way to detect + this possibility. */ + tmp_ast_l = tree; + tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++); + if (tmp_ast_r == NULL) + ERROR_EXIT(REG_ESPACE); + + tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r); + if (tree == NULL) + ERROR_EXIT(REG_ESPACE); + +#ifdef TRE_DEBUG + tre_ast_print(tree); + DPRINT(("Number of states: %d\n", parse_ctx.position)); +#endif /* TRE_DEBUG */ + + errcode = tre_compute_nfl(mem, stack, tree); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + counts = xmalloc(sizeof(int) * parse_ctx.position); + if (counts == NULL) + ERROR_EXIT(REG_ESPACE); + + offs = xmalloc(sizeof(int) * parse_ctx.position); + if (offs == NULL) + ERROR_EXIT(REG_ESPACE); + + for (i = 0; i < parse_ctx.position; i++) + counts[i] = 0; + tre_ast_to_tnfa(tree, NULL, counts, NULL); + + add = 0; + for (i = 0; i < parse_ctx.position; i++) + { + offs[i] = add; + add += counts[i] + 1; + counts[i] = 0; + } + transitions = xcalloc((unsigned)add + 1, sizeof(*transitions)); + if (transitions == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->transitions = transitions; + tnfa->num_transitions = add; + + DPRINT(("Converting to TNFA:\n")); + errcode = tre_ast_to_tnfa(tree, transitions, counts, offs); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + /* If in eight bit mode, compute a table of characters that can be the + first character of a match. */ + tnfa->first_char = -1; + if (TRE_MB_CUR_MAX == 1 && !tmp_ast_l->nullable) + { + int count = 0; + tre_cint_t k; + DPRINT(("Characters that can start a match:")); + tnfa->firstpos_chars = xcalloc(256, sizeof(char)); + if (tnfa->firstpos_chars == NULL) + ERROR_EXIT(REG_ESPACE); + for (p = tree->firstpos; p->position >= 0; p++) + { + tre_tnfa_transition_t *j = transitions + offs[p->position]; + while (j->state != NULL) + { + for (k = j->code_min; k <= j->code_max && k < 256; k++) + { + DPRINT((" %d", k)); + tnfa->firstpos_chars[k] = 1; + count++; + } + j++; + } + } + DPRINT(("\n")); +#define TRE_OPTIMIZE_FIRST_CHAR 1 +#if TRE_OPTIMIZE_FIRST_CHAR + if (count == 1) + { + for (k = 0; k < 256; k++) + if (tnfa->firstpos_chars[k]) + { + DPRINT(("first char must be %d\n", k)); + tnfa->first_char = k; + xfree(tnfa->firstpos_chars); + tnfa->firstpos_chars = NULL; + break; + } + } +#endif + + } + else + tnfa->firstpos_chars = NULL; + + + p = tree->firstpos; + i = 0; + while (p->position >= 0) + { + i++; + +#ifdef TRE_DEBUG + { + int *tags; + DPRINT(("initial: %d", p->position)); + tags = p->tags; + if (tags != NULL) + { + if (*tags >= 0) + DPRINT(("/")); + while (*tags >= 0) + { + DPRINT(("%d", *tags)); + tags++; + if (*tags >= 0) + DPRINT((",")); + } + } + DPRINT((", assert %d", p->assertions)); + if (p->params) + { + DPRINT((", ")); + tre_print_params(p->params); + } + DPRINT(("\n")); + } +#endif /* TRE_DEBUG */ + + p++; + } + + initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t)); + if (initial == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->initial = initial; + + i = 0; + for (p = tree->firstpos; p->position >= 0; p++) + { + initial[i].state = transitions + offs[p->position]; + initial[i].state_id = p->position; + initial[i].tags = NULL; + /* Copy the arrays p->tags, and p->params, they are allocated + from a tre_mem object. */ + if (p->tags) + { + int j; + for (j = 0; p->tags[j] >= 0; j++); + initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1)); + if (!initial[i].tags) + ERROR_EXIT(REG_ESPACE); + memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1)); + } + initial[i].params = NULL; + if (p->params) + { + initial[i].params = xmalloc(sizeof(*p->params) * TRE_PARAM_LAST); + if (!initial[i].params) + ERROR_EXIT(REG_ESPACE); + memcpy(initial[i].params, p->params, + sizeof(*p->params) * TRE_PARAM_LAST); + } + initial[i].assertions = p->assertions; + i++; + } + initial[i].state = NULL; + + tnfa->num_transitions = add; + tnfa->final = transitions + offs[tree->lastpos[0].position]; + tnfa->num_states = parse_ctx.position; + tnfa->cflags = cflags; + + DPRINT(("final state %p\n", (void *)tnfa->final)); + + tre_mem_destroy(mem); + tre_stack_destroy(stack); + xfree(counts); + xfree(offs); + + preg->TRE_REGEX_T_FIELD = (void *)tnfa; + return REG_OK; + + error_exit: + /* Free everything that was allocated and return the error code. */ + tre_mem_destroy(mem); + if (stack != NULL) + tre_stack_destroy(stack); + if (counts != NULL) + xfree(counts); + if (offs != NULL) + xfree(offs); + preg->TRE_REGEX_T_FIELD = (void *)tnfa; + tre_free(preg); + return errcode; +} + + + + +void +tre_free(regex_t *preg) +{ + tre_tnfa_t *tnfa; + unsigned int i; + tre_tnfa_transition_t *trans; + + tnfa = (void *)preg->TRE_REGEX_T_FIELD; + if (!tnfa) + return; + + for (i = 0; i < tnfa->num_transitions; i++) + if (tnfa->transitions[i].state) + { + if (tnfa->transitions[i].tags) + xfree(tnfa->transitions[i].tags); + if (tnfa->transitions[i].neg_classes) + xfree(tnfa->transitions[i].neg_classes); + if (tnfa->transitions[i].params) + xfree(tnfa->transitions[i].params); + } + if (tnfa->transitions) + xfree(tnfa->transitions); + + if (tnfa->initial) + { + for (trans = tnfa->initial; trans->state; trans++) + { + if (trans->tags) + xfree(trans->tags); + if (trans->params) + xfree(trans->params); + } + xfree(tnfa->initial); + } + + if (tnfa->submatch_data) + { + for (i = 0; i < tnfa->num_submatches; i++) + if (tnfa->submatch_data[i].parents) + xfree(tnfa->submatch_data[i].parents); + xfree(tnfa->submatch_data); + } + + if (tnfa->tag_directions) + xfree(tnfa->tag_directions); + if (tnfa->firstpos_chars) + xfree(tnfa->firstpos_chars); + if (tnfa->minimal_tags) + xfree(tnfa->minimal_tags); + xfree(tnfa); +} + +char * +tre_version(void) +{ + static char str[256]; + char *version; + + if (str[0] == 0) + { + (void) tre_config(TRE_CONFIG_VERSION, &version); + (void) snprintf(str, sizeof(str), "TRE %s (BSD)", version); + } + return str; +} + +int +tre_config(int query, void *result) +{ + int *int_result = result; + const char **string_result = result; + + switch (query) + { + case TRE_CONFIG_APPROX: +#ifdef TRE_APPROX + *int_result = 1; +#else /* !TRE_APPROX */ + *int_result = 0; +#endif /* !TRE_APPROX */ + return REG_OK; + + case TRE_CONFIG_WCHAR: +#ifdef TRE_WCHAR + *int_result = 1; +#else /* !TRE_WCHAR */ + *int_result = 0; +#endif /* !TRE_WCHAR */ + return REG_OK; + + case TRE_CONFIG_MULTIBYTE: +#ifdef TRE_MULTIBYTE + *int_result = 1; +#else /* !TRE_MULTIBYTE */ + *int_result = 0; +#endif /* !TRE_MULTIBYTE */ + return REG_OK; + + case TRE_CONFIG_SYSTEM_ABI: +#ifdef TRE_CONFIG_SYSTEM_ABI + *int_result = 1; +#else /* !TRE_CONFIG_SYSTEM_ABI */ + *int_result = 0; +#endif /* !TRE_CONFIG_SYSTEM_ABI */ + return REG_OK; + + case TRE_CONFIG_VERSION: + *string_result = TRE_VERSION; + return REG_OK; + } + + return REG_NOMATCH; +} + + +/* EOF */ +/* + tre-match-approx.c - TRE approximate regex matching engine + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +/* AIX requires this to be the first thing in the file. */ +#ifdef TRE_USE_ALLOCA +#ifndef __GNUC__ +# if HAVE_ALLOCA_H +# include <alloca.h> +# else +# ifdef _AIX + #pragma alloca +# else +# ifndef alloca /* predefined by HP cc +Olibcalls */ +char *alloca (); +# endif +# endif +# endif +#endif +#endif /* TRE_USE_ALLOCA */ + +#define __USE_STRING_INLINES +#undef __NO_INLINE__ + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* HAVE_WCTYPE_H */ +#ifndef TRE_WCHAR +#include <ctype.h> +#endif /* !TRE_WCHAR */ +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif /* HAVE_MALLOC_H */ + +/* + tre-match-utils.h - TRE matcher helper definitions + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#define str_source ((const tre_str_source*)string) + +#ifdef TRE_WCHAR + +#ifdef TRE_MULTIBYTE + +/* Wide character and multibyte support. */ + +#define GET_NEXT_WCHAR() \ + do { \ + prev_c = next_c; \ + if (type == STR_BYTE) \ + { \ + pos++; \ + if (len >= 0 && pos >= len) \ + next_c = '\0'; \ + else \ + next_c = (unsigned char)(*str_byte++); \ + } \ + else if (type == STR_WIDE) \ + { \ + pos++; \ + if (len >= 0 && pos >= len) \ + next_c = L'\0'; \ + else \ + next_c = *str_wide++; \ + } \ + else if (type == STR_MBS) \ + { \ + pos += pos_add_next; \ + if (str_byte == NULL) \ + next_c = L'\0'; \ + else \ + { \ + size_t w; \ + int max; \ + if (len >= 0) \ + max = len - pos; \ + else \ + max = 32; \ + if (max <= 0) \ + { \ + next_c = L'\0'; \ + pos_add_next = 1; \ + } \ + else \ + { \ + w = tre_mbrtowc(&next_c, str_byte, (size_t)max, &mbstate); \ + if (w == (size_t)-1 || w == (size_t)-2) \ + return REG_NOMATCH; \ + if (w == 0 && len >= 0) \ + { \ + pos_add_next = 1; \ + next_c = 0; \ + str_byte++; \ + } \ + else \ + { \ + pos_add_next = w; \ + str_byte += w; \ + } \ + } \ + } \ + } \ + else if (type == STR_USER) \ + { \ + pos += pos_add_next; \ + str_user_end = str_source->get_next_char(&next_c, &pos_add_next, \ + str_source->context); \ + } \ + } while(/*CONSTCOND*/0) + +#else /* !TRE_MULTIBYTE */ + +/* Wide character support, no multibyte support. */ + +#define GET_NEXT_WCHAR() \ + do { \ + prev_c = next_c; \ + if (type == STR_BYTE) \ + { \ + pos++; \ + if (len >= 0 && pos >= len) \ + next_c = '\0'; \ + else \ + next_c = (unsigned char)(*str_byte++); \ + } \ + else if (type == STR_WIDE) \ + { \ + pos++; \ + if (len >= 0 && pos >= len) \ + next_c = L'\0'; \ + else \ + next_c = *str_wide++; \ + } \ + else if (type == STR_USER) \ + { \ + pos += pos_add_next; \ + str_user_end = str_source->get_next_char(&next_c, &pos_add_next, \ + str_source->context); \ + } \ + } while(/*CONSTCOND*/0) + +#endif /* !TRE_MULTIBYTE */ + +#else /* !TRE_WCHAR */ + +/* No wide character or multibyte support. */ + +#define GET_NEXT_WCHAR() \ + do { \ + prev_c = next_c; \ + if (type == STR_BYTE) \ + { \ + pos++; \ + if (len >= 0 && pos >= len) \ + next_c = '\0'; \ + else \ + next_c = (unsigned char)(*str_byte++); \ + } \ + else if (type == STR_USER) \ + { \ + pos += pos_add_next; \ + str_user_end = str_source->get_next_char(&next_c, &pos_add_next, \ + str_source->context); \ + } \ + } while(/*CONSTCOND*/0) + +#endif /* !TRE_WCHAR */ + + + +#define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c)) + +#define CHECK_ASSERTIONS(assertions) \ + (((assertions & ASSERT_AT_BOL) \ + && (pos > 0 || reg_notbol) \ + && (prev_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_EOL) \ + && (next_c != L'\0' || reg_noteol) \ + && (next_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_BOW) \ + && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_EOW) \ + && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB) \ + && (pos != 0 && next_c != L'\0' \ + && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB_NEG) \ + && (pos == 0 || next_c == L'\0' \ + || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c)))) + +#define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \ + (((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && !(tnfa->cflags & REG_ICASE) \ + && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && (tnfa->cflags & REG_ICASE) \ + && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \ + && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \ + && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\ + tnfa->cflags & REG_ICASE))) + + + + +/* Returns 1 if `t1' wins `t2', 0 otherwise. */ +inline static int +tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions, + int *t1, int *t2) +{ + int i; + for (i = 0; i < num_tags; i++) + { + if (tag_directions[i] == TRE_TAG_MINIMIZE) + { + if (t1[i] < t2[i]) + return 1; + if (t1[i] > t2[i]) + return 0; + } + else + { + if (t1[i] > t2[i]) + return 1; + if (t1[i] < t2[i]) + return 0; + } + } + /* assert(0);*/ + return 0; +} + +inline static int +tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase) +{ + DPRINT(("neg_char_classes_test: %p, %d, %d\n", classes, wc, icase)); + while (*classes != (tre_ctype_t)0) + if ((!icase && tre_isctype(wc, *classes)) + || (icase && (tre_isctype(tre_toupper(wc), *classes) + || tre_isctype(tre_tolower(wc), *classes)))) + return 1; /* Match. */ + else + classes++; + return 0; /* No match. */ +} + +#define TRE_M_COST 0 +#define TRE_M_NUM_INS 1 +#define TRE_M_NUM_DEL 2 +#define TRE_M_NUM_SUBST 3 +#define TRE_M_NUM_ERR 4 +#define TRE_M_LAST 5 + +#define TRE_M_MAX_DEPTH 3 + +typedef struct { + /* State in the TNFA transition table. */ + tre_tnfa_transition_t *state; + /* Position in input string. */ + int pos; + /* Tag values. */ + int *tags; + /* Matching parameters. */ + regaparams_t params; + /* Nesting depth of parameters. This is used as an index in + the `costs' array. */ + int depth; + /* Costs and counter values for different parameter nesting depths. */ + int costs[TRE_M_MAX_DEPTH + 1][TRE_M_LAST]; +} tre_tnfa_approx_reach_t; + + +#ifdef TRE_DEBUG +/* Prints the `reach' array in a readable fashion with DPRINT. */ +static void +tre_print_reach(const tre_tnfa_t *tnfa, tre_tnfa_approx_reach_t *reach, + int pos, int num_tags) +{ + int id; + + /* Print each state on one line. */ + DPRINT((" reach:\n")); + for (id = 0; id < tnfa->num_states; id++) + { + int i, j; + if (reach[id].pos < pos) + continue; /* Not reached. */ + DPRINT((" %03d, costs ", id)); + for (i = 0; i <= reach[id].depth; i++) + { + DPRINT(("[")); + for (j = 0; j < TRE_M_LAST; j++) + { + DPRINT(("%2d", reach[id].costs[i][j])); + if (j + 1 < TRE_M_LAST) + DPRINT((",")); + } + DPRINT(("]")); + if (i + 1 <= reach[id].depth) + DPRINT((", ")); + } + DPRINT(("\n tags ")); + for (i = 0; i < num_tags; i++) + { + DPRINT(("%02d", reach[id].tags[i])); + if (i + 1 < num_tags) + DPRINT((",")); + } + DPRINT(("\n")); + } + DPRINT(("\n")); +} +#endif /* TRE_DEBUG */ + + +/* Sets the matching parameters in `reach' to the ones defined in the `pa' + array. If `pa' specifies default values, they are taken from + `default_params'. */ +inline static void +tre_set_params(tre_tnfa_approx_reach_t *reach, + int *pa, regaparams_t default_params) +{ + int value; + + /* If depth is increased reset costs and counters to zero for the + new levels. */ + value = pa[TRE_PARAM_DEPTH]; + assert(value <= TRE_M_MAX_DEPTH); + if (value > reach->depth) + { + int i, j; + for (i = reach->depth + 1; i <= value; i++) + for (j = 0; j < TRE_M_LAST; j++) + reach->costs[i][j] = 0; + } + reach->depth = value; + + /* Set insert cost. */ + value = pa[TRE_PARAM_COST_INS]; + if (value == TRE_PARAM_DEFAULT) + reach->params.cost_ins = default_params.cost_ins; + else if (value != TRE_PARAM_UNSET) + reach->params.cost_ins = value; + + /* Set delete cost. */ + value = pa[TRE_PARAM_COST_DEL]; + if (value == TRE_PARAM_DEFAULT) + reach->params.cost_del = default_params.cost_del; + else if (value != TRE_PARAM_UNSET) + reach->params.cost_del = value; + + /* Set substitute cost. */ + value = pa[TRE_PARAM_COST_SUBST]; + if (value == TRE_PARAM_DEFAULT) + reach->params.cost_subst = default_params.cost_subst; + else + reach->params.cost_subst = value; + + /* Set maximum cost. */ + value = pa[TRE_PARAM_COST_MAX]; + if (value == TRE_PARAM_DEFAULT) + reach->params.max_cost = default_params.max_cost; + else if (value != TRE_PARAM_UNSET) + reach->params.max_cost = value; + + /* Set maximum inserts. */ + value = pa[TRE_PARAM_MAX_INS]; + if (value == TRE_PARAM_DEFAULT) + reach->params.max_ins = default_params.max_ins; + else if (value != TRE_PARAM_UNSET) + reach->params.max_ins = value; + + /* Set maximum deletes. */ + value = pa[TRE_PARAM_MAX_DEL]; + if (value == TRE_PARAM_DEFAULT) + reach->params.max_del = default_params.max_del; + else if (value != TRE_PARAM_UNSET) + reach->params.max_del = value; + + /* Set maximum substitutes. */ + value = pa[TRE_PARAM_MAX_SUBST]; + if (value == TRE_PARAM_DEFAULT) + reach->params.max_subst = default_params.max_subst; + else if (value != TRE_PARAM_UNSET) + reach->params.max_subst = value; + + /* Set maximum number of errors. */ + value = pa[TRE_PARAM_MAX_ERR]; + if (value == TRE_PARAM_DEFAULT) + reach->params.max_err = default_params.max_err; + else if (value != TRE_PARAM_UNSET) + reach->params.max_err = value; +} + +reg_errcode_t +tre_tnfa_run_approx(const tre_tnfa_t *tnfa, const void *string, int len, + tre_str_type_t type, int *match_tags, + regamatch_t *match, regaparams_t default_params, + int eflags, int *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + int pos = -1; + unsigned int pos_add_next = 1; +#ifdef TRE_WCHAR + const wchar_t *str_wide = string; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* !TRE_WCHAR */ +#endif /* TRE_WCHAR */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + int str_user_end = 0; + + int prev_pos; + + /* Number of tags. */ + int num_tags; + /* The reach tables. */ + tre_tnfa_approx_reach_t *reach, *reach_next; + /* Tag array for temporary use. */ + int *tmp_tags; + + /* End offset of best match so far, or -1 if no match found yet. */ + int match_eo = -1; + /* Costs of the match. */ + int match_costs[TRE_M_LAST]; + + /* Space for temporary data required for matching. */ + unsigned char *buf; + + int i, id; + + if (!match_tags) + num_tags = 0; + else + num_tags = tnfa->num_tags; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + DPRINT(("tre_tnfa_run_approx, input type %d, len %d, eflags %d, " + "match_tags %p\n", + type, len, eflags, + match_tags)); + DPRINT(("max cost %d, ins %d, del %d, subst %d\n", + default_params.max_cost, + default_params.cost_ins, + default_params.cost_del, + default_params.cost_subst)); + + /* Allocate memory for temporary data required for matching. This needs to + be done for every matching operation to be thread safe. This allocates + everything in a single large block from the stack frame using alloca() + or with malloc() if alloca is unavailable. */ + { + unsigned char *buf_cursor; + /* Space needed for one array of tags. */ + int tag_bytes = sizeof(*tmp_tags) * num_tags; + /* Space needed for one reach table. */ + int reach_bytes = sizeof(*reach_next) * tnfa->num_states; + /* Total space needed. */ + int total_bytes = reach_bytes * 2 + (tnfa->num_states * 2 + 1 ) * tag_bytes; + /* Add some extra to make sure we can align the pointers. The multiplier + used here must be equal to the number of ALIGN calls below. */ + total_bytes += (sizeof(long) - 1) * 3; + + /* Allocate the memory. */ +#ifdef TRE_USE_ALLOCA + buf = alloca(total_bytes); +#else /* !TRE_USE_ALLOCA */ + buf = xmalloc((unsigned)total_bytes); +#endif /* !TRE_USE_ALLOCA */ + if (!buf) + return REG_ESPACE; + memset(buf, 0, (size_t)total_bytes); + + /* Allocate `tmp_tags' from `buf'. */ + tmp_tags = (void *)buf; + buf_cursor = buf + tag_bytes; + buf_cursor += ALIGN(buf_cursor, long); + + /* Allocate `reach' from `buf'. */ + reach = (void *)buf_cursor; + buf_cursor += reach_bytes; + buf_cursor += ALIGN(buf_cursor, long); + + /* Allocate `reach_next' from `buf'. */ + reach_next = (void *)buf_cursor; + buf_cursor += reach_bytes; + buf_cursor += ALIGN(buf_cursor, long); + + /* Allocate tag arrays for `reach' and `reach_next' from `buf'. */ + for (i = 0; i < tnfa->num_states; i++) + { + reach[i].tags = (void *)buf_cursor; + buf_cursor += tag_bytes; + reach_next[i].tags = (void *)buf_cursor; + buf_cursor += tag_bytes; + } + assert(buf_cursor <= buf + total_bytes); + } + + for (i = 0; i < TRE_M_LAST; i++) + match_costs[i] = INT_MAX; + + /* Mark the reach arrays empty. */ + for (i = 0; i < tnfa->num_states; i++) + reach[i].pos = reach_next[i].pos = -2; + + prev_pos = pos; + GET_NEXT_WCHAR(); + pos = 0; + + while (/*CONSTCOND*/1) + { + DPRINT(("%03d:%2lc/%05d\n", pos, (tre_cint_t)next_c, (int)next_c)); + + /* Add initial states to `reach_next' if an exact match has not yet + been found. */ + if (match_costs[TRE_M_COST] > 0) + { + tre_tnfa_transition_t *trans; + DPRINT((" init")); + for (trans = tnfa->initial; trans->state; trans++) + { + int stateid = trans->state_id; + + /* If this state is not currently in `reach_next', add it + there. */ + if (reach_next[stateid].pos < pos) + { + if (trans->assertions && CHECK_ASSERTIONS(trans->assertions)) + { + /* Assertions failed, don't add this state. */ + DPRINT((" !%d (assert)", stateid)); + continue; + } + DPRINT((" %d", stateid)); + reach_next[stateid].state = trans->state; + reach_next[stateid].pos = pos; + + /* Compute tag values after this transition. */ + for (i = 0; i < num_tags; i++) + reach_next[stateid].tags[i] = -1; + + if (trans->tags) + for (i = 0; trans->tags[i] >= 0; i++) + if (trans->tags[i] < num_tags) + reach_next[stateid].tags[trans->tags[i]] = pos; + + /* Set the parameters, depth, and costs. */ + reach_next[stateid].params = default_params; + reach_next[stateid].depth = 0; + for (i = 0; i < TRE_M_LAST; i++) + reach_next[stateid].costs[0][i] = 0; + if (trans->params) + tre_set_params(&reach_next[stateid], trans->params, + default_params); + + /* If this is the final state, mark the exact match. */ + if (trans->state == tnfa->final) + { + match_eo = pos; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next[stateid].tags[i]; + for (i = 0; i < TRE_M_LAST; i++) + match_costs[i] = 0; + } + } + } + DPRINT(("\n")); + } + + + /* Handle inserts. This is done by pretending there's an epsilon + transition from each state in `reach' back to the same state. + We don't need to worry about the final state here; this will never + give a better match than what we already have. */ + for (id = 0; id < tnfa->num_states; id++) + { + int depth; + int cost, cost0; + + if (reach[id].pos != prev_pos) + { + DPRINT((" insert: %d not reached\n", id)); + continue; /* Not reached. */ + } + + depth = reach[id].depth; + + /* Compute and check cost at current depth. */ + cost = reach[id].costs[depth][TRE_M_COST]; + if (reach[id].params.cost_ins != TRE_PARAM_UNSET) + cost += reach[id].params.cost_ins; + if (cost > reach[id].params.max_cost) + continue; /* Cost too large. */ + + /* Check number of inserts at current depth. */ + if (reach[id].costs[depth][TRE_M_NUM_INS] + 1 + > reach[id].params.max_ins) + continue; /* Too many inserts. */ + + /* Check total number of errors at current depth. */ + if (reach[id].costs[depth][TRE_M_NUM_ERR] + 1 + > reach[id].params.max_err) + continue; /* Too many errors. */ + + /* Compute overall cost. */ + cost0 = cost; + if (depth > 0) + { + cost0 = reach[id].costs[0][TRE_M_COST]; + if (reach[id].params.cost_ins != TRE_PARAM_UNSET) + cost0 += reach[id].params.cost_ins; + else + cost0 += default_params.cost_ins; + } + + DPRINT((" insert: from %d to %d, cost %d: ", id, id, + reach[id].costs[depth][TRE_M_COST])); + if (reach_next[id].pos == pos + && (cost0 >= reach_next[id].costs[0][TRE_M_COST])) + { + DPRINT(("lose\n")); + continue; + } + DPRINT(("win\n")); + + /* Copy state, position, tags, parameters, and depth. */ + reach_next[id].state = reach[id].state; + reach_next[id].pos = pos; + for (i = 0; i < num_tags; i++) + reach_next[id].tags[i] = reach[id].tags[i]; + reach_next[id].params = reach[id].params; + reach_next[id].depth = reach[id].depth; + + /* Set the costs after this transition. */ + memcpy(reach_next[id].costs, reach[id].costs, + sizeof(reach_next[id].costs[0][0]) + * TRE_M_LAST * (depth + 1)); + reach_next[id].costs[depth][TRE_M_COST] = cost; + reach_next[id].costs[depth][TRE_M_NUM_INS]++; + reach_next[id].costs[depth][TRE_M_NUM_ERR]++; + if (depth > 0) + { + reach_next[id].costs[0][TRE_M_COST] = cost0; + reach_next[id].costs[0][TRE_M_NUM_INS]++; + reach_next[id].costs[0][TRE_M_NUM_ERR]++; + } + + } + + + /* Handle deletes. This is done by traversing through the whole TNFA + pretending that all transitions are epsilon transitions, until + no more states can be reached with better costs. */ + { + /* XXX - dynamic ringbuffer size */ + tre_tnfa_approx_reach_t *ringbuffer[512]; + tre_tnfa_approx_reach_t **deque_start, **deque_end; + + deque_start = deque_end = ringbuffer; + + /* Add all states in `reach_next' to the deque. */ + for (id = 0; id < tnfa->num_states; id++) + { + if (reach_next[id].pos != pos) + continue; + *deque_end = &reach_next[id]; + deque_end++; + assert(deque_end != deque_start); + } + + /* Repeat until the deque is empty. */ + while (deque_end != deque_start) + { + tre_tnfa_approx_reach_t *reach_p; + int depth; + int cost, cost0; + tre_tnfa_transition_t *trans; + + /* Pop the first item off the deque. */ + reach_p = *deque_start; + id = reach_p - reach_next; + depth = reach_p->depth; + + /* Compute cost at current depth. */ + cost = reach_p->costs[depth][TRE_M_COST]; + if (reach_p->params.cost_del != TRE_PARAM_UNSET) + cost += reach_p->params.cost_del; + + /* Check cost, number of deletes, and total number of errors + at current depth. */ + if (cost > reach_p->params.max_cost + || (reach_p->costs[depth][TRE_M_NUM_DEL] + 1 + > reach_p->params.max_del) + || (reach_p->costs[depth][TRE_M_NUM_ERR] + 1 + > reach_p->params.max_err)) + { + /* Too many errors or cost too large. */ + DPRINT((" delete: from %03d: cost too large\n", id)); + deque_start++; + if (deque_start >= (ringbuffer + 512)) + deque_start = ringbuffer; + continue; + } + + /* Compute overall cost. */ + cost0 = cost; + if (depth > 0) + { + cost0 = reach_p->costs[0][TRE_M_COST]; + if (reach_p->params.cost_del != TRE_PARAM_UNSET) + cost0 += reach_p->params.cost_del; + else + cost0 += default_params.cost_del; + } + + for (trans = reach_p->state; trans->state; trans++) + { + int dest_id = trans->state_id; + DPRINT((" delete: from %03d to %03d, cost %d (%d): ", + id, dest_id, cost0, reach_p->params.max_cost)); + + if (trans->assertions && CHECK_ASSERTIONS(trans->assertions)) + { + DPRINT(("assertion failed\n")); + continue; + } + + /* Compute tag values after this transition. */ + for (i = 0; i < num_tags; i++) + tmp_tags[i] = reach_p->tags[i]; + if (trans->tags) + for (i = 0; trans->tags[i] >= 0; i++) + if (trans->tags[i] < num_tags) + tmp_tags[trans->tags[i]] = pos; + + /* If another path has also reached this state, choose the one + with the smallest cost or best tags if costs are equal. */ + if (reach_next[dest_id].pos == pos + && (cost0 > reach_next[dest_id].costs[0][TRE_M_COST] + || (cost0 == reach_next[dest_id].costs[0][TRE_M_COST] + && (!match_tags + || !tre_tag_order(num_tags, + tnfa->tag_directions, + tmp_tags, + reach_next[dest_id].tags))))) + { + DPRINT(("lose, cost0 %d, have %d\n", + cost0, reach_next[dest_id].costs[0][TRE_M_COST])); + continue; + } + DPRINT(("win\n")); + + /* Set state, position, tags, parameters, depth, and costs. */ + reach_next[dest_id].state = trans->state; + reach_next[dest_id].pos = pos; + for (i = 0; i < num_tags; i++) + reach_next[dest_id].tags[i] = tmp_tags[i]; + + reach_next[dest_id].params = reach_p->params; + if (trans->params) + tre_set_params(&reach_next[dest_id], trans->params, + default_params); + + reach_next[dest_id].depth = reach_p->depth; + memcpy(&reach_next[dest_id].costs, + reach_p->costs, + sizeof(reach_p->costs[0][0]) + * TRE_M_LAST * (depth + 1)); + reach_next[dest_id].costs[depth][TRE_M_COST] = cost; + reach_next[dest_id].costs[depth][TRE_M_NUM_DEL]++; + reach_next[dest_id].costs[depth][TRE_M_NUM_ERR]++; + if (depth > 0) + { + reach_next[dest_id].costs[0][TRE_M_COST] = cost0; + reach_next[dest_id].costs[0][TRE_M_NUM_DEL]++; + reach_next[dest_id].costs[0][TRE_M_NUM_ERR]++; + } + + if (trans->state == tnfa->final + && (match_eo < 0 + || match_costs[TRE_M_COST] > cost0 + || (match_costs[TRE_M_COST] == cost0 + && (num_tags > 0 + && tmp_tags[0] <= match_tags[0])))) + { + DPRINT((" setting new match at %d, cost %d\n", + pos, cost0)); + match_eo = pos; + memcpy(match_costs, reach_next[dest_id].costs[0], + sizeof(match_costs[0]) * TRE_M_LAST); + for (i = 0; i < num_tags; i++) + match_tags[i] = tmp_tags[i]; + } + + /* Add to the end of the deque. */ + *deque_end = &reach_next[dest_id]; + deque_end++; + if (deque_end >= (ringbuffer + 512)) + deque_end = ringbuffer; + assert(deque_end != deque_start); + } + deque_start++; + if (deque_start >= (ringbuffer + 512)) + deque_start = ringbuffer; + } + + } + +#ifdef TRE_DEBUG + tre_print_reach(tnfa, reach_next, pos, num_tags); +#endif /* TRE_DEBUG */ + + /* Check for end of string. */ + if (len < 0) + { + if (type == STR_USER) + { + if (str_user_end) + break; + } + else if (next_c == L'\0') + break; + } + else + { + if (pos >= len) + break; + } + + prev_pos = pos; + GET_NEXT_WCHAR(); + + /* Swap `reach' and `reach_next'. */ + { + tre_tnfa_approx_reach_t *tmp; + tmp = reach; + reach = reach_next; + reach_next = tmp; + } + + /* Handle exact matches and substitutions. */ + for (id = 0; id < tnfa->num_states; id++) + { + tre_tnfa_transition_t *trans; + + if (reach[id].pos < prev_pos) + continue; /* Not reached. */ + for (trans = reach[id].state; trans->state; trans++) + { + int dest_id; + int depth; + int cost, cost0, err; + + if (trans->assertions + && (CHECK_ASSERTIONS(trans->assertions) + || CHECK_CHAR_CLASSES(trans, tnfa, eflags))) + { + DPRINT((" exact, from %d: assert failed\n", id)); + continue; + } + + depth = reach[id].depth; + dest_id = trans->state_id; + + cost = reach[id].costs[depth][TRE_M_COST]; + cost0 = reach[id].costs[0][TRE_M_COST]; + err = 0; + + if (trans->code_min > (tre_cint_t)prev_c + || trans->code_max < (tre_cint_t)prev_c) + { + /* Handle substitutes. The required character was not in + the string, so match it in place of whatever was supposed + to be there and increase costs accordingly. */ + err = 1; + + /* Compute and check cost at current depth. */ + cost = reach[id].costs[depth][TRE_M_COST]; + if (reach[id].params.cost_subst != TRE_PARAM_UNSET) + cost += reach[id].params.cost_subst; + if (cost > reach[id].params.max_cost) + continue; /* Cost too large. */ + + /* Check number of substitutes at current depth. */ + if (reach[id].costs[depth][TRE_M_NUM_SUBST] + 1 + > reach[id].params.max_subst) + continue; /* Too many substitutes. */ + + /* Check total number of errors at current depth. */ + if (reach[id].costs[depth][TRE_M_NUM_ERR] + 1 + > reach[id].params.max_err) + continue; /* Too many errors. */ + + /* Compute overall cost. */ + cost0 = cost; + if (depth > 0) + { + cost0 = reach[id].costs[0][TRE_M_COST]; + if (reach[id].params.cost_subst != TRE_PARAM_UNSET) + cost0 += reach[id].params.cost_subst; + else + cost0 += default_params.cost_subst; + } + DPRINT((" subst, from %03d to %03d, cost %d: ", + id, dest_id, cost0)); + } + else + DPRINT((" exact, from %03d to %03d, cost %d: ", + id, dest_id, cost0)); + + /* Compute tag values after this transition. */ + for (i = 0; i < num_tags; i++) + tmp_tags[i] = reach[id].tags[i]; + if (trans->tags) + for (i = 0; trans->tags[i] >= 0; i++) + if (trans->tags[i] < num_tags) + tmp_tags[trans->tags[i]] = pos; + + /* If another path has also reached this state, choose the + one with the smallest cost or best tags if costs are equal. */ + if (reach_next[dest_id].pos == pos + && (cost0 > reach_next[dest_id].costs[0][TRE_M_COST] + || (cost0 == reach_next[dest_id].costs[0][TRE_M_COST] + && !tre_tag_order(num_tags, tnfa->tag_directions, + tmp_tags, + reach_next[dest_id].tags)))) + { + DPRINT(("lose\n")); + continue; + } + DPRINT(("win %d %d\n", + reach_next[dest_id].pos, + reach_next[dest_id].costs[0][TRE_M_COST])); + + /* Set state, position, tags, and depth. */ + reach_next[dest_id].state = trans->state; + reach_next[dest_id].pos = pos; + for (i = 0; i < num_tags; i++) + reach_next[dest_id].tags[i] = tmp_tags[i]; + reach_next[dest_id].depth = reach[id].depth; + + /* Set parameters. */ + reach_next[dest_id].params = reach[id].params; + if (trans->params) + tre_set_params(&reach_next[dest_id], trans->params, + default_params); + + /* Set the costs after this transition. */ + memcpy(&reach_next[dest_id].costs, + reach[id].costs, + sizeof(reach[id].costs[0][0]) + * TRE_M_LAST * (depth + 1)); + reach_next[dest_id].costs[depth][TRE_M_COST] = cost; + reach_next[dest_id].costs[depth][TRE_M_NUM_SUBST] += err; + reach_next[dest_id].costs[depth][TRE_M_NUM_ERR] += err; + if (depth > 0) + { + reach_next[dest_id].costs[0][TRE_M_COST] = cost0; + reach_next[dest_id].costs[0][TRE_M_NUM_SUBST] += err; + reach_next[dest_id].costs[0][TRE_M_NUM_ERR] += err; + } + + if (trans->state == tnfa->final + && (match_eo < 0 + || cost0 < match_costs[TRE_M_COST] + || (cost0 == match_costs[TRE_M_COST] + && num_tags > 0 && tmp_tags[0] <= match_tags[0]))) + { + DPRINT((" setting new match at %d, cost %d\n", + pos, cost0)); + match_eo = pos; + for (i = 0; i < TRE_M_LAST; i++) + match_costs[i] = reach_next[dest_id].costs[0][i]; + for (i = 0; i < num_tags; i++) + match_tags[i] = tmp_tags[i]; + } + } + } + } + + DPRINT(("match end offset = %d, match cost = %d\n", match_eo, + match_costs[TRE_M_COST])); + +#ifndef TRE_USE_ALLOCA + if (buf) + xfree(buf); +#endif /* !TRE_USE_ALLOCA */ + + match->cost = match_costs[TRE_M_COST]; + match->num_ins = match_costs[TRE_M_NUM_INS]; + match->num_del = match_costs[TRE_M_NUM_DEL]; + match->num_subst = match_costs[TRE_M_NUM_SUBST]; + *match_end_ofs = match_eo; + + return match_eo >= 0 ? REG_OK : REG_NOMATCH; +} +/* + tre-match-backtrack.c - TRE backtracking regex matching engine + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + This matcher is for regexps that use back referencing. Regexp matching + with back referencing is an NP-complete problem on the number of back + references. The easiest way to match them is to use a backtracking + routine which basically goes through all possible paths in the TNFA + and chooses the one which results in the best (leftmost and longest) + match. This can be spectacularly expensive and may run out of stack + space, but there really is no better known generic algorithm. Quoting + Henry Spencer from comp.compilers: + <URL: http://compilers.iecc.com/comparch/article/93-03-102> + + POSIX.2 REs require longest match, which is really exciting to + implement since the obsolete ("basic") variant also includes + \<digit>. I haven't found a better way of tackling this than doing + a preliminary match using a DFA (or simulation) on a modified RE + that just replicates subREs for \<digit>, and then doing a + backtracking match to determine whether the subRE matches were + right. This can be rather slow, but I console myself with the + thought that people who use \<digit> deserve very slow execution. + (Pun unintentional but very appropriate.) + +*/ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +#ifdef TRE_USE_ALLOCA +/* AIX requires this to be the first thing in the file. */ +#ifndef __GNUC__ +# if HAVE_ALLOCA_H +# include <alloca.h> +# else +# ifdef _AIX + #pragma alloca +# else +# ifndef alloca /* predefined by HP cc +Olibcalls */ +char *alloca (); +# endif +# endif +# endif +#endif +#endif /* TRE_USE_ALLOCA */ + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* HAVE_WCTYPE_H */ +#ifndef TRE_WCHAR +#include <ctype.h> +#endif /* !TRE_WCHAR */ +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif /* HAVE_MALLOC_H */ + + +typedef struct { + int pos; + const char *str_byte; +#ifdef TRE_WCHAR + const wchar_t *str_wide; +#endif /* TRE_WCHAR */ + tre_tnfa_transition_t *state; + int state_id; + int next_c; + int *tags; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ +} tre_backtrack_item_t; + +typedef struct tre_backtrack_struct { + tre_backtrack_item_t item; + struct tre_backtrack_struct *prev; + struct tre_backtrack_struct *next; +} *tre_backtrack_t; + +#ifdef TRE_WCHAR +#define BT_STACK_WIDE_IN(_str_wide) stack->item.str_wide = (_str_wide) +#define BT_STACK_WIDE_OUT (str_wide) = stack->item.str_wide +#else /* !TRE_WCHAR */ +#define BT_STACK_WIDE_IN(_str_wide) +#define BT_STACK_WIDE_OUT +#endif /* !TRE_WCHAR */ + +#ifdef TRE_MBSTATE +#define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate) +#define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate +#else /* !TRE_MBSTATE */ +#define BT_STACK_MBSTATE_IN +#define BT_STACK_MBSTATE_OUT +#endif /* !TRE_MBSTATE */ + + +#ifdef TRE_USE_ALLOCA +#define tre_bt_mem_new tre_mem_newa +#define tre_bt_mem_alloc tre_mem_alloca +#define tre_bt_mem_destroy(obj) do { } while (0) +#else /* !TRE_USE_ALLOCA */ +#define tre_bt_mem_new tre_mem_new +#define tre_bt_mem_alloc tre_mem_alloc +#define tre_bt_mem_destroy tre_mem_destroy +#endif /* !TRE_USE_ALLOCA */ + + +#define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \ + do \ + { \ + int i; \ + if (!stack->next) \ + { \ + tre_backtrack_t s; \ + s = tre_bt_mem_alloc(mem, sizeof(*s)); \ + if (!s) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + s->prev = stack; \ + s->next = NULL; \ + s->item.tags = tre_bt_mem_alloc(mem, \ + sizeof(*tags) * tnfa->num_tags); \ + if (!s->item.tags) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + stack->next = s; \ + stack = s; \ + } \ + else \ + stack = stack->next; \ + stack->item.pos = (_pos); \ + stack->item.str_byte = (_str_byte); \ + BT_STACK_WIDE_IN(_str_wide); \ + stack->item.state = (_state); \ + stack->item.state_id = (_state_id); \ + stack->item.next_c = (_next_c); \ + for (i = 0; i < tnfa->num_tags; i++) \ + stack->item.tags[i] = (_tags)[i]; \ + BT_STACK_MBSTATE_IN; \ + } \ + while (/*CONSTCOND*/0) + +#define BT_STACK_POP() \ + do \ + { \ + int i; \ + assert(stack->prev); \ + pos = stack->item.pos; \ + if (type == STR_USER) \ + str_source->rewind(pos + pos_add_next, str_source->context); \ + str_byte = stack->item.str_byte; \ + BT_STACK_WIDE_OUT; \ + state = stack->item.state; \ + next_c = stack->item.next_c; \ + for (i = 0; i < tnfa->num_tags; i++) \ + tags[i] = stack->item.tags[i]; \ + BT_STACK_MBSTATE_OUT; \ + stack = stack->prev; \ + } \ + while (/*CONSTCOND*/0) + +#undef MIN +#define MIN(a, b) ((a) <= (b) ? (a) : (b)) + +reg_errcode_t +tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, + int len, tre_str_type_t type, int *match_tags, + int eflags, int *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + int pos = 0; + unsigned int pos_add_next = 1; +#ifdef TRE_WCHAR + const wchar_t *str_wide = string; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ +#endif /* TRE_WCHAR */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + int str_user_end = 0; + + /* These are used to remember the necessary values of the above + variables to return to the position where the current search + started from. */ + int next_c_start; + const char *str_byte_start; + int pos_start = -1; +#ifdef TRE_WCHAR + const wchar_t *str_wide_start; +#endif /* TRE_WCHAR */ +#ifdef TRE_MBSTATE + mbstate_t mbstate_start; +#endif /* TRE_MBSTATE */ + + /* End offset of best match so far, or -1 if no match found yet. */ + int match_eo = -1; + /* Tag arrays. */ + int *next_tags, *tags = NULL; + /* Current TNFA state. */ + tre_tnfa_transition_t *state; + int *states_seen = NULL; + + /* Memory allocator to for allocating the backtracking stack. */ + tre_mem_t mem = tre_bt_mem_new(); + + /* The backtracking stack. */ + tre_backtrack_t stack; + + tre_tnfa_transition_t *trans_i; + regmatch_t *pmatch = NULL; + int ret; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + if (!mem) + return REG_ESPACE; + stack = tre_bt_mem_alloc(mem, sizeof(*stack)); + if (!stack) + { + ret = REG_ESPACE; + goto error_exit; + } + stack->prev = NULL; + stack->next = NULL; + + DPRINT(("tnfa_execute_backtrack, input type %d\n", type)); + DPRINT(("len = %d\n", len)); + +#ifdef TRE_USE_ALLOCA + tags = alloca(sizeof(*tags) * tnfa->num_tags); + pmatch = alloca(sizeof(*pmatch) * tnfa->num_submatches); + states_seen = alloca(sizeof(*states_seen) * tnfa->num_states); +#else /* !TRE_USE_ALLOCA */ + if (tnfa->num_tags) + { + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); + if (!tags) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_submatches) + { + pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches); + if (!pmatch) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_states) + { + states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states); + if (!states_seen) + { + ret = REG_ESPACE; + goto error_exit; + } + } +#endif /* !TRE_USE_ALLOCA */ + + retry: + { + int i; + for (i = 0; i < tnfa->num_tags; i++) + { + tags[i] = -1; + if (match_tags) + match_tags[i] = -1; + } + for (i = 0; i < tnfa->num_states; i++) + states_seen[i] = 0; + } + + state = NULL; + pos = pos_start; + if (type == STR_USER) + str_source->rewind(pos + pos_add_next, str_source->context); + GET_NEXT_WCHAR(); + pos_start = pos; + next_c_start = next_c; + str_byte_start = str_byte; +#ifdef TRE_WCHAR + str_wide_start = str_wide; +#endif /* TRE_WCHAR */ +#ifdef TRE_MBSTATE + mbstate_start = mbstate; +#endif /* TRE_MBSTATE */ + + /* Handle initial states. */ + next_tags = NULL; + for (trans_i = tnfa->initial; trans_i->state; trans_i++) + { + DPRINT(("> init %p, prev_c %lc\n", trans_i->state, (tre_cint_t)prev_c)); + if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) + { + DPRINT(("assert failed\n")); + continue; + } + if (state == NULL) + { + /* Start from this state. */ + state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Backtrack to this state. */ + DPRINT(("saving state %d for backtracking\n", trans_i->state_id)); + BT_STACK_PUSH(pos, str_byte, str_wide, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp = trans_i->tags; + if (tmp) + while (*tmp >= 0) + stack->item.tags[*tmp++] = pos; + } + } + } + + if (next_tags) + for (; *next_tags >= 0; next_tags++) + tags[*next_tags] = pos; + + + DPRINT(("entering match loop, pos %d, str_byte %p\n", pos, str_byte)); + DPRINT(("pos:chr/code | state and tags\n")); + DPRINT(("-------------+------------------------------------------------\n")); + + if (state == NULL) + goto backtrack; + + while (/*CONSTCOND*/1) + { + tre_tnfa_transition_t *next_state; + int empty_br_match; + + DPRINT(("start loop\n")); + if (state == tnfa->final) + { + DPRINT((" match found, %d %d\n", match_eo, pos)); + if (match_eo < pos + || (match_eo == pos + && match_tags + && tre_tag_order(tnfa->num_tags, tnfa->tag_directions, + tags, match_tags))) + { + int i; + /* This match wins the previous match. */ + DPRINT((" win previous\n")); + match_eo = pos; + if (match_tags) + for (i = 0; i < tnfa->num_tags; i++) + match_tags[i] = tags[i]; + } + /* Our TNFAs never have transitions leaving from the final state, + so we jump right to backtracking. */ + goto backtrack; + } + +#ifdef TRE_DEBUG + DPRINT(("%3d:%2lc/%05d | %p ", pos, (tre_cint_t)next_c, (int)next_c, + state)); + { + int i; + for (i = 0; i < tnfa->num_tags; i++) + DPRINT(("%d%s", tags[i], i < tnfa->num_tags - 1 ? ", " : "")); + DPRINT(("\n")); + } +#endif /* TRE_DEBUG */ + + /* Go to the next character in the input string. */ + empty_br_match = 0; + trans_i = state; + if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) + { + /* This is a back reference state. All transitions leaving from + this state have the same back reference "assertion". Instead + of reading the next character, we match the back reference. */ + int so, eo, bt = trans_i->u.backref; + int bt_len; + int result; + + DPRINT((" should match back reference %d\n", bt)); + /* Get the substring we need to match against. Remember to + turn off REG_NOSUB temporarily. */ + tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & /*LINTED*/!REG_NOSUB, + tnfa, tags, pos); + so = pmatch[bt].rm_so; + eo = pmatch[bt].rm_eo; + bt_len = eo - so; + +#ifdef TRE_DEBUG + { + int slen; + if (len < 0) + slen = bt_len; + else + slen = MIN(bt_len, len - pos); + + if (type == STR_BYTE) + { + DPRINT((" substring (len %d) is [%d, %d[: '%.*s'\n", + bt_len, so, eo, bt_len, (char*)string + so)); + DPRINT((" current string is '%.*s'\n", slen, str_byte - 1)); + } +#ifdef TRE_WCHAR + else if (type == STR_WIDE) + { + DPRINT((" substring (len %d) is [%d, %d[: '%.*" STRF "'\n", + bt_len, so, eo, bt_len, (wchar_t*)string + so)); + DPRINT((" current string is '%.*" STRF "'\n", + slen, str_wide - 1)); + } +#endif /* TRE_WCHAR */ + } +#endif + + if (len < 0) + { + if (type == STR_USER) + result = str_source->compare((unsigned)so, (unsigned)pos, + (unsigned)bt_len, + str_source->context); +#ifdef TRE_WCHAR + else if (type == STR_WIDE) + result = wcsncmp((const wchar_t*)string + so, str_wide - 1, + (size_t)bt_len); +#endif /* TRE_WCHAR */ + else + result = strncmp((const char*)string + so, str_byte - 1, + (size_t)bt_len); + } + else if (len - pos < bt_len) + result = 1; +#ifdef TRE_WCHAR + else if (type == STR_WIDE) + result = wmemcmp((const wchar_t*)string + so, str_wide - 1, + (size_t)bt_len); +#endif /* TRE_WCHAR */ + else + result = memcmp((const char*)string + so, str_byte - 1, + (size_t)bt_len); + + if (result == 0) + { + /* Back reference matched. Check for infinite loop. */ + if (bt_len == 0) + empty_br_match = 1; + if (empty_br_match && states_seen[trans_i->state_id]) + { + DPRINT((" avoid loop\n")); + goto backtrack; + } + + states_seen[trans_i->state_id] = empty_br_match; + + /* Advance in input string and resync `prev_c', `next_c' + and pos. */ + DPRINT((" back reference matched\n")); + str_byte += bt_len - 1; +#ifdef TRE_WCHAR + str_wide += bt_len - 1; +#endif /* TRE_WCHAR */ + pos += bt_len - 1; + GET_NEXT_WCHAR(); + DPRINT((" pos now %d\n", pos)); + } + else + { + DPRINT((" back reference did not match\n")); + goto backtrack; + } + } + else + { + /* Check for end of string. */ + if (len < 0) + { + if (type == STR_USER) + { + if (str_user_end) + goto backtrack; + } + else if (next_c == L'\0') + goto backtrack; + } + else + { + if (pos >= len) + goto backtrack; + } + + /* Read the next character. */ + GET_NEXT_WCHAR(); + } + + next_state = NULL; + for (trans_i = state; trans_i->state; trans_i++) + { + DPRINT((" transition %d-%d (%c-%c) %d to %d\n", + trans_i->code_min, trans_i->code_max, + trans_i->code_min, trans_i->code_max, + trans_i->assertions, trans_i->state_id)); + if (trans_i->code_min <= (tre_cint_t)prev_c + && trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + DPRINT((" assertion failed\n")); + continue; + } + + if (next_state == NULL) + { + /* First matching transition. */ + DPRINT((" Next state is %d\n", trans_i->state_id)); + next_state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Second matching transition. We may need to backtrack here + to take this transition instead of the first one, so we + push this transition in the backtracking stack so we can + jump back here if needed. */ + DPRINT((" saving state %d for backtracking\n", + trans_i->state_id)); + BT_STACK_PUSH(pos, str_byte, str_wide, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp; + for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) + stack->item.tags[*tmp] = pos; + } +#if 0 /* XXX - it's important not to look at all transitions here to keep + the stack small! */ + break; +#endif + } + } + } + + if (next_state != NULL) + { + /* Matching transitions were found. Take the first one. */ + state = next_state; + + /* Update the tag values. */ + if (next_tags) + while (*next_tags >= 0) + tags[*next_tags++] = pos; + } + else + { + backtrack: + /* A matching transition was not found. Try to backtrack. */ + if (stack->prev) + { + DPRINT((" backtracking\n")); + if (stack->item.state->assertions && ASSERT_BACKREF) + { + DPRINT((" states_seen[%d] = 0\n", + stack->item.state_id)); + states_seen[stack->item.state_id] = 0; + } + + BT_STACK_POP(); + } + else if (match_eo < 0) + { + /* Try starting from a later position in the input string. */ + /* Check for end of string. */ + if (len < 0) + { + if (next_c == L'\0') + { + DPRINT(("end of string.\n")); + break; + } + } + else + { + if (pos >= len) + { + DPRINT(("end of string.\n")); + break; + } + } + DPRINT(("restarting from next start position\n")); + next_c = next_c_start; +#ifdef TRE_MBSTATE + mbstate = mbstate_start; +#endif /* TRE_MBSTATE */ + str_byte = str_byte_start; +#ifdef TRE_WCHAR + str_wide = str_wide_start; +#endif /* TRE_WCHAR */ + goto retry; + } + else + { + DPRINT(("finished\n")); + break; + } + } + } + + ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; + *match_end_ofs = match_eo; + + error_exit: + tre_bt_mem_destroy(mem); +#ifndef TRE_USE_ALLOCA + if (tags) + xfree(tags); + if (pmatch) + xfree(pmatch); + if (states_seen) + xfree(states_seen); +#endif /* !TRE_USE_ALLOCA */ + + return ret; +} +/* + tre-match-parallel.c - TRE parallel regex matching engine + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + This algorithm searches for matches basically by reading characters + in the searched string one by one, starting at the beginning. All + matching paths in the TNFA are traversed in parallel. When two or + more paths reach the same state, exactly one is chosen according to + tag ordering rules; if returning submatches is not required it does + not matter which path is chosen. + + The worst case time required for finding the leftmost and longest + match, or determining that there is no match, is always linearly + dependent on the length of the text being searched. + + This algorithm cannot handle TNFAs with back referencing nodes. + See `tre-match-backtrack.c'. +*/ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +#ifdef TRE_USE_ALLOCA +/* AIX requires this to be the first thing in the file. */ +#ifndef __GNUC__ +# if HAVE_ALLOCA_H +# include <alloca.h> +# else +# ifdef _AIX + #pragma alloca +# else +# ifndef alloca /* predefined by HP cc +Olibcalls */ +char *alloca (); +# endif +# endif +# endif +#endif +#endif /* TRE_USE_ALLOCA */ + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#ifdef HAVE_WCHAR_H +#include <wchar.h> +#endif /* HAVE_WCHAR_H */ +#ifdef HAVE_WCTYPE_H +#include <wctype.h> +#endif /* HAVE_WCTYPE_H */ +#ifndef TRE_WCHAR +#include <ctype.h> +#endif /* !TRE_WCHAR */ +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif /* HAVE_MALLOC_H */ + + + + +typedef struct { + tre_tnfa_transition_t *state; + int *tags; +} tre_tnfa_reach_t; + +typedef struct { + int pos; + int **tags; +} tre_reach_pos_t; + + +#ifdef TRE_DEBUG +static void +tre_print_reach(const tre_tnfa_t *tnfa, tre_tnfa_reach_t *reach, int num_tags) +{ + int i; + + while (reach->state != NULL) + { + DPRINT((" %p", (void *)reach->state)); + if (num_tags > 0) + { + DPRINT(("/")); + for (i = 0; i < num_tags; i++) + { + DPRINT(("%d:%d", i, reach->tags[i])); + if (i < (num_tags-1)) + DPRINT((",")); + } + } + reach++; + } + DPRINT(("\n")); + +} +#endif /* TRE_DEBUG */ + +reg_errcode_t +tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, int len, + tre_str_type_t type, int *match_tags, int eflags, + int *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + int pos = -1; + unsigned int pos_add_next = 1; +#ifdef TRE_WCHAR + const wchar_t *str_wide = string; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ +#endif /* TRE_WCHAR */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + int str_user_end = 0; + + char *buf; + tre_tnfa_transition_t *trans_i; + tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i; + tre_reach_pos_t *reach_pos; + int *tag_i; + int num_tags, i; + + int match_eo = -1; /* end offset of match (-1 if no match found yet) */ + int new_match = 0; + int *tmp_tags = NULL; + int *tmp_iptr; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + DPRINT(("tre_tnfa_run_parallel, input type %d\n", type)); + + if (!match_tags) + num_tags = 0; + else + num_tags = tnfa->num_tags; + + /* Allocate memory for temporary data required for matching. This needs to + be done for every matching operation to be thread safe. This allocates + everything in a single large block from the stack frame using alloca() + or with malloc() if alloca is unavailable. */ + { + int tbytes, rbytes, pbytes, xbytes, total_bytes; + char *tmp_buf; + /* Compute the length of the block we need. */ + tbytes = sizeof(*tmp_tags) * num_tags; + rbytes = sizeof(*reach_next) * (tnfa->num_states + 1); + pbytes = sizeof(*reach_pos) * tnfa->num_states; + xbytes = sizeof(int) * num_tags; + total_bytes = + (sizeof(long) - 1) * 4 /* for alignment paddings */ + + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes; + + /* Allocate the memory. */ +#ifdef TRE_USE_ALLOCA + buf = alloca(total_bytes); +#else /* !TRE_USE_ALLOCA */ + buf = xmalloc((unsigned)total_bytes); +#endif /* !TRE_USE_ALLOCA */ + if (buf == NULL) + return REG_ESPACE; + memset(buf, 0, (size_t)total_bytes); + + /* Get the various pointers within tmp_buf (properly aligned). */ + tmp_tags = (void *)buf; + tmp_buf = buf + tbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_next = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_pos = (void *)tmp_buf; + tmp_buf += pbytes; + tmp_buf += ALIGN(tmp_buf, long); + for (i = 0; i < tnfa->num_states; i++) + { + reach[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + reach_next[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + } + } + + for (i = 0; i < tnfa->num_states; i++) + reach_pos[i].pos = -1; + + /* If only one character can start a match, find it first. */ + if (tnfa->first_char >= 0 && type == STR_BYTE && str_byte) + { + const char *orig_str = str_byte; + int first = tnfa->first_char; + + if (len >= 0) + str_byte = memchr(orig_str, first, (size_t)len); + else + str_byte = strchr(orig_str, first); + if (str_byte == NULL) + { +#ifndef TRE_USE_ALLOCA + if (buf) + xfree(buf); +#endif /* !TRE_USE_ALLOCA */ + return REG_NOMATCH; + } + DPRINT(("skipped %lu chars\n", (unsigned long)(str_byte - orig_str))); + if (str_byte >= orig_str + 1) + prev_c = (unsigned char)*(str_byte - 1); + next_c = (unsigned char)*str_byte; + pos = str_byte - orig_str; + if (len < 0 || pos < len) + str_byte++; + } + else + { + GET_NEXT_WCHAR(); + pos = 0; + } + +#if 0 + /* Skip over characters that cannot possibly be the first character + of a match. */ + if (tnfa->firstpos_chars != NULL) + { + char *chars = tnfa->firstpos_chars; + + if (len < 0) + { + const char *orig_str = str_byte; + /* XXX - use strpbrk() and wcspbrk() because they might be + optimized for the target architecture. Try also strcspn() + and wcscspn() and compare the speeds. */ + while (next_c != L'\0' && !chars[next_c]) + { + next_c = *str_byte++; + } + prev_c = *(str_byte - 2); + pos += str_byte - orig_str; + DPRINT(("skipped %d chars\n", str_byte - orig_str)); + } + else + { + while (pos <= len && !chars[next_c]) + { + prev_c = next_c; + next_c = (unsigned char)(*str_byte++); + pos++; + } + } + } +#endif + + DPRINT(("length: %d\n", len)); + DPRINT(("pos:chr/code | states and tags\n")); + DPRINT(("-------------+------------------------------------------------\n")); + + reach_next_i = reach_next; + while (/*CONSTCOND*/1) + { + /* If no match found yet, add the initial states to `reach_next'. */ + if (match_eo < 0) + { + DPRINT((" init >")); + trans_i = tnfa->initial; + while (trans_i->state != NULL) + { + if (reach_pos[trans_i->state_id].pos < pos) + { + if (trans_i->assertions + && CHECK_ASSERTIONS(trans_i->assertions)) + { + DPRINT(("assertion failed\n")); + trans_i++; + continue; + } + + DPRINT((" %p", (void *)trans_i->state)); + reach_next_i->state = trans_i->state; + for (i = 0; i < num_tags; i++) + reach_next_i->tags[i] = -1; + tag_i = trans_i->tags; + if (tag_i) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + reach_next_i->tags[*tag_i] = pos; + tag_i++; + } + if (reach_next_i->state == tnfa->final) + { + DPRINT((" found empty match\n")); + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + reach_next_i++; + } + trans_i++; + } + DPRINT(("\n")); + reach_next_i->state = NULL; + } + else + { + if (num_tags == 0 || reach_next_i == reach_next) + /* We have found a match. */ + break; + } + + /* Check for end of string. */ + if (len < 0) + { + if (type == STR_USER) + { + if (str_user_end) + break; + } + else if (next_c == L'\0') + break; + } + else + { + if (pos >= len) + break; + } + + GET_NEXT_WCHAR(); + +#ifdef TRE_DEBUG + DPRINT(("%3d:%2lc/%05d |", pos - 1, (tre_cint_t)prev_c, (int)prev_c)); + tre_print_reach(tnfa, reach_next, num_tags); + DPRINT(("%3d:%2lc/%05d |", pos, (tre_cint_t)next_c, (int)next_c)); + tre_print_reach(tnfa, reach_next, num_tags); +#endif /* TRE_DEBUG */ + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + + /* For each state in `reach', weed out states that don't fulfill the + minimal matching conditions. */ + if (tnfa->num_minimals && new_match) + { + new_match = 0; + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + int skip = 0; + for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) + { + int end = tnfa->minimal_tags[i]; + int start = tnfa->minimal_tags[i + 1]; + DPRINT((" Minimal start %d, end %d\n", start, end)); + if (end >= num_tags) + { + DPRINT((" Throwing %p out.\n", reach_i->state)); + skip = 1; + break; + } + else if (reach_i->tags[start] == match_tags[start] + && reach_i->tags[end] < match_tags[end]) + { + DPRINT((" Throwing %p out because t%d < %d\n", + reach_i->state, end, match_tags[end])); + skip = 1; + break; + } + } + if (!skip) + { + reach_next_i->state = reach_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = reach_i->tags; + reach_i->tags = tmp_iptr; + reach_next_i++; + } + } + reach_next_i->state = NULL; + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + } + + /* For each state in `reach' see if there is a transition leaving with + the current input symbol to a state not yet in `reach_next', and + add the destination states to `reach_next'. */ + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + for (trans_i = reach_i->state; trans_i->state; trans_i++) + { + /* Does this transition match the input symbol? */ + if (trans_i->code_min <= (tre_cint_t)prev_c && + trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + DPRINT(("assertion failed\n")); + continue; + } + + /* Compute the tags after this transition. */ + for (i = 0; i < num_tags; i++) + tmp_tags[i] = reach_i->tags[i]; + tag_i = trans_i->tags; + if (tag_i != NULL) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + tmp_tags[*tag_i] = pos; + tag_i++; + } + + if (reach_pos[trans_i->state_id].pos < pos) + { + /* Found an unvisited node. */ + reach_next_i->state = trans_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = tmp_tags; + tmp_tags = tmp_iptr; + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + + if (reach_next_i->state == tnfa->final + && (match_eo == -1 + || (num_tags > 0 + && reach_next_i->tags[0] <= match_tags[0]))) + { + DPRINT((" found match %p\n", trans_i->state)); + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_next_i++; + + } + else + { + assert(reach_pos[trans_i->state_id].pos == pos); + /* Another path has also reached this state. We choose + the winner by examining the tag values for both + paths. */ + if (tre_tag_order(num_tags, tnfa->tag_directions, + tmp_tags, + *reach_pos[trans_i->state_id].tags)) + { + /* The new path wins. */ + tmp_iptr = *reach_pos[trans_i->state_id].tags; + *reach_pos[trans_i->state_id].tags = tmp_tags; + if (trans_i->state == tnfa->final) + { + DPRINT((" found better match\n")); + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = tmp_tags[i]; + } + tmp_tags = tmp_iptr; + } + } + } + } + } + reach_next_i->state = NULL; + } + + DPRINT(("match end offset = %d\n", match_eo)); + +#ifndef TRE_USE_ALLOCA + if (buf) + xfree(buf); +#endif /* !TRE_USE_ALLOCA */ + + *match_end_ofs = match_eo; + return match_eo >= 0 ? REG_OK : REG_NOMATCH; +} + +/* EOF */ +/* + tre-mem.c - TRE memory allocator + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + This memory allocator is for allocating small memory blocks efficiently + in terms of memory overhead and execution speed. The allocated blocks + cannot be freed individually, only all at once. There can be multiple + allocators, though. +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ +#include <stdlib.h> +#include <string.h> + + + +/* Returns a new memory allocator or NULL if out of memory. */ +tre_mem_t +tre_mem_new_impl(int provided, void *provided_block) +{ + tre_mem_t mem; + if (provided) + { + mem = provided_block; + memset(mem, 0, sizeof(*mem)); + } + else + mem = xcalloc(1, sizeof(*mem)); + if (mem == NULL) + return NULL; + return mem; +} + + +/* Frees the memory allocator and all memory allocated with it. */ +void +tre_mem_destroy(tre_mem_t mem) +{ + tre_list_t *tmp, *l = mem->blocks; + + while (l != NULL) + { + xfree(l->data); + tmp = l->next; + xfree(l); + l = tmp; + } + xfree(mem); +} + + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. */ +void * +tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block, + int zero, size_t size) +{ + void *ptr; + + if (mem->failed) + { + DPRINT(("tre_mem_alloc: oops, called after failure?!\n")); + return NULL; + } + +#ifdef MALLOC_DEBUGGING + if (!provided) + { + ptr = xmalloc(1); + if (ptr == NULL) + { + DPRINT(("tre_mem_alloc: xmalloc forced failure\n")); + mem->failed = 1; + return NULL; + } + xfree(ptr); + } +#endif /* MALLOC_DEBUGGING */ + + if (mem->n < size) + { + /* We need more memory than is available in the current block. + Allocate a new block. */ + tre_list_t *l; + if (provided) + { + DPRINT(("tre_mem_alloc: using provided block\n")); + if (provided_block == NULL) + { + DPRINT(("tre_mem_alloc: provided block was NULL\n")); + mem->failed = 1; + return NULL; + } + mem->ptr = provided_block; + mem->n = TRE_MEM_BLOCK_SIZE; + } + else + { + int block_size; + if (size * 8 > TRE_MEM_BLOCK_SIZE) + block_size = size * 8; + else + block_size = TRE_MEM_BLOCK_SIZE; + DPRINT(("tre_mem_alloc: allocating new %d byte block\n", + block_size)); + l = xmalloc(sizeof(*l)); + if (l == NULL) + { + mem->failed = 1; + return NULL; + } + l->data = xmalloc(block_size); + if (l->data == NULL) + { + xfree(l); + mem->failed = 1; + return NULL; + } + l->next = NULL; + if (mem->current != NULL) + mem->current->next = l; + if (mem->blocks == NULL) + mem->blocks = l; + mem->current = l; + mem->ptr = l->data; + mem->n = block_size; + } + } + + /* Make sure the next pointer will be aligned. */ + size += ALIGN(mem->ptr + size, long); + + /* Allocate from current block. */ + ptr = mem->ptr; + mem->ptr += size; + mem->n -= size; + + /* Set to zero if needed. */ + if (zero) + memset(ptr, 0, size); + + return ptr; +} + +/* EOF */ +/* + tre-parse.c - Regexp parser + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + This parser is just a simple recursive descent parser for POSIX.2 + regexps. The parser supports both the obsolete default syntax and + the "extended" syntax, and some nonstandard extensions. +*/ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ +#include <string.h> +#include <assert.h> +#include <limits.h> + + + +/* Characters with special meanings in regexp syntax. */ +#define CHAR_PIPE L'|' +#define CHAR_LPAREN L'(' +#define CHAR_RPAREN L')' +#define CHAR_LBRACE L'{' +#define CHAR_RBRACE L'}' +#define CHAR_LBRACKET L'[' +#define CHAR_RBRACKET L']' +#define CHAR_MINUS L'-' +#define CHAR_STAR L'*' +#define CHAR_QUESTIONMARK L'?' +#define CHAR_PLUS L'+' +#define CHAR_PERIOD L'.' +#define CHAR_COLON L':' +#define CHAR_EQUAL L'=' +#define CHAR_COMMA L',' +#define CHAR_CARET L'^' +#define CHAR_DOLLAR L'$' +#define CHAR_BACKSLASH L'\\' +#define CHAR_HASH L'#' +#define CHAR_TILDE L'~' + + +/* Some macros for expanding \w, \s, etc. */ +static const struct tre_macro_struct { + const char c; + const char *expansion; +} tre_macros[] = + { {'t', "\t"}, {'n', "\n"}, {'r', "\r"}, + {'f', "\f"}, {'a', "\a"}, {'e', "\033"}, + {'w', "[[:alnum:]_]"}, {'W', "[^[:alnum:]_]"}, {'s', "[[:space:]]"}, + {'S', "[^[:space:]]"}, {'d', "[[:digit:]]"}, {'D', "[^[:digit:]]"}, + { 0, NULL } + }; + + +/* Expands a macro delimited by `regex' and `regex_end' to `buf', which + must have at least `len' items. Sets buf[0] to zero if the there + is no match in `tre_macros'. */ +static void +tre_expand_macro(const tre_char_t *regex, const tre_char_t *regex_end, + tre_char_t *buf, size_t buf_len) +{ + int i; + + buf[0] = 0; + if (regex >= regex_end) + return; + + for (i = 0; tre_macros[i].expansion; i++) + { + if (tre_macros[i].c == *regex) + { + unsigned int j; + DPRINT(("Expanding macro '%c' => '%s'\n", + tre_macros[i].c, tre_macros[i].expansion)); + for (j = 0; tre_macros[i].expansion[j] && j < buf_len; j++) + buf[j] = tre_macros[i].expansion[j]; + buf[j] = 0; + break; + } + } +} + +static reg_errcode_t +tre_new_item(tre_mem_t mem, int min, int max, int *i, int *max_i, + tre_ast_node_t ***items) +{ + reg_errcode_t status; + tre_ast_node_t **array = *items; + /* Allocate more space if necessary. */ + if (*i >= *max_i) + { + tre_ast_node_t **new_items; + DPRINT(("out of array space, i = %d\n", *i)); + /* If the array is already 1024 items large, give up -- there's + probably an error in the regexp (e.g. not a '\0' terminated + string and missing ']') */ + if (*max_i > 1024) + return REG_ESPACE; + *max_i *= 2; + new_items = xrealloc(array, sizeof(*items) * *max_i); + if (new_items == NULL) + return REG_ESPACE; + *items = array = new_items; + } + array[*i] = tre_ast_new_literal(mem, min, max, -1); + status = array[*i] == NULL ? REG_ESPACE : REG_OK; + (*i)++; + return status; +} + + +/* Expands a character class to character ranges. */ +static reg_errcode_t +tre_expand_ctype(tre_mem_t mem, tre_ctype_t class, tre_ast_node_t ***items, + int *i, int *max_i, int cflags) +{ + reg_errcode_t status = REG_OK; + tre_cint_t c; + int j, min = -1, max = 0; + assert(TRE_MB_CUR_MAX == 1); + + DPRINT((" expanding class to character ranges\n")); + for (j = 0; (j < 256) && (status == REG_OK); j++) + { + c = j; + if (tre_isctype(c, class) + || ((cflags & REG_ICASE) + && (tre_isctype(tre_tolower(c), class) + || tre_isctype(tre_toupper(c), class)))) +{ + if (min < 0) + min = c; + max = c; + } + else if (min >= 0) + { + DPRINT((" range %c (%d) to %c (%d)\n", min, min, max, max)); + status = tre_new_item(mem, min, max, i, max_i, items); + min = -1; + } + } + if (min >= 0 && status == REG_OK) + status = tre_new_item(mem, min, max, i, max_i, items); + return status; +} + + +static int +tre_compare_items(const void *a, const void *b) +{ + const tre_ast_node_t *node_a = *(tre_ast_node_t * const *)a; + const tre_ast_node_t *node_b = *(tre_ast_node_t * const *)b; + tre_literal_t *l_a = node_a->obj, *l_b = node_b->obj; + int a_min = l_a->code_min, b_min = l_b->code_min; + + if (a_min < b_min) + return -1; + else if (a_min > b_min) + return 1; + else + return 0; +} + +#ifndef TRE_USE_SYSTEM_WCTYPE + +/* isalnum() and the rest may be macros, so wrap them to functions. */ +int tre_isalnum_func(tre_cint_t c) { return tre_isalnum(c); } +int tre_isalpha_func(tre_cint_t c) { return tre_isalpha(c); } + +#ifdef tre_isascii +int tre_isascii_func(tre_cint_t c) { return tre_isascii(c); } +#else /* !tre_isascii */ +int tre_isascii_func(tre_cint_t c) { return !(c >> 7); } +#endif /* !tre_isascii */ + +#ifdef tre_isblank +int tre_isblank_func(tre_cint_t c) { return tre_isblank(c); } +#else /* !tre_isblank */ +int tre_isblank_func(tre_cint_t c) { return ((c == ' ') || (c == '\t')); } +#endif /* !tre_isblank */ + +int tre_iscntrl_func(tre_cint_t c) { return tre_iscntrl(c); } +int tre_isdigit_func(tre_cint_t c) { return tre_isdigit(c); } +int tre_isgraph_func(tre_cint_t c) { return tre_isgraph(c); } +int tre_islower_func(tre_cint_t c) { return tre_islower(c); } +int tre_isprint_func(tre_cint_t c) { return tre_isprint(c); } +int tre_ispunct_func(tre_cint_t c) { return tre_ispunct(c); } +int tre_isspace_func(tre_cint_t c) { return tre_isspace(c); } +int tre_isupper_func(tre_cint_t c) { return tre_isupper(c); } +int tre_isxdigit_func(tre_cint_t c) { return tre_isxdigit(c); } + +struct { + char *name; + int (*func)(tre_cint_t); +} tre_ctype_map[] = { + { "alnum", &tre_isalnum_func }, + { "alpha", &tre_isalpha_func }, +#ifdef tre_isascii + { "ascii", &tre_isascii_func }, +#endif /* tre_isascii */ +#ifdef tre_isblank + { "blank", &tre_isblank_func }, +#endif /* tre_isblank */ + { "cntrl", &tre_iscntrl_func }, + { "digit", &tre_isdigit_func }, + { "graph", &tre_isgraph_func }, + { "lower", &tre_islower_func }, + { "print", &tre_isprint_func }, + { "punct", &tre_ispunct_func }, + { "space", &tre_isspace_func }, + { "upper", &tre_isupper_func }, + { "xdigit", &tre_isxdigit_func }, + { NULL, NULL} +}; + +tre_ctype_t tre_ctype(const char *name) +{ + int i; + for (i = 0; tre_ctype_map[i].name != NULL; i++) + { + if (strcmp(name, tre_ctype_map[i].name) == 0) + return tre_ctype_map[i].func; + } + return (tre_ctype_t)0; +} +#endif /* !TRE_USE_SYSTEM_WCTYPE */ + +/* Maximum number of character classes that can occur in a negated bracket + expression. */ +#define MAX_NEG_CLASSES 64 + +/* Maximum length of character class names. */ +#define MAX_CLASS_NAME + +#define REST(re) (int)(ctx->re_end - (re)), (re) + +static reg_errcode_t +tre_parse_bracket_items(tre_parse_ctx_t *ctx, int negate, + tre_ctype_t neg_classes[], int *num_neg_classes, + tre_ast_node_t ***items, int *num_items, + int *items_size) +{ + const tre_char_t *re = ctx->re; + reg_errcode_t status = REG_OK; + tre_ctype_t class = (tre_ctype_t)0; + int i = *num_items; + int max_i = *items_size; + int skip; + + /* Build an array of the items in the bracket expression. */ + while (status == REG_OK) + { + skip = 0; + if (re == ctx->re_end) + { + status = REG_EBRACK; + } + else if (*re == CHAR_RBRACKET && re > ctx->re) + { + DPRINT(("tre_parse_bracket: done: '%.*" STRF "'\n", REST(re))); + re++; + break; + } + else + { + tre_cint_t min = 0, max = 0; + + class = (tre_ctype_t)0; + if (re + 2 < ctx->re_end + && *(re + 1) == CHAR_MINUS && *(re + 2) != CHAR_RBRACKET) + { + DPRINT(("tre_parse_bracket: range: '%.*" STRF "'\n", REST(re))); + min = *re; + max = *(re + 2); + re += 3; + /* XXX - Should use collation order instead of encoding values + in character ranges. */ + if (min > max) + status = REG_ERANGE; + } + else if (re + 1 < ctx->re_end + && *re == CHAR_LBRACKET && *(re + 1) == CHAR_PERIOD) + status = REG_ECOLLATE; + else if (re + 1 < ctx->re_end + && *re == CHAR_LBRACKET && *(re + 1) == CHAR_EQUAL) + status = REG_ECOLLATE; + else if (re + 1 < ctx->re_end + && *re == CHAR_LBRACKET && *(re + 1) == CHAR_COLON) + { + char tmp_str[64]; + const tre_char_t *endptr = re + 2; + int len; + DPRINT(("tre_parse_bracket: class: '%.*" STRF "'\n", REST(re))); + while (endptr < ctx->re_end && *endptr != CHAR_COLON) + endptr++; + if (endptr != ctx->re_end) + { + len = MIN(endptr - re - 2, 63); +#ifdef TRE_WCHAR + { + tre_char_t tmp_wcs[64]; + wcsncpy(tmp_wcs, re + 2, (size_t)len); + tmp_wcs[len] = L'\0'; +#if defined HAVE_WCSRTOMBS + { + mbstate_t state; + const tre_char_t *src = tmp_wcs; + memset(&state, '\0', sizeof(state)); + len = wcsrtombs(tmp_str, &src, sizeof(tmp_str), &state); + } +#elif defined HAVE_WCSTOMBS + len = wcstombs(tmp_str, tmp_wcs, 63); +#endif /* defined HAVE_WCSTOMBS */ + } +#else /* !TRE_WCHAR */ + strncpy(tmp_str, (const char*)re + 2, len); +#endif /* !TRE_WCHAR */ + tmp_str[len] = '\0'; + DPRINT((" class name: %s\n", tmp_str)); + class = tre_ctype(tmp_str); + if (!class) + status = REG_ECTYPE; + /* Optimize character classes for 8 bit character sets. */ + if (status == REG_OK && TRE_MB_CUR_MAX == 1) + { + status = tre_expand_ctype(ctx->mem, class, items, + &i, &max_i, ctx->cflags); + class = (tre_ctype_t)0; + skip = 1; + } + re = endptr + 2; + } + else + status = REG_ECTYPE; + min = 0; + max = TRE_CHAR_MAX; + } + else + { + DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re))); + if (*re == CHAR_MINUS && *(re + 1) != CHAR_RBRACKET + && ctx->re != re) + /* Two ranges are not allowed to share and endpoint. */ + status = REG_ERANGE; + min = max = *re++; + } + + if (status != REG_OK) + break; + + if (class && negate) + if (*num_neg_classes >= MAX_NEG_CLASSES) + status = REG_ESPACE; + else + neg_classes[(*num_neg_classes)++] = class; + else if (!skip) + { + status = tre_new_item(ctx->mem, min, max, &i, &max_i, items); + if (status != REG_OK) + break; + ((tre_literal_t*)((*items)[i-1])->obj)->u.class = class; + } + + /* Add opposite-case counterpoints if REG_ICASE is present. + This is broken if there are more than two "same" characters. */ + if (ctx->cflags & REG_ICASE && !class && status == REG_OK && !skip) + { + tre_cint_t cmin, ccurr; + + DPRINT(("adding opposite-case counterpoints\n")); + while (min <= max) + { + if (tre_islower(min)) + { + cmin = ccurr = tre_toupper(min++); + while (tre_islower(min) && tre_toupper(min) == ccurr + 1 + && min <= max) + ccurr = tre_toupper(min++); + status = tre_new_item(ctx->mem, cmin, ccurr, + &i, &max_i, items); + } + else if (tre_isupper(min)) + { + cmin = ccurr = tre_tolower(min++); + while (tre_isupper(min) && tre_tolower(min) == ccurr + 1 + && min <= max) + ccurr = tre_tolower(min++); + status = tre_new_item(ctx->mem, cmin, ccurr, + &i, &max_i, items); + } + else min++; + if (status != REG_OK) + break; + } + if (status != REG_OK) + break; + } + } + } + *num_items = i; + *items_size = max_i; + ctx->re = re; + return status; +} + +static reg_errcode_t +tre_parse_bracket(tre_parse_ctx_t *ctx, tre_ast_node_t **result) +{ + tre_ast_node_t *node = NULL; + int negate = 0; + reg_errcode_t status = REG_OK; + tre_ast_node_t **items, *u, *n; + int i = 0, j, max_i = 32, curr_max, curr_min; + tre_ctype_t neg_classes[MAX_NEG_CLASSES]; + int num_neg_classes = 0; + + /* Start off with an array of `max_i' elements. */ + items = xmalloc(sizeof(*items) * max_i); + if (items == NULL) + return REG_ESPACE; + + if (*ctx->re == CHAR_CARET) + { + DPRINT(("tre_parse_bracket: negate: '%.*" STRF "'\n", REST(ctx->re))); + negate = 1; + ctx->re++; + } + + status = tre_parse_bracket_items(ctx, negate, neg_classes, &num_neg_classes, + &items, &i, &max_i); + + if (status != REG_OK) + goto parse_bracket_done; + + /* Sort the array if we need to negate it. */ + if (negate) + qsort(items, (unsigned)i, sizeof(*items), tre_compare_items); + + curr_max = curr_min = 0; + /* Build a union of the items in the array, negated if necessary. */ + for (j = 0; j < i && status == REG_OK; j++) + { + int min, max; + tre_literal_t *l = items[j]->obj; + min = l->code_min; + max = l->code_max; + + DPRINT(("item: %d - %d, class %ld, curr_max = %d\n", + (int)l->code_min, (int)l->code_max, (long)l->u.class, curr_max)); + + if (negate) + { + if (min < curr_max) + { + /* Overlap. */ + curr_max = MAX(max + 1, curr_max); + DPRINT(("overlap, curr_max = %d\n", curr_max)); + l = NULL; + } + else + { + /* No overlap. */ + curr_max = min - 1; + if (curr_max >= curr_min) + { + DPRINT(("no overlap\n")); + l->code_min = curr_min; + l->code_max = curr_max; + } + else + { + DPRINT(("no overlap, zero room\n")); + l = NULL; + } + curr_min = curr_max = max + 1; + } + } + + if (l != NULL) + { + int k; + DPRINT(("creating %d - %d\n", (int)l->code_min, (int)l->code_max)); + l->position = ctx->position; + if (num_neg_classes > 0) + { + l->neg_classes = tre_mem_alloc(ctx->mem, + (sizeof(l->neg_classes) + * (num_neg_classes + 1))); + if (l->neg_classes == NULL) + { + status = REG_ESPACE; + break; + } + for (k = 0; k < num_neg_classes; k++) + l->neg_classes[k] = neg_classes[k]; + l->neg_classes[k] = (tre_ctype_t)0; + } + else + l->neg_classes = NULL; + if (node == NULL) + node = items[j]; + else + { + u = tre_ast_new_union(ctx->mem, node, items[j]); + if (u == NULL) + status = REG_ESPACE; + node = u; + } + } + } + + if (status != REG_OK) + goto parse_bracket_done; + + if (negate) + { + int k; + DPRINT(("final: creating %d - %d\n", curr_min, (int)TRE_CHAR_MAX)); + n = tre_ast_new_literal(ctx->mem, curr_min, TRE_CHAR_MAX, ctx->position); + if (n == NULL) + status = REG_ESPACE; + else + { + tre_literal_t *l = n->obj; + if (num_neg_classes > 0) + { + l->neg_classes = tre_mem_alloc(ctx->mem, + (sizeof(l->neg_classes) + * (num_neg_classes + 1))); + if (l->neg_classes == NULL) + { + status = REG_ESPACE; + goto parse_bracket_done; + } + for (k = 0; k < num_neg_classes; k++) + l->neg_classes[k] = neg_classes[k]; + l->neg_classes[k] = (tre_ctype_t)0; + } + else + l->neg_classes = NULL; + if (node == NULL) + node = n; + else + { + u = tre_ast_new_union(ctx->mem, node, n); + if (u == NULL) + status = REG_ESPACE; + node = u; + } + } + } + + if (status != REG_OK) + goto parse_bracket_done; + +#ifdef TRE_DEBUG + tre_ast_print(node); +#endif /* TRE_DEBUG */ + + parse_bracket_done: + xfree(items); + ctx->position++; + *result = node; + return status; +} + + +/* Parses a positive decimal integer. Returns -1 if the string does not + contain a valid number. */ +static int +tre_parse_int(const tre_char_t **regex, const tre_char_t *regex_end) +{ + int num = -1; + const tre_char_t *r = *regex; + while (r < regex_end && *r >= L'0' && *r <= L'9') + { + if (num < 0) + num = 0; + num = num * 10 + *r - L'0'; + r++; + } + *regex = r; + return num; +} + + +static reg_errcode_t +tre_parse_bound(tre_parse_ctx_t *ctx, tre_ast_node_t **result) +{ + int min, max, i; + int cost_ins, cost_del, cost_subst, cost_max; + int limit_ins, limit_del, limit_subst, limit_err; + const tre_char_t *r = ctx->re; + const tre_char_t *start; + int minimal = (ctx->cflags & REG_UNGREEDY) ? 1 : 0; + int approx = 0; + int costs_set = 0; + int counts_set = 0; + + cost_ins = cost_del = cost_subst = cost_max = TRE_PARAM_UNSET; + limit_ins = limit_del = limit_subst = limit_err = TRE_PARAM_UNSET; + + /* Parse number (minimum repetition count). */ + min = -1; + if (r < ctx->re_end && *r >= L'0' && *r <= L'9') { + DPRINT(("tre_parse: min count: '%.*" STRF "'\n", REST(r))); + min = tre_parse_int(&r, ctx->re_end); + } + + /* Parse comma and second number (maximum repetition count). */ + max = min; + if (r < ctx->re_end && *r == CHAR_COMMA) + { + r++; + DPRINT(("tre_parse: max count: '%.*" STRF "'\n", REST(r))); + max = tre_parse_int(&r, ctx->re_end); + } + + /* Check that the repeat counts are sane. */ + if ((max >= 0 && min > max) || max > RE_DUP_MAX) + return REG_BADBR; + + + /* + '{' + optionally followed immediately by a number == minimum repcount + optionally followed by , then a number == maximum repcount + + then a number == maximum insertion count + - then a number == maximum deletion count + # then a number == maximum substitution count + ~ then a number == maximum number of errors + Any of +, -, # or ~ without followed by a number means that + the maximum count/number of errors is infinite. + + An equation of the form + Xi + Yd + Zs < C + can be specified to set costs and the cost limit to a value + different from the default value: + - X is the cost of an insertion + - Y is the cost of a deletion + - Z is the cost of a substitution + - C is the maximum cost + + If no count limit or cost is set for an operation, the operation + is not allowed at all. + */ + + + do { + int done; + start = r; + + /* Parse count limit settings */ + done = 0; + if (!counts_set) + while (r + 1 < ctx->re_end && !done) + { + switch (*r) + { + case CHAR_PLUS: /* Insert limit */ + DPRINT(("tre_parse: ins limit: '%.*" STRF "'\n", REST(r))); + r++; + limit_ins = tre_parse_int(&r, ctx->re_end); + if (limit_ins < 0) + limit_ins = INT_MAX; + counts_set = 1; + break; + case CHAR_MINUS: /* Delete limit */ + DPRINT(("tre_parse: del limit: '%.*" STRF "'\n", REST(r))); + r++; + limit_del = tre_parse_int(&r, ctx->re_end); + if (limit_del < 0) + limit_del = INT_MAX; + counts_set = 1; + break; + case CHAR_HASH: /* Substitute limit */ + DPRINT(("tre_parse: subst limit: '%.*" STRF "'\n", REST(r))); + r++; + limit_subst = tre_parse_int(&r, ctx->re_end); + if (limit_subst < 0) + limit_subst = INT_MAX; + counts_set = 1; + break; + case CHAR_TILDE: /* Maximum number of changes */ + DPRINT(("tre_parse: count limit: '%.*" STRF "'\n", REST(r))); + r++; + limit_err = tre_parse_int(&r, ctx->re_end); + if (limit_err < 0) + limit_err = INT_MAX; + approx = 1; + break; + case CHAR_COMMA: + r++; + break; + case L' ': + r++; + break; + case L'}': + done = 1; + break; + default: + done = 1; + break; + } + } + + /* Parse cost restriction equation. */ + done = 0; + if (!costs_set) + while (r + 1 < ctx->re_end && !done) + { + switch (*r) + { + case CHAR_PLUS: + case L' ': + r++; + break; + case L'<': + DPRINT(("tre_parse: max cost: '%.*" STRF "'\n", REST(r))); + r++; + while (*r == L' ') + r++; + cost_max = tre_parse_int(&r, ctx->re_end); + if (cost_max < 0) + cost_max = INT_MAX; + else + cost_max--; + approx = 1; + break; + case CHAR_COMMA: + r++; + done = 1; + break; + default: + if (*r >= L'0' && *r <= L'9') + { +#ifdef TRE_DEBUG + const tre_char_t *sr = r; +#endif /* TRE_DEBUG */ + int cost = tre_parse_int(&r, ctx->re_end); + /* XXX - make sure r is not past end. */ + switch (*r) + { + case L'i': /* Insert cost */ + DPRINT(("tre_parse: ins cost: '%.*" STRF "'\n", + REST(sr))); + r++; + cost_ins = cost; + costs_set = 1; + break; + case L'd': /* Delete cost */ + DPRINT(("tre_parse: del cost: '%.*" STRF "'\n", + REST(sr))); + r++; + cost_del = cost; + costs_set = 1; + break; + case L's': /* Substitute cost */ + DPRINT(("tre_parse: subst cost: '%.*" STRF "'\n", + REST(sr))); + r++; + cost_subst = cost; + costs_set = 1; + break; + default: + return REG_BADBR; + } + } + else + { + done = 1; + break; + } + } + } + } while (start != r); + + /* Missing }. */ + if (r >= ctx->re_end) + return REG_EBRACE; + + /* Empty contents of {}. */ + if (r == ctx->re) + return REG_BADBR; + + /* Parse the ending '}' or '\}'.*/ + if (ctx->cflags & REG_EXTENDED) + { + if (r >= ctx->re_end || *r != CHAR_RBRACE) + return REG_BADBR; + r++; + } + else + { + if (r + 1 >= ctx->re_end + || *r != CHAR_BACKSLASH + || *(r + 1) != CHAR_RBRACE) + return REG_BADBR; + r += 2; + } + + + /* Parse trailing '?' marking minimal repetition. */ + if (r < ctx->re_end) + { + if (*r == CHAR_QUESTIONMARK) + { + minimal = !(ctx->cflags & REG_UNGREEDY); + r++; + } + else if (*r == CHAR_STAR || *r == CHAR_PLUS) + { + /* These are reserved for future extensions. */ + return REG_BADRPT; + } + } + + /* Create the AST node(s). */ + if (min == 0 && max == 0) + { + *result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (*result == NULL) + return REG_ESPACE; + } + else + { + if (min < 0 && max < 0) + /* Only approximate parameters set, no repetitions. */ + min = max = 1; + + *result = tre_ast_new_iter(ctx->mem, *result, min, max, minimal); + if (!*result) + return REG_ESPACE; + + /* If approximate matching parameters are set, add them to the + iteration node. */ + if (approx || costs_set || counts_set) + { + int *params; + tre_iteration_t *iter = (*result)->obj; + + if (costs_set || counts_set) + { + if (limit_ins == TRE_PARAM_UNSET) + { + if (cost_ins == TRE_PARAM_UNSET) + limit_ins = 0; + else + limit_ins = INT_MAX; + } + + if (limit_del == TRE_PARAM_UNSET) + { + if (cost_del == TRE_PARAM_UNSET) + limit_del = 0; + else + limit_del = INT_MAX; + } + + if (limit_subst == TRE_PARAM_UNSET) + { + if (cost_subst == TRE_PARAM_UNSET) + limit_subst = 0; + else + limit_subst = INT_MAX; + } + } + + if (cost_max == TRE_PARAM_UNSET) + cost_max = INT_MAX; + if (limit_err == TRE_PARAM_UNSET) + limit_err = INT_MAX; + + ctx->have_approx = 1; + params = tre_mem_alloc(ctx->mem, sizeof(*params) * TRE_PARAM_LAST); + if (!params) + return REG_ESPACE; + for (i = 0; i < TRE_PARAM_LAST; i++) + params[i] = TRE_PARAM_UNSET; + params[TRE_PARAM_COST_INS] = cost_ins; + params[TRE_PARAM_COST_DEL] = cost_del; + params[TRE_PARAM_COST_SUBST] = cost_subst; + params[TRE_PARAM_COST_MAX] = cost_max; + params[TRE_PARAM_MAX_INS] = limit_ins; + params[TRE_PARAM_MAX_DEL] = limit_del; + params[TRE_PARAM_MAX_SUBST] = limit_subst; + params[TRE_PARAM_MAX_ERR] = limit_err; + iter->params = params; + } + } + + DPRINT(("tre_parse_bound: min %d, max %d, costs [%d,%d,%d, total %d], " + "limits [%d,%d,%d, total %d]\n", + min, max, cost_ins, cost_del, cost_subst, cost_max, + limit_ins, limit_del, limit_subst, limit_err)); + + + ctx->re = r; + return REG_OK; +} + +typedef enum { + PARSE_RE = 0, + PARSE_ATOM, + PARSE_MARK_FOR_SUBMATCH, + PARSE_BRANCH, + PARSE_PIECE, + PARSE_CATENATION, + PARSE_POST_CATENATION, + PARSE_UNION, + PARSE_POST_UNION, + PARSE_POSTFIX, + PARSE_RESTORE_CFLAGS +} tre_parse_re_stack_symbol_t; + + +reg_errcode_t +tre_parse(tre_parse_ctx_t *ctx) +{ + tre_ast_node_t *result = NULL; + tre_parse_re_stack_symbol_t symbol; + reg_errcode_t status = REG_OK; + tre_stack_t *stack = ctx->stack; + int bottom = tre_stack_num_objects(stack); + int depth = 0; + int temporary_cflags = 0; + + DPRINT(("tre_parse: parsing '%.*" STRF "', len = %d\n", + ctx->len, ctx->re, ctx->len)); + + if (!ctx->nofirstsub) + { + STACK_PUSH(stack, int, ctx->submatch_id); + STACK_PUSH(stack, int, PARSE_MARK_FOR_SUBMATCH); + ctx->submatch_id++; + } + STACK_PUSH(stack, int, PARSE_RE); + ctx->re_start = ctx->re; + ctx->re_end = ctx->re + ctx->len; + + + /* The following is basically just a recursive descent parser. I use + an explicit stack instead of recursive functions mostly because of + two reasons: compatibility with systems which have an overflowable + call stack, and efficiency (both in lines of code and speed). */ + while (tre_stack_num_objects(stack) > bottom && status == REG_OK) + { + if (status != REG_OK) + break; + symbol = tre_stack_pop_int(stack); + switch (symbol) + { + case PARSE_RE: + /* Parse a full regexp. A regexp is one or more branches, + separated by the union operator `|'. */ +#ifdef REG_LITERAL + if (!(ctx->cflags & REG_LITERAL) + && ctx->cflags & REG_EXTENDED) +#endif /* REG_LITERAL */ + STACK_PUSHX(stack, int, PARSE_UNION); + STACK_PUSHX(stack, int, PARSE_BRANCH); + break; + + case PARSE_BRANCH: + /* Parse a branch. A branch is one or more pieces, concatenated. + A piece is an atom possibly followed by a postfix operator. */ + STACK_PUSHX(stack, int, PARSE_CATENATION); + STACK_PUSHX(stack, int, PARSE_PIECE); + break; + + case PARSE_PIECE: + /* Parse a piece. A piece is an atom possibly followed by one + or more postfix operators. */ +#ifdef REG_LITERAL + if (!(ctx->cflags & REG_LITERAL)) +#endif /* REG_LITERAL */ + STACK_PUSHX(stack, int, PARSE_POSTFIX); + STACK_PUSHX(stack, int, PARSE_ATOM); + break; + + case PARSE_CATENATION: + /* If the expression has not ended, parse another piece. */ + { + tre_char_t c; + if (ctx->re >= ctx->re_end) + break; + c = *ctx->re; +#ifdef REG_LITERAL + if (!(ctx->cflags & REG_LITERAL)) + { +#endif /* REG_LITERAL */ + if (ctx->cflags & REG_EXTENDED && c == CHAR_PIPE) + break; + if ((ctx->cflags & REG_EXTENDED + && c == CHAR_RPAREN && depth > 0) + || (!(ctx->cflags & REG_EXTENDED) + && (c == CHAR_BACKSLASH + && *(ctx->re + 1) == CHAR_RPAREN))) + { + if (!(ctx->cflags & REG_EXTENDED) && depth == 0) + status = REG_EPAREN; + DPRINT(("tre_parse: group end: '%.*" STRF "'\n", + REST(ctx->re))); + depth--; + if (!(ctx->cflags & REG_EXTENDED)) + ctx->re += 2; + break; + } +#ifdef REG_LITERAL + } +#endif /* REG_LITERAL */ + +#ifdef REG_RIGHT_ASSOC + if (ctx->cflags & REG_RIGHT_ASSOC) + { + /* Right associative concatenation. */ + STACK_PUSHX(stack, voidptr, result); + STACK_PUSHX(stack, int, PARSE_POST_CATENATION); + STACK_PUSHX(stack, int, PARSE_CATENATION); + STACK_PUSHX(stack, int, PARSE_PIECE); + } + else +#endif /* REG_RIGHT_ASSOC */ + { + /* Default case, left associative concatenation. */ + STACK_PUSHX(stack, int, PARSE_CATENATION); + STACK_PUSHX(stack, voidptr, result); + STACK_PUSHX(stack, int, PARSE_POST_CATENATION); + STACK_PUSHX(stack, int, PARSE_PIECE); + } + break; + } + + case PARSE_POST_CATENATION: + { + tre_ast_node_t *tree = tre_stack_pop_voidptr(stack); + tre_ast_node_t *tmp_node; + tmp_node = tre_ast_new_catenation(ctx->mem, tree, result); + if (!tmp_node) + return REG_ESPACE; + result = tmp_node; + break; + } + + case PARSE_UNION: + if (ctx->re >= ctx->re_end) + break; +#ifdef REG_LITERAL + if (ctx->cflags & REG_LITERAL) + break; +#endif /* REG_LITERAL */ + switch (*ctx->re) + { + case CHAR_PIPE: + DPRINT(("tre_parse: union: '%.*" STRF "'\n", + REST(ctx->re))); + STACK_PUSHX(stack, int, PARSE_UNION); + STACK_PUSHX(stack, voidptr, result); + STACK_PUSHX(stack, int, PARSE_POST_UNION); + STACK_PUSHX(stack, int, PARSE_BRANCH); + ctx->re++; + break; + + case CHAR_RPAREN: + ctx->re++; + break; + + default: + break; + } + break; + + case PARSE_POST_UNION: + { + tre_ast_node_t *tmp_node; + tre_ast_node_t *tree = tre_stack_pop_voidptr(stack); + tmp_node = tre_ast_new_union(ctx->mem, tree, result); + if (!tmp_node) + return REG_ESPACE; + result = tmp_node; + break; + } + + case PARSE_POSTFIX: + /* Parse postfix operators. */ + if (ctx->re >= ctx->re_end) + break; +#ifdef REG_LITERAL + if (ctx->cflags & REG_LITERAL) + break; +#endif /* REG_LITERAL */ + switch (*ctx->re) + { + case CHAR_PLUS: + case CHAR_QUESTIONMARK: + if (!(ctx->cflags & REG_EXTENDED)) + break; + /*FALLTHROUGH*/ + case CHAR_STAR: + { + tre_ast_node_t *tmp_node; + int minimal = (ctx->cflags & REG_UNGREEDY) ? 1 : 0; + int rep_min = 0; + int rep_max = -1; +#ifdef TRE_DEBUG + const tre_char_t *tmp_re; +#endif + + if (*ctx->re == CHAR_PLUS) + rep_min = 1; + if (*ctx->re == CHAR_QUESTIONMARK) + rep_max = 1; +#ifdef TRE_DEBUG + tmp_re = ctx->re; +#endif + + if (ctx->re + 1 < ctx->re_end) + { + if (*(ctx->re + 1) == CHAR_QUESTIONMARK) + { + minimal = !(ctx->cflags & REG_UNGREEDY); + ctx->re++; + } + else if (*(ctx->re + 1) == CHAR_STAR + || *(ctx->re + 1) == CHAR_PLUS) + { + /* These are reserved for future extensions. */ + return REG_BADRPT; + } + } + + DPRINT(("tre_parse: %s star: '%.*" STRF "'\n", + minimal ? " minimal" : "greedy", REST(tmp_re))); + ctx->re++; + tmp_node = tre_ast_new_iter(ctx->mem, result, rep_min, rep_max, + minimal); + if (tmp_node == NULL) + return REG_ESPACE; + result = tmp_node; + STACK_PUSHX(stack, int, PARSE_POSTFIX); + } + break; + + case CHAR_BACKSLASH: + /* "\{" is special without REG_EXTENDED */ + if (!(ctx->cflags & REG_EXTENDED) + && ctx->re + 1 < ctx->re_end + && *(ctx->re + 1) == CHAR_LBRACE) + { + ctx->re++; + goto parse_brace; + } + else + break; + + case CHAR_LBRACE: + /* "{" is literal without REG_EXTENDED */ + if (!(ctx->cflags & REG_EXTENDED)) + break; + + parse_brace: + DPRINT(("tre_parse: bound: '%.*" STRF "'\n", + REST(ctx->re))); + ctx->re++; + + status = tre_parse_bound(ctx, &result); + if (status != REG_OK) + return status; + STACK_PUSHX(stack, int, PARSE_POSTFIX); + break; + } + break; + + case PARSE_ATOM: + /* Parse an atom. An atom is a regular expression enclosed in `()', + an empty set of `()', a bracket expression, `.', `^', `$', + a `\' followed by a character, or a single character. */ + + /* End of regexp? (empty string). */ + if (ctx->re >= ctx->re_end) + goto parse_literal; + +#ifdef REG_LITERAL + if (ctx->cflags & REG_LITERAL) + goto parse_literal; +#endif /* REG_LITERAL */ + + switch (*ctx->re) + { + case CHAR_LPAREN: /* parenthesized subexpression */ + + /* Handle "(?...)" extensions. They work in a way similar + to Perls corresponding extensions. */ + if (ctx->cflags & REG_EXTENDED + && *(ctx->re + 1) == CHAR_QUESTIONMARK) + { + int new_cflags = ctx->cflags; + int bit = 1; + DPRINT(("tre_parse: extension: '%.*" STRF "\n", + REST(ctx->re))); + ctx->re += 2; + while (/*CONSTCOND*/1) + { + if (*ctx->re == L'i') + { + DPRINT(("tre_parse: icase: '%.*" STRF "\n", + REST(ctx->re))); + if (bit) + new_cflags |= REG_ICASE; + else + new_cflags &= ~REG_ICASE; + ctx->re++; + } + else if (*ctx->re == L'n') + { + DPRINT(("tre_parse: newline: '%.*" STRF "\n", + REST(ctx->re))); + if (bit) + new_cflags |= REG_NEWLINE; + else + new_cflags &= ~REG_NEWLINE; + ctx->re++; + } +#ifdef REG_RIGHT_ASSOC + else if (*ctx->re == L'r') + { + DPRINT(("tre_parse: right assoc: '%.*" STRF "\n", + REST(ctx->re))); + if (bit) + new_cflags |= REG_RIGHT_ASSOC; + else + new_cflags &= ~REG_RIGHT_ASSOC; + ctx->re++; + } +#endif /* REG_RIGHT_ASSOC */ +#ifdef REG_UNGREEDY + else if (*ctx->re == L'U') + { + DPRINT(("tre_parse: ungreedy: '%.*" STRF "\n", + REST(ctx->re))); + if (bit) + new_cflags |= REG_UNGREEDY; + else + new_cflags &= ~REG_UNGREEDY; + ctx->re++; + } +#endif /* REG_UNGREEDY */ + else if (*ctx->re == CHAR_MINUS) + { + DPRINT(("tre_parse: turn off: '%.*" STRF "\n", + REST(ctx->re))); + ctx->re++; + bit = 0; + } + else if (*ctx->re == CHAR_COLON) + { + DPRINT(("tre_parse: no group: '%.*" STRF "\n", + REST(ctx->re))); + ctx->re++; + depth++; + break; + } + else if (*ctx->re == CHAR_HASH) + { + DPRINT(("tre_parse: comment: '%.*" STRF "\n", + REST(ctx->re))); + /* A comment can contain any character except a + right parenthesis */ + while (*ctx->re != CHAR_RPAREN + && ctx->re < ctx->re_end) + ctx->re++; + if (*ctx->re == CHAR_RPAREN && ctx->re < ctx->re_end) + { + ctx->re++; + break; + } + else + return REG_BADPAT; + } + else if (*ctx->re == CHAR_RPAREN) + { + ctx->re++; + break; + } + else + return REG_BADPAT; + } + + /* Turn on the cflags changes for the rest of the + enclosing group. */ + STACK_PUSHX(stack, int, ctx->cflags); + STACK_PUSHX(stack, int, PARSE_RESTORE_CFLAGS); + STACK_PUSHX(stack, int, PARSE_RE); + ctx->cflags = new_cflags; + break; + } + + if (ctx->cflags & REG_EXTENDED + || (ctx->re > ctx->re_start + && *(ctx->re - 1) == CHAR_BACKSLASH)) + { + depth++; + if (ctx->re + 2 < ctx->re_end + && *(ctx->re + 1) == CHAR_QUESTIONMARK + && *(ctx->re + 2) == CHAR_COLON) + { + DPRINT(("tre_parse: group begin: '%.*" STRF + "', no submatch\n", REST(ctx->re))); + /* Don't mark for submatching. */ + ctx->re += 3; + STACK_PUSHX(stack, int, PARSE_RE); + } + else + { + DPRINT(("tre_parse: group begin: '%.*" STRF + "', submatch %d\n", REST(ctx->re), + ctx->submatch_id)); + ctx->re++; + /* First parse a whole RE, then mark the resulting tree + for submatching. */ + STACK_PUSHX(stack, int, ctx->submatch_id); + STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH); + STACK_PUSHX(stack, int, PARSE_RE); + ctx->submatch_id++; + } + } + else + goto parse_literal; + break; + + case CHAR_RPAREN: /* end of current subexpression */ + if ((ctx->cflags & REG_EXTENDED && depth > 0) + || (ctx->re > ctx->re_start + && *(ctx->re - 1) == CHAR_BACKSLASH)) + { + DPRINT(("tre_parse: empty: '%.*" STRF "'\n", + REST(ctx->re))); + /* We were expecting an atom, but instead the current + subexpression was closed. POSIX leaves the meaning of + this to be implementation-defined. We interpret this as + an empty expression (which matches an empty string). */ + result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (result == NULL) + return REG_ESPACE; + if (!(ctx->cflags & REG_EXTENDED)) + ctx->re--; + } + else + goto parse_literal; + break; + + case CHAR_LBRACKET: /* bracket expression */ + DPRINT(("tre_parse: bracket: '%.*" STRF "'\n", + REST(ctx->re))); + ctx->re++; + status = tre_parse_bracket(ctx, &result); + if (status != REG_OK) + return status; + break; + + case CHAR_BACKSLASH: + /* If this is "\(" or "\)" chew off the backslash and + try again. */ + if (!(ctx->cflags & REG_EXTENDED) + && ctx->re + 1 < ctx->re_end + && (*(ctx->re + 1) == CHAR_LPAREN + || *(ctx->re + 1) == CHAR_RPAREN)) + { + ctx->re++; + STACK_PUSHX(stack, int, PARSE_ATOM); + break; + } + + /* If a macro is used, parse the expanded macro recursively. */ + { + tre_char_t buf[64]; + tre_expand_macro(ctx->re + 1, ctx->re_end, + buf, elementsof(buf)); + if (buf[0] != 0) + { + tre_parse_ctx_t subctx; + memcpy(&subctx, ctx, sizeof(subctx)); + subctx.re = buf; + subctx.len = tre_strlen(buf); + subctx.nofirstsub = 1; + status = tre_parse(&subctx); + if (status != REG_OK) + return status; + ctx->re += 2; + ctx->position = subctx.position; + result = subctx.result; + break; + } + } + + if (ctx->re + 1 >= ctx->re_end) + /* Trailing backslash. */ + return REG_EESCAPE; + +#ifdef REG_LITERAL + if (*(ctx->re + 1) == L'Q') + { + DPRINT(("tre_parse: tmp literal: '%.*" STRF "'\n", + REST(ctx->re))); + ctx->cflags |= REG_LITERAL; + temporary_cflags |= REG_LITERAL; + ctx->re += 2; + STACK_PUSHX(stack, int, PARSE_ATOM); + break; + } +#endif /* REG_LITERAL */ + + DPRINT(("tre_parse: bleep: '%.*" STRF "'\n", REST(ctx->re))); + ctx->re++; + switch (*ctx->re) + { + case L'b': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_WB, -1); + ctx->re++; + break; + case L'B': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_WB_NEG, -1); + ctx->re++; + break; + case L'<': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_BOW, -1); + ctx->re++; + break; + case L'>': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_EOW, -1); + ctx->re++; + break; + case L'x': + ctx->re++; + if (ctx->re[0] != CHAR_LBRACE && ctx->re < ctx->re_end) + { + /* 8 bit hex char. */ + char tmp[3] = {0, 0, 0}; + long val; + DPRINT(("tre_parse: 8 bit hex: '%.*" STRF "'\n", + REST(ctx->re - 2))); + + if (tre_isxdigit(ctx->re[0]) && ctx->re < ctx->re_end) + { + tmp[0] = (char)ctx->re[0]; + ctx->re++; + } + if (tre_isxdigit(ctx->re[0]) && ctx->re < ctx->re_end) + { + tmp[1] = (char)ctx->re[0]; + ctx->re++; + } + val = strtol(tmp, NULL, 16); + result = tre_ast_new_literal(ctx->mem, (int)val, + (int)val, ctx->position); + ctx->position++; + break; + } + else if (ctx->re < ctx->re_end) + { + /* Wide char. */ + char tmp[32]; + long val; + int i = 0; + ctx->re++; + while (ctx->re_end - ctx->re >= 0) + { + if (ctx->re[0] == CHAR_RBRACE) + break; + if (tre_isxdigit(ctx->re[0])) + { + tmp[i] = (char)ctx->re[0]; + i++; + ctx->re++; + continue; + } + return REG_EBRACE; + } + ctx->re++; + tmp[i] = 0; + val = strtol(tmp, NULL, 16); + result = tre_ast_new_literal(ctx->mem, (int)val, (int)val, + ctx->position); + ctx->position++; + break; + } + /*FALLTHROUGH*/ + + default: + if (tre_isdigit(*ctx->re)) + { + /* Back reference. */ + int val = *ctx->re - L'0'; + DPRINT(("tre_parse: backref: '%.*" STRF "'\n", + REST(ctx->re - 1))); + result = tre_ast_new_literal(ctx->mem, BACKREF, val, + ctx->position); + if (result == NULL) + return REG_ESPACE; + ctx->position++; + ctx->max_backref = MAX(val, ctx->max_backref); + ctx->re++; + } + else + { + /* Escaped character. */ + DPRINT(("tre_parse: escaped: '%.*" STRF "'\n", + REST(ctx->re - 1))); + result = tre_ast_new_literal(ctx->mem, *ctx->re, *ctx->re, + ctx->position); + ctx->position++; + ctx->re++; + } + break; + } + if (result == NULL) + return REG_ESPACE; + break; + + case CHAR_PERIOD: /* the any-symbol */ + DPRINT(("tre_parse: any: '%.*" STRF "'\n", + REST(ctx->re))); + if (ctx->cflags & REG_NEWLINE) + { + tre_ast_node_t *tmp1; + tre_ast_node_t *tmp2; + tmp1 = tre_ast_new_literal(ctx->mem, 0, L'\n' - 1, + ctx->position); + if (!tmp1) + return REG_ESPACE; + tmp2 = tre_ast_new_literal(ctx->mem, L'\n' + 1, TRE_CHAR_MAX, + ctx->position + 1); + if (!tmp2) + return REG_ESPACE; + result = tre_ast_new_union(ctx->mem, tmp1, tmp2); + if (!result) + return REG_ESPACE; + ctx->position += 2; + } + else + { + result = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, + ctx->position); + if (!result) + return REG_ESPACE; + ctx->position++; + } + ctx->re++; + break; + + case CHAR_CARET: /* beginning of line assertion */ + /* '^' has a special meaning everywhere in EREs, and in the + beginning of the RE and after \( is BREs. */ + if (ctx->cflags & REG_EXTENDED + || (ctx->re - 2 >= ctx->re_start + && *(ctx->re - 2) == CHAR_BACKSLASH + && *(ctx->re - 1) == CHAR_LPAREN) + || ctx->re == ctx->re_start) + { + DPRINT(("tre_parse: BOL: '%.*" STRF "'\n", + REST(ctx->re))); + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_BOL, -1); + if (result == NULL) + return REG_ESPACE; + ctx->re++; + } + else + goto parse_literal; + break; + + case CHAR_DOLLAR: /* end of line assertion. */ + /* '$' is special everywhere in EREs, and in the end of the + string and before \) is BREs. */ + if (ctx->cflags & REG_EXTENDED + || (ctx->re + 2 < ctx->re_end + && *(ctx->re + 1) == CHAR_BACKSLASH + && *(ctx->re + 2) == CHAR_RPAREN) + || ctx->re + 1 == ctx->re_end) + { + DPRINT(("tre_parse: EOL: '%.*" STRF "'\n", + REST(ctx->re))); + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_EOL, -1); + if (result == NULL) + return REG_ESPACE; + ctx->re++; + } + else + goto parse_literal; + break; + + default: + parse_literal: + + if (temporary_cflags && ctx->re + 1 < ctx->re_end + && *ctx->re == CHAR_BACKSLASH && *(ctx->re + 1) == L'E') + { + DPRINT(("tre_parse: end tmps: '%.*" STRF "'\n", + REST(ctx->re))); + ctx->cflags &= ~temporary_cflags; + temporary_cflags = 0; + ctx->re += 2; + STACK_PUSHX(stack, int, PARSE_PIECE); + break; + } + + + /* We are expecting an atom. If the subexpression (or the whole + regexp ends here, we interpret it as an empty expression + (which matches an empty string). */ + if ( +#ifdef REG_LITERAL + !(ctx->cflags & REG_LITERAL) && +#endif /* REG_LITERAL */ + (ctx->re >= ctx->re_end + || *ctx->re == CHAR_STAR + || (ctx->cflags & REG_EXTENDED + && (*ctx->re == CHAR_PIPE + || *ctx->re == CHAR_LBRACE + || *ctx->re == CHAR_PLUS + || *ctx->re == CHAR_QUESTIONMARK)) + /* Test for "\)" in BRE mode. */ + || (!(ctx->cflags & REG_EXTENDED) + && ctx->re + 1 < ctx->re_end + && *ctx->re == CHAR_BACKSLASH + && *(ctx->re + 1) == CHAR_LBRACE))) + { + DPRINT(("tre_parse: empty: '%.*" STRF "'\n", + REST(ctx->re))); + result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (!result) + return REG_ESPACE; + break; + } + + DPRINT(("tre_parse: literal: '%.*" STRF "'\n", + REST(ctx->re))); + /* Note that we can't use an tre_isalpha() test here, since there + may be characters which are alphabetic but neither upper or + lower case. */ + if (ctx->cflags & REG_ICASE + && (tre_isupper(*ctx->re) || tre_islower(*ctx->re))) + { + tre_ast_node_t *tmp1; + tre_ast_node_t *tmp2; + + /* XXX - Can there be more than one opposite-case + counterpoints for some character in some locale? Or + more than two characters which all should be regarded + the same character if case is ignored? If yes, there + does not seem to be a portable way to detect it. I guess + that at least for multi-character collating elements there + could be several opposite-case counterpoints, but they + cannot be supported portably anyway. */ + tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(*ctx->re), + tre_toupper(*ctx->re), + ctx->position); + if (!tmp1) + return REG_ESPACE; + tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(*ctx->re), + tre_tolower(*ctx->re), + ctx->position); + if (!tmp2) + return REG_ESPACE; + result = tre_ast_new_union(ctx->mem, tmp1, tmp2); + if (!result) + return REG_ESPACE; + } + else + { + result = tre_ast_new_literal(ctx->mem, *ctx->re, *ctx->re, + ctx->position); + if (!result) + return REG_ESPACE; + } + ctx->position++; + ctx->re++; + break; + } + break; + + case PARSE_MARK_FOR_SUBMATCH: + { + int submatch_id = tre_stack_pop_int(stack); + + if (result->submatch_id >= 0) + { + tre_ast_node_t *n, *tmp_node; + n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (n == NULL) + return REG_ESPACE; + tmp_node = tre_ast_new_catenation(ctx->mem, n, result); + if (tmp_node == NULL) + return REG_ESPACE; + tmp_node->num_submatches = result->num_submatches; + result = tmp_node; + } + result->submatch_id = submatch_id; + result->num_submatches++; + break; + } + + case PARSE_RESTORE_CFLAGS: + ctx->cflags = tre_stack_pop_int(stack); + break; + + default: + assert(0); + break; + } + } + + /* Check for missing closing parentheses. */ + if (depth > 0) + return REG_EPAREN; + + if (status == REG_OK) + ctx->result = result; + + return status; +} + +/* EOF */ +/* + tre-stack.c - Simple stack implementation + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ +#include <stdlib.h> +#include <assert.h> + + +union tre_stack_item { + void *voidptr_value; + int int_value; +}; + +struct tre_stack_rec { + int size; + int max_size; + int increment; + int ptr; + union tre_stack_item *stack; +}; + + +tre_stack_t * +tre_stack_new(int size, int max_size, int increment) +{ + tre_stack_t *s; + + s = xmalloc(sizeof(*s)); + if (s != NULL) + { + s->stack = xmalloc(sizeof(*s->stack) * size); + if (s->stack == NULL) + { + xfree(s); + return NULL; + } + s->size = size; + s->max_size = max_size; + s->increment = increment; + s->ptr = 0; + } + return s; +} + +void +tre_stack_destroy(tre_stack_t *s) +{ + xfree(s->stack); + xfree(s); +} + +int +tre_stack_num_objects(tre_stack_t *s) +{ + return s->ptr; +} + +static reg_errcode_t +tre_stack_push(tre_stack_t *s, union tre_stack_item value) +{ + if (s->ptr < s->size) + { + s->stack[s->ptr] = value; + s->ptr++; + } + else + { + if (s->size >= s->max_size) + { + DPRINT(("tre_stack_push: stack full\n")); + return REG_ESPACE; + } + else + { + union tre_stack_item *new_buffer; + int new_size; + DPRINT(("tre_stack_push: trying to realloc more space\n")); + new_size = s->size + s->increment; + if (new_size > s->max_size) + new_size = s->max_size; + new_buffer = xrealloc(s->stack, sizeof(*new_buffer) * new_size); + if (new_buffer == NULL) + { + DPRINT(("tre_stack_push: realloc failed.\n")); + return REG_ESPACE; + } + DPRINT(("tre_stack_push: realloc succeeded.\n")); + assert(new_size > s->size); + s->size = new_size; + s->stack = new_buffer; + tre_stack_push(s, value); + } + } + return REG_OK; +} + +#define define_pushf(typetag, type) \ + declare_pushf(typetag, type) { \ + union tre_stack_item item; \ + item.typetag ## _value = value; \ + return tre_stack_push(s, item); \ +} + +define_pushf(int, int) +define_pushf(voidptr, void *) + +#define define_popf(typetag, type) \ + declare_popf(typetag, type) { \ + return s->stack[--s->ptr].typetag ## _value; \ + } + +define_popf(int, int) +define_popf(voidptr, void *) + +/* EOF */ +/* + xmalloc.c - Simple malloc debugging library implementation + + This software is released under a BSD-style license. + See the file LICENSE for details and copyright. + +*/ + +/* + TODO: + - red zones + - group dumps by source location +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif /* HAVE_CONFIG_H */ + +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#define XMALLOC_INTERNAL 1 + + +/* + Internal stuff. +*/ + +typedef struct hashTableItemRec { + void *ptr; + int bytes; + const char *file; + int line; + const char *func; + struct hashTableItemRec *next; +} hashTableItem; + +typedef struct { + hashTableItem **table; +} hashTable; + +static int xmalloc_peak; +int xmalloc_current; +static int xmalloc_peak_blocks; +int xmalloc_current_blocks; +static int xmalloc_fail_after; + +#define TABLE_BITS 8 +#define TABLE_MASK ((1 << TABLE_BITS) - 1) +#define TABLE_SIZE (1 << TABLE_BITS) + +static hashTable * +hash_table_new(void) +{ + hashTable *tbl; + + tbl = malloc(sizeof(*tbl)); + + if (tbl != NULL) + { + tbl->table = calloc(TABLE_SIZE, sizeof(*tbl->table)); + + if (tbl->table == NULL) + { + free(tbl); + return NULL; + } + } + + return tbl; +} + +static int +hash_void_ptr(void *ptr) +{ + int hash; + int i; + + /* I took this hash function just off the top of my head, I have + no idea whether it is bad or very bad. */ + hash = 0; + for (i = 0; i < (int)sizeof(ptr)*8 / TABLE_BITS; i++) + { + hash ^= (unsigned long)ptr >> i*8; + hash += i * 17; + hash &= TABLE_MASK; + } + return hash; +} + +static void +hash_table_add(hashTable *tbl, void *ptr, int bytes, + const char *file, int line, const char *func) +{ + int i; + hashTableItem *item, *new; + + i = hash_void_ptr(ptr); + + item = tbl->table[i]; + if (item != NULL) + while (item->next != NULL) + item = item->next; + + new = malloc(sizeof(*new)); + assert(new != NULL); + new->ptr = ptr; + new->bytes = bytes; + new->file = file; + new->line = line; + new->func = func; + new->next = NULL; + if (item != NULL) + item->next = new; + else + tbl->table[i] = new; + + xmalloc_current += bytes; + if (xmalloc_current > xmalloc_peak) + xmalloc_peak = xmalloc_current; + xmalloc_current_blocks++; + if (xmalloc_current_blocks > xmalloc_peak_blocks) + xmalloc_peak_blocks = xmalloc_current_blocks; +} + +static void +hash_table_del(hashTable *tbl, void *ptr) +{ + int i; + hashTableItem *item, *prev; + + i = hash_void_ptr(ptr); + + item = tbl->table[i]; + if (item == NULL) + { + printf("xfree: invalid ptr %p\n", ptr); + abort(); + } + prev = NULL; + while (item->ptr != ptr) + { + prev = item; + item = item->next; + } + if (item->ptr != ptr) + { + printf("xfree: invalid ptr %p\n", ptr); + abort(); + } + + xmalloc_current -= item->bytes; + xmalloc_current_blocks--; + + if (prev != NULL) + { + prev->next = item->next; + free(item); + } + else + { + tbl->table[i] = item->next; + free(item); + } +} + +static hashTable *xmalloc_table = NULL; + +static void +xmalloc_init(void) +{ + if (xmalloc_table == NULL) + { + xmalloc_table = hash_table_new(); + xmalloc_peak = 0; + xmalloc_peak_blocks = 0; + xmalloc_current = 0; + xmalloc_current_blocks = 0; + xmalloc_fail_after = -1; + } + assert(xmalloc_table != NULL); + assert(xmalloc_table->table != NULL); +} + + + +/* + Public API. +*/ + +void +xmalloc_configure(int fail_after) +{ + xmalloc_init(); + xmalloc_fail_after = fail_after; +} + +int +xmalloc_dump_leaks(void) +{ + int i; + int num_leaks = 0; + int leaked_bytes = 0; + hashTableItem *item; + + xmalloc_init(); + + for (i = 0; i < TABLE_SIZE; i++) + { + item = xmalloc_table->table[i]; + while (item != NULL) + { + printf("%s:%d: %s: %d bytes at %p not freed\n", + item->file, item->line, item->func, item->bytes, item->ptr); + num_leaks++; + leaked_bytes += item->bytes; + item = item->next; + } + } + if (num_leaks == 0) + printf("No memory leaks.\n"); + else + printf("%d unfreed memory chuncks, total %d unfreed bytes.\n", + num_leaks, leaked_bytes); + printf("Peak memory consumption %d bytes (%.1f kB, %.1f MB) in %d blocks ", + xmalloc_peak, (double)xmalloc_peak / 1024, + (double)xmalloc_peak / (1024*1024), xmalloc_peak_blocks); + printf("(average "); + if (xmalloc_peak_blocks) + printf("%d", ((xmalloc_peak + xmalloc_peak_blocks / 2) + / xmalloc_peak_blocks)); + else + printf("N/A"); + printf(" bytes per block).\n"); + + return num_leaks; +} + +void * +xmalloc_impl(size_t size, const char *file, int line, const char *func) +{ + void *ptr; + + xmalloc_init(); + assert(size > 0); + + if (xmalloc_fail_after == 0) + { + xmalloc_fail_after = -2; +#if 0 + printf("xmalloc: forced failure %s:%d: %s\n", file, line, func); +#endif + return NULL; + } + else if (xmalloc_fail_after == -2) + { + printf("xmalloc: called after failure from %s:%d: %s\n", + file, line, func); + assert(0); + } + else if (xmalloc_fail_after > 0) + xmalloc_fail_after--; + + ptr = malloc(size); + if (ptr != NULL) + hash_table_add(xmalloc_table, ptr, (int)size, file, line, func); + return ptr; +} + +void * +xcalloc_impl(size_t nmemb, size_t size, const char *file, int line, + const char *func) +{ + void *ptr; + + xmalloc_init(); + assert(size > 0); + + if (xmalloc_fail_after == 0) + { + xmalloc_fail_after = -2; +#if 0 + printf("xcalloc: forced failure %s:%d: %s\n", file, line, func); +#endif + return NULL; + } + else if (xmalloc_fail_after == -2) + { + printf("xcalloc: called after failure from %s:%d: %s\n", + file, line, func); + assert(0); + } + else if (xmalloc_fail_after > 0) + xmalloc_fail_after--; + + ptr = calloc(nmemb, size); + if (ptr != NULL) + hash_table_add(xmalloc_table, ptr, (int)(nmemb * size), file, line, func); + return ptr; +} + +void +xfree_impl(void *ptr, const char *file, int line, const char *func) +{ + /*LINTED*/(void)&file; + /*LINTED*/(void)&line; + /*LINTED*/(void)&func; + xmalloc_init(); + + if (ptr != NULL) + hash_table_del(xmalloc_table, ptr); + free(ptr); +} + +void * +xrealloc_impl(void *ptr, size_t new_size, const char *file, int line, + const char *func) +{ + void *new_ptr; + + xmalloc_init(); + assert(ptr != NULL); + assert(new_size > 0); + + if (xmalloc_fail_after == 0) + { + xmalloc_fail_after = -2; + return NULL; + } + else if (xmalloc_fail_after == -2) + { + printf("xrealloc: called after failure from %s:%d: %s\n", + file, line, func); + assert(0); + } + else if (xmalloc_fail_after > 0) + xmalloc_fail_after--; + + new_ptr = realloc(ptr, new_size); + if (new_ptr != NULL) + { + hash_table_del(xmalloc_table, ptr); + hash_table_add(xmalloc_table, new_ptr, (int)new_size, file, line, func); + } + return new_ptr; +} + + + +/* EOF */ |