--- /dev/null
+/*
+ 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>
+#include <stddef.h>
+
+#include "xmalloc.h"
+#include "tre-mem.h"
+#include "tre-ast.h"
+#include "tre-stack.h"
+#include "tre-parse.h"
+
+/* BSD compatibility:
+ Before looking up a collating symbol, check if the name matches in
+ the character names (cnames) array; if so, use the corresponding
+ character.
+
+ Also set ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND, which will preserve
+ the implementation choice that for ERE, a non-numeric character following
+ a left brace that would normally be a bound, causes the left brace to be
+ literal. */
+#define BSD_COMPATIBILITY
+#ifdef BSD_COMPATIBILITY
+#include "cname.h"
+#define ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+#endif /* BSD_COMPATIBILITY */
+
+/* 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 type, int val, int *max_i,
+ tre_bracket_match_list_t **items)
+{
+ reg_errcode_t status = REG_OK;
+ tre_bracket_match_list_t *array = *items;
+ int i = array->num_bracket_matches;
+ /* Allocate more space if necessary. */
+ if (i >= *max_i)
+ {
+ tre_bracket_match_list_t *new_items;
+ DPRINT(("out of tre_bracket_match_list_t array space (%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_BRACKET_MATCH_LIST_N(*max_i));
+ if (new_items == NULL)
+ return REG_ESPACE;
+ *items = array = new_items;
+ }
+ array->bracket_matches[i].type = type;
+ array->bracket_matches[i].value = val;
+ array->num_bracket_matches++;
+ return status;
+}
+
+#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 */
+
+#define REST(re) (int)(ctx->re_end - (re)), (re)
+
+#define START_COLLATING_SYMBOLS 16
+#define MAX_COLLATING_SYMBOL_LEN 4
+
+typedef struct {
+ const tre_char_t *start;
+ int len;
+} tre_collating_symbol;
+
+#include <xlocale.h>
+
+int __collate_equiv_value(locale_t loc, const wchar_t *str, size_t len);
+
+#ifdef BSD_COMPATIBILITY
+static wchar_t
+tre_search_cnames(const wchar_t *name, size_t len)
+{
+ size_t low = 0;
+ size_t high = NCNAMES - 1;
+ size_t cur;
+ int cmp;
+
+ while(low <= high)
+ {
+ cur = (low + high) / 2;
+ cmp = wcsncmp(name, cnames[cur].name, len);
+ if (cmp == 0 && cnames[cur].name[len] == 0) return cnames[cur].code;
+ if (cmp > 0) low = cur + 1;
+ else high = cur - 1;
+ }
+ return (wchar_t)-1;
+}
+#endif /* BSD_COMPATIBILITY */
+
+/* Scan the contents of a bracket expression, and create a
+ * tre_bracket_match_list_t encoding the bracket expression. If during
+ * the scan, multi-character collating symbols are detected, switch
+ * into a mode to collect those MCCSs into a tre_collating_symbol
+ * list and pass them back. tre_parse_bracket will use that to
+ * create a new string composed of a union of the bracket expression
+ * without the MCCSs and the MCCSs (e.g., [x[.ch.]] => [x]|ch), and
+ * call tre_parse (recursive) to parse that new string (which will
+ * call tre_parse_bracket and tre_parse_bracket_items again. */
+static reg_errcode_t
+tre_parse_bracket_items(tre_parse_ctx_t *ctx, tre_bracket_match_list_t **items,
+ int *items_size, tre_collating_symbol **result)
+{
+ const tre_char_t *re = ctx->re;
+ const tre_char_t *re_end = ctx->re_end;
+ tre_collating_symbol *col_syms = NULL;
+ tre_collating_symbol *cp = NULL;
+ int n_col_syms = 0;
+ reg_errcode_t status;
+ int max_i = *items_size;
+ int other = 0; /* contains content other than multi-character collating
+ * symbols */
+ int range = -1; /* -1 unset, 0 begin range set, +1 end range expected */
+ tre_cint_t min, c;
+ int invert = ((*items)->flags & TRE_BRACKET_MATCH_FLAG_NEGATE);
+ int collect_MCCS = 0;
+ const tre_char_t *start;
+
+ for ( ;re < re_end; re++)
+ {
+ switch (*re)
+ {
+ case CHAR_MINUS:
+ /* A first hyphen */
+ if (re == ctx->re)
+ {
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ min = CHAR_MINUS;
+ other++;
+ range = 0;
+ break;
+ }
+ /* The hyphen is the end range */
+ if (range > 0)
+ {
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ c = CHAR_MINUS;
+ goto process_end_range;
+ }
+ if (re + 1 >= re_end)
+ {
+ status = REG_EBRACK;
+ goto error;
+ }
+ /* The hyphen is at the end */
+ if (re[1] == CHAR_RBRACKET)
+ {
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ c = CHAR_MINUS;
+ goto process_begin_range;
+ }
+ /* Two ranges are not allowed to share an endpoint, or begin
+ * range is illegal. */
+ if (range < 0)
+ {
+ status = REG_ERANGE;
+ goto error;
+ }
+ range = 1; /* Expect end range */
+ DPRINT(("tre_parse_bracket: range: '%.*" STRF "'\n", REST(re)));
+ break;
+
+ case CHAR_LBRACKET:
+ if (re + 1 >= re_end)
+ {
+ status = REG_EBRACK;
+ goto error;
+ }
+ switch (re[1])
+ {
+ case CHAR_PERIOD:
+ {
+ re += 2;
+ start = re;
+ for (;; re++)
+ {
+ if (re >= re_end)
+ {
+ status = REG_ECOLLATE;
+ goto error;
+ }
+ if (*re == CHAR_PERIOD)
+ {
+ if (re + 1 >= re_end)
+ {
+ status = REG_ECOLLATE;
+ goto error;
+ }
+ /* Found end */
+ if (re[1] == CHAR_RBRACKET)
+ {
+ DPRINT(("tre_parse_bracket: collating "
+ "symbol: '%.*" STRF "'\n",
+ REST(start - 2)));
+ /* Empty name */
+ if (re == start)
+ {
+ status = REG_ECOLLATE;
+ goto error;
+ }
+#ifdef BSD_COMPATIBILITY
+ /* Check if the name is in cnames; if so, use
+ the corresponding code */
+ c = tre_search_cnames(start, re - start);
+ if (c != (wchar_t)-1)
+ {
+ re++;
+ goto process_single_character;
+ }
+#endif /* BSD_COMPATIBILITY */
+ /* Verify this is a known sequence */
+ if (__collate_equiv_value(ctx->loc, start,
+ re - start) <= 0)
+ {
+ status = REG_ECOLLATE;
+ goto error;
+ }
+ /* Process single character collating symbols */
+ if (re - start == 1)
+ {
+ c = *start;
+ re++;
+ goto process_single_character;
+ }
+ /* Inverted MCCSs are undefined */
+ if (invert)
+ {
+ status = REG_ECOLLATE;
+ goto error;
+ }
+ /* Can't have MCCSs as an endpoint to a range */
+ if (range > 0)
+ {
+ status = REG_ERANGE;
+ goto error;
+ }
+ range = -1;
+ /* Switch into MCCS collection mode (if not
+ * already there */
+#if TRE_DEBUG
+ if (!collect_MCCS)
+ {
+ collect_MCCS = 1;
+ DPRINT(("tre_parse_bracket: Detected MCCS\n"));
+ }
+#else /* !TRE_DEBUG */
+ collect_MCCS = 1;
+#endif /* !TRE_DEBUG */
+ /* Allocate a memory block the first time */
+ if (!cp)
+ {
+ if ((col_syms = xmalloc(sizeof(*col_syms) *
+ (START_COLLATING_SYMBOLS + 2)))
+ == NULL)
+ return REG_ESPACE;
+ cp = col_syms + 1;
+ n_col_syms = START_COLLATING_SYMBOLS;
+ }
+ /* Enlarge the memory block is more is needed */
+ if ((cp - col_syms) - 1 >= n_col_syms)
+ {
+ int i = n_col_syms;
+ tre_collating_symbol *tmp =
+ xrealloc(col_syms, sizeof(*col_syms) *
+ ((n_col_syms *= 2) + 2));
+ if (tmp == NULL)
+ {
+ xfree(col_syms);
+ return REG_ESPACE;
+ }
+ DPRINT(("tre_list_collating_symbols: "
+ "Enlarging col_syms to %d\n",
+ n_col_syms));
+ col_syms = tmp;
+ cp = col_syms + i + 1;
+ }
+ cp->start = start;
+ cp->len = re - start;
+ cp++;
+ re++;
+ break;
+ }
+ }
+ }
+ break;
+ }
+
+ case CHAR_EQUAL:
+ case CHAR_COLON:
+ {
+ /* Process equivalence and character classes */
+ tre_char_t kind = re[1];
+
+ /* Can't have a class as an endpoint to a range */
+ if (range > 0)
+ {
+ status = REG_ERANGE;
+ goto error;
+ }
+ if (!collect_MCCS && range == 0)
+ {
+ status = tre_new_item(ctx->mem, TRE_BRACKET_MATCH_TYPE_CHAR,
+ min, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ range = -1;
+ re += 2;
+ start = re;
+ for (;; re++)
+ {
+ if (re >= re_end)
+ {
+ status = kind == CHAR_EQUAL ? REG_ECOLLATE : REG_ECTYPE;
+ goto error;
+ }
+ if (*re == kind)
+ {
+ if (re + 1 >= re_end)
+ {
+ status = kind == CHAR_EQUAL ? REG_ECOLLATE :
+ REG_ECTYPE;
+ goto error;
+ }
+ /* Found end */
+ if (re[1] == CHAR_RBRACKET)
+ {
+ if (re == start)
+ {
+ /* Empty class name */
+ status = kind == CHAR_EQUAL ? REG_ECOLLATE :
+ REG_ECTYPE;
+ goto error;
+ }
+ /* Process equivalence class */
+ if (kind == CHAR_EQUAL)
+ {
+ int equiv;
+
+ DPRINT(("tre_parse_bracket: equivalence: '%.*"
+ STRF "'\n", REST(start - 2)));
+
+ /* While we find the collation value even for
+ multi-character collating elements , we
+ don't (yet) match any collation values
+ against multi-character sequences. We'd have
+ to enumerate those multi-character sequences
+ and like multi-character collating symbols,
+ create a union of those sequences with the
+ rest of the bracket expression. While
+ doable, a bracket expression matching
+ multiple characters, that doesn't explicitly
+ contain multi-character sequences, might
+ be unexpected, so we punt for now. */
+ if ((equiv = __collate_equiv_value(ctx->loc,
+ start, re - start)) <= 0)
+ {
+ /* The standard says that if no collating
+ element if found, we use the collating
+ symbol itself. But __collate_equiv_value
+ doesn't make a distinction between
+ an element that is in a equvalence
+ class with others, or is the only member,
+ so we already know there is no collating
+ symbol. (Note that in the case of a
+ collating element whose collation value
+ is unique, matching against the
+ collating element itself, or against
+ its collation value, is equivalent.) */
+#ifdef BSD_COMPATIBILITY
+ /* Check if the name is in cnames; if so,
+ use the corresponding code */
+ c = tre_search_cnames(start, re - start);
+ if (c != (wchar_t)-1)
+ {
+ re++;
+ goto process_single_character;
+ }
+#endif /* BSD_COMPATIBILITY */
+ status = REG_ECOLLATE;
+ goto error;
+ }
+ if (!collect_MCCS)
+ {
+ status = tre_new_item(ctx->mem,
+ TRE_BRACKET_MATCH_TYPE_EQUIVALENCE,
+ equiv, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ }
+ else
+ {
+ /* Process character class */
+ DPRINT(("tre_parse_bracket: class: '%.*" STRF
+ "'\n", REST(start - 2)));
+ if (!collect_MCCS)
+ {
+ char tmp_str[64];
+ tre_ctype_t class;
+ int len = MIN(re - start, 63);
+#ifdef TRE_WCHAR
+ {
+ tre_char_t tmp_wcs[64];
+ wcsncpy(tmp_wcs, start, (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_l(tmp_str, &src,
+ sizeof(tmp_str), &state,
+ ctx->loc);
+ }
+#elif defined HAVE_WCSTOMBS
+ len = wcstombs(tmp_str, tmp_wcs, 63);
+#endif /* defined HAVE_WCSTOMBS */
+ }
+#else /* !TRE_WCHAR */
+ strncpy(tmp_str, (const char*)start, len);
+#endif /* !TRE_WCHAR */
+ tmp_str[len] = '\0';
+ DPRINT((" class name: %s\n", tmp_str));
+ class = tre_ctype_l(tmp_str, ctx->loc);
+ if (!class)
+ {
+ status = REG_ECTYPE;
+ goto error;
+ }
+ status = tre_new_item(ctx->mem,
+ TRE_BRACKET_MATCH_TYPE_CLASS,
+ class, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ }
+ re++;
+ break;
+ }
+ }
+ }
+ other++;
+ break;
+ }
+
+ default:
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ c = CHAR_LBRACKET;
+ goto process_single_character;
+ break;
+ }
+ break;
+
+ case CHAR_RBRACKET:
+ /* A first right bracket */
+ if (re == ctx->re)
+ {
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ min = CHAR_RBRACKET;
+ range = 0;
+ other++;
+ break;
+ }
+ /* Done */
+ if (collect_MCCS)
+ {
+ DPRINT(("tre_parse_bracket: done: '%.*" STRF "'\n",
+ REST(re)));
+ if (col_syms)
+ {
+ /* Mark the character following the right bracket. Set len
+ * to whether there are other things besides the
+ * multi-character collating symbols */
+ col_syms->start = re + 1;
+ col_syms->len = other;
+ /* Mark the end of the list */
+ cp->start = NULL;
+ }
+ *result = col_syms;
+ return REG_OK;
+ }
+ /* range > 0 is not possible, since we did a lookahead after the
+ * hyphen */
+ if (range == 0)
+ {
+ status = tre_new_item(ctx->mem, TRE_BRACKET_MATCH_TYPE_CHAR,
+ min, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ DPRINT(("tre_parse_bracket: done: '%.*" STRF "'\n", REST(re)));
+ *items_size = max_i;
+ ctx->re = re + 1;
+ return REG_OK;
+
+ default:
+ DPRINT(("tre_parse_bracket: char: '%.*" STRF "'\n", REST(re)));
+ c = *re;
+process_single_character:
+ /* Process single character */
+ if (range > 0)
+ {
+ int mine, maxe;
+
+process_end_range:
+ /* Get collation equivalence values */
+ mine = __collate_equiv_value(ctx->loc, &min, 1);
+ maxe = __collate_equiv_value(ctx->loc, &c, 1);
+ if (maxe < mine)
+ {
+ status = REG_ERANGE;
+ goto error;
+ }
+ if (!collect_MCCS)
+ {
+ status = tre_new_item(ctx->mem,
+ TRE_BRACKET_MATCH_TYPE_RANGE_BEGIN,
+ mine, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ status = tre_new_item(ctx->mem,
+ TRE_BRACKET_MATCH_TYPE_RANGE_END,
+ maxe, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ range = -1;
+ }
+ else
+ {
+process_begin_range:
+ if (!collect_MCCS)
+ {
+ if (range == 0)
+ {
+ status = tre_new_item(ctx->mem,
+ TRE_BRACKET_MATCH_TYPE_CHAR,
+ min, &max_i, items);
+ if (status != REG_OK)
+ goto error;
+ }
+ min = c;
+ }
+ range = 0;
+ }
+ other++;
+ break;
+ }
+ }
+ status = REG_EBRACK;
+error:
+ DPRINT(("tre_parse_bracket: error: '%.*" STRF "', status=%d\n",
+ REST(re), status));
+ if (col_syms)
+ xfree(col_syms);
+ return status;
+}
+
+#ifdef TRE_DEBUG
+static const char *bracket_match_type_str[] = {
+ "unused",
+ "char",
+ "range begin",
+ "range end",
+ "class",
+ "equivalence value",
+};
+#endif /* TRE_DEBUG */
+
+static reg_errcode_t
+tre_parse_bracket(tre_parse_ctx_t *ctx, tre_ast_node_t **result)
+{
+ tre_ast_node_t *node;
+ reg_errcode_t status = REG_OK;
+ tre_bracket_match_list_t *items;
+ int max_i = 32;
+ tre_collating_symbol *col_syms = NULL;
+
+ /* Handle special cases [[:<:]] and [[:>:]] */
+ if (ctx->re_end - ctx->re >= 6 && ctx->re[0] == CHAR_LBRACKET
+ && ctx->re[1] == CHAR_COLON && (ctx->re[2] == L'<' || ctx->re[2] == L'>')
+ && ctx->re[3] == CHAR_COLON && ctx->re[4] == CHAR_RBRACKET
+ && ctx->re[5] == CHAR_RBRACKET)
+ {
+ *result = tre_ast_new_literal(ctx->mem, ASSERTION,
+ (ctx->re[2] == L'<') ? ASSERT_AT_BOW : ASSERT_AT_EOW,
+ -1);
+ DPRINT(("tre_parse_bracket: special case %s\n", (ctx->re[2] == L'<') ?
+ "[[:<:]]" : "[[:>:]]"));
+ ctx->re += 6;
+ return *result ? REG_OK : REG_ESPACE;
+ }
+
+ /* Start off with an array of `max_i' elements. */
+ items = xcalloc(1, SIZEOF_BRACKET_MATCH_LIST_N(max_i));
+ if (items == NULL)
+ return REG_ESPACE;
+
+ if (*ctx->re == CHAR_CARET)
+ {
+ DPRINT(("tre_parse_bracket: negate: '%.*" STRF "'\n", REST(ctx->re)));
+ items->flags |= TRE_BRACKET_MATCH_FLAG_NEGATE;
+ ctx->re++;
+ }
+
+ status = tre_parse_bracket_items(ctx, &items, &max_i, &col_syms);
+
+ if (status != REG_OK)
+ goto parse_bracket_done;
+
+ /* If there are collating symbols, split off the multi-character ones
+ * into a union of the bracket expression (without the collating symbols)
+ * and the multiple-character sequences. We create an equivalent input
+ * string and run tre_parse() recursively */
+ if (col_syms)
+ {
+ tre_char_t *str, *sp;
+ tre_collating_symbol *cp;
+ tre_parse_ctx_t subctx;
+
+ /* Allocate a new string. We start with the size of the original
+ * bracket expression (minus 1) and add 2 (for a leading "[" and
+ * a trailing nil; don't need a "^", since it is illegal to have
+ * inverted MCCSs). Since a multi-character collating symbols
+ * will be converted from "[.xx.]" to "|xx" (n+4 to n+1), we don't
+ * need to worry about the new string getting too long. */
+ xfree(items);
+ str = xmalloc(sizeof(*str) * ((col_syms->start - ctx->re) + 2));
+ if (str == NULL)
+ {
+ xfree(col_syms);
+ return REG_ESPACE;
+ }
+ sp = str;
+ if (col_syms->len > 0)
+ {
+ /* There are other items in the bracket expression besides the
+ * multi-character collating symbols, so create a new bracket
+ * expression with only those other itmes. */
+ const tre_char_t *re;
+ ptrdiff_t i;
+
+ *sp++ = '[';
+ re = ctx->re;
+ for (cp = col_syms + 1; cp->start; cp++)
+ {
+ /* The "- 2" is to account for the "[." */
+ if ((i = ((cp->start - re) - 2)) > 0)
+ {
+ memcpy(sp, re, sizeof(*sp) * i);
+ sp += i;
+ }
+ /* The "+ 2" is to account for the ".]" */
+ re = cp->start + cp->len + 2;
+ }
+ i = col_syms->start - re; /* Includes the trailing right bracket */
+ memcpy(sp, re, sizeof(*sp) * i);
+ sp += i;
+ *sp++ = '|';
+ }
+ for (cp = col_syms + 1; cp->start; cp++)
+ {
+ memcpy(sp, cp->start, sizeof(*sp) * cp->len);
+ sp += cp->len;
+ if (cp[1].start)
+ *sp++ = '|';
+ }
+ *sp = 0;
+ DPRINT(("tre_parse_bracket: Reparsing bracket expression with '%ls'\n",
+ str));
+
+ memcpy(&subctx, ctx, sizeof(subctx));
+ subctx.re = str;
+ subctx.len = sp - str;
+ subctx.nofirstsub = 1;
+ subctx.cflags |= REG_EXTENDED; /* Force extended mode for parsing */
+ status = tre_parse(&subctx);
+ xfree(str);
+ if (status != REG_OK)
+ {
+ xfree(col_syms);
+ return status;
+ }
+ ctx->re = col_syms->start;
+ ctx->position = subctx.position;
+ xfree(col_syms);
+ *result = subctx.result;
+ DPRINT(("tre_parse_bracket: Returning to original string\n"));
+ return REG_OK;
+ }
+
+ DPRINT(("tre_parse_bracket: creating bracket expression literal\n"));
+ node = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, ctx->position);
+ if (node == NULL)
+ {
+ status = REG_ESPACE;
+ goto parse_bracket_done;
+ }
+ else
+ {
+ tre_literal_t *l = node->obj;
+ l->u.bracket_match_list = tre_mem_alloc(ctx->mem,
+ SIZEOF_BRACKET_MATCH_LIST(items));
+ if (l->u.bracket_match_list == NULL)
+ {
+ status = REG_ESPACE;
+ goto parse_bracket_done;
+ }
+ memcpy(l->u.bracket_match_list, items, SIZEOF_BRACKET_MATCH_LIST(items));
+ }
+
+#ifdef TRE_DEBUG
+ {
+ int i;
+ tre_bracket_match_t *b;
+ DPRINT(("tre_parse_bracket: %d bracket match items, flags 0x%x\n",
+ items->num_bracket_matches, items->flags));
+ for (i = 0, b = items->bracket_matches;
+ i < items->num_bracket_matches; i++, b++)
+ {
+ DPRINT((" %d: %s %d\n", i, bracket_match_type_str[b->type],
+ b->value));
+ }
+ }
+#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;
+#ifdef TRE_APPROX
+ int i;
+ int cost_ins, cost_del, cost_subst, cost_max;
+ int limit_ins, limit_del, limit_subst, limit_err;
+ const tre_char_t *start;
+#endif /* TRE_APPROX */
+ const tre_char_t *r = ctx->re;
+ int minimal = (ctx->cflags & REG_UNGREEDY) ? 1 : 0;
+#ifdef TRE_APPROX
+ 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;
+#endif /* TRE_APPROX */
+
+ /* Parse number (minimum repetition count). */
+ min = -1;
+ if (r >= ctx->re_end)
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ return (ctx->cflags & REG_EXTENDED) ? REG_NOMATCH : REG_EBRACE;
+#else /* !ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ return REG_EBRACE;
+#endif /* !ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ if (*r >= L'0' && *r <= L'9') {
+ DPRINT(("tre_parse: min count: '%.*" STRF "'\n", REST(r)));
+ min = tre_parse_int(&r, ctx->re_end);
+ }
+#ifndef TRE_APPROX
+ else
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ /* For ERE, return REG_NOMATCH to signal that the lbrace should
+ be treated as a literal */
+ return (ctx->cflags & REG_EXTENDED) ? REG_NOMATCH : REG_BADBR;
+#else /* !ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ return REG_BADBR;
+#endif /* !ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+#endif /* !TRE_APPROX */
+
+ /* 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) || min > RE_DUP_MAX || max > RE_DUP_MAX)
+ return REG_BADBR;
+
+
+#ifdef TRE_APPROX
+ /*
+ '{'
+ 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);
+#endif /* TRE_APPROX */
+
+ /*{*//* 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++;
+ /* Parse trailing '?' marking minimal repetition. */
+ if (r < ctx->re_end)
+ {
+ if (*r == CHAR_QUESTIONMARK)
+ {
+ /* Process the question mark only in enhanced mode.
+ Otherwise, the question mark is an error in ERE
+ or a literal in BRE */
+ if (ctx->cflags & REG_ENHANCED)
+ {
+ minimal = !(ctx->cflags & REG_UNGREEDY);
+ r++;
+ }
+ else return REG_BADRPT;
+ }
+ else if (*r == CHAR_STAR || *r == CHAR_PLUS)
+ {
+ /* These are reserved for future extensions. */
+ return REG_BADRPT;
+ }
+ }
+ }
+ else
+ {
+ if (r + 1 >= ctx->re_end
+ || *r != CHAR_BACKSLASH
+ || *(r + 1) != CHAR_RBRACE)
+ return REG_BADBR;
+ r += 2;
+ if (r < ctx->re_end && *r == CHAR_STAR)
+ {
+ /* This is reserved for future extensions. */
+ return REG_BADRPT;
+ }
+ }
+
+ if (minimal)
+ ctx->num_reorder_tags++;
+
+ if (!result) goto parse_bound_exit;
+ /* Create the AST node(s). */
+ /* Originally, if min == 0 && max == 0, we immediately replace the whole
+ iteration with EMPTY. This unfortunately drops any submatches, and
+ messes up setting the pmatch values (we can get tags of -1, and
+ tag values in the billions). So we leave it and process this case as
+ usual, and wait until tre_expand_ast() to replace with EMPTY */
+#ifdef TRE_APPROX
+ if (min < 0 && max < 0)
+ /* Only approximate parameters set, no repetitions. */
+ min = max = 1;
+#endif /* TRE_APPROX */
+
+ *result = tre_ast_new_iter(ctx->mem, *result, min, max, minimal);
+ if (!*result)
+ return REG_ESPACE;
+
+#ifdef TRE_APPROX
+ /* 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;
+ }
+#endif /* TRE_APPROX */
+
+parse_bound_exit:
+#ifdef TRE_APPROX
+ 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));
+#else /* !TRE_APPROX */
+ DPRINT(("tre_parse_bound: min %d, max %d\n", min, max));
+#endif /* !TRE_APPROX */
+
+
+ ctx->re = r;
+ return REG_OK;
+}
+
+/* Previously, we had PARSE_RESTORE_CFLAGS restore the cflags, but for
+ non-self-contained options, like (?i), this causes ((?i)fu)bar to be
+ treated more like ((?i)fu(?-i)bar), so the pmatch value is incorrect.
+ Because we now set up tags for even non-capturing parenthesized
+ subexpressions, we always call PARSE_MARK_FOR_SUBMATCH. So if we
+ pass the unmodified version of cflags to PARSE_MARK_FOR_SUBMATCH and
+ have it restore cflags after the subexpression, we don't need to have
+ a separate PARSE_RESTORE_CFLAGS, and then after processing the
+ non-self-contained option, we can call PARSE_ATOM instead of PARSE_RE.
+ This has the side-benefit of now matching the perl behavior: the RE
+ foo(?i)bar|zap is foo(?i)bar OR (?i)zap instead of TRE previous behavior
+ of foo AND (?i) (bar OR zap). */
+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,
+} 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;
+ int bre_branch_begin;
+#ifdef TRE_DEBUG
+ const tre_char_t *tmp_re;
+#endif
+
+ DPRINT(("tre_parse: parsing '%.*" STRF "', len = %d cflags = 0%o\n",
+ ctx->len, ctx->re, ctx->len, ctx->cflags));
+
+ if (ctx->len <= 0) return REG_EMPTY;
+ if (!ctx->nofirstsub)
+ {
+ STACK_PUSH(stack, int, ctx->cflags);
+ STACK_PUSH(stack, int, ctx->submatch_id);
+ STACK_PUSH(stack, int, PARSE_MARK_FOR_SUBMATCH);
+ ctx->submatch_id++;
+ }
+ STACK_PUSH(stack, int, 0); // bre_branch_begin
+ 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)
+ {
+ 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 `|'. */
+ bre_branch_begin = tre_stack_pop_int(stack);
+ if (
+#ifdef REG_LITERAL
+ !(ctx->cflags & REG_LITERAL) &&
+#endif /* REG_LITERAL */
+ ctx->cflags & (REG_EXTENDED | REG_ENHANCED))
+ STACK_PUSHX(stack, int, PARSE_UNION);
+ STACK_PUSHX(stack, int, bre_branch_begin);
+ 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. */
+ bre_branch_begin = tre_stack_pop_int(stack);
+ STACK_PUSHX(stack, int, PARSE_CATENATION);
+ STACK_PUSHX(stack, int, bre_branch_begin);
+ 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. */
+ bre_branch_begin = tre_stack_pop_int(stack);
+ STACK_PUSHX(stack, int, PARSE_POSTFIX);
+ STACK_PUSHX(stack, int, bre_branch_begin);
+ 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) ||
+ ((ctx->cflags & (REG_EXTENDED | REG_ENHANCED)) == REG_ENHANCED
+ && ctx->re + 1 < ctx->re_end && c == CHAR_BACKSLASH &&
+ *(ctx->re + 1) == CHAR_PIPE))
+ break;
+ if ((ctx->cflags & REG_EXTENDED
+ && c == CHAR_RPAREN && depth > 0)
+ || (!(ctx->cflags & REG_EXTENDED)
+ && ctx->re + 1 < ctx->re_end && c == CHAR_BACKSLASH
+ && *(ctx->re + 1) == CHAR_RPAREN))
+ {
+ if (!(ctx->cflags & REG_EXTENDED) && depth == 0)
+ return REG_EPAREN;
+ DPRINT(("tre_parse: group end: '%.*" STRF "'\n",
+ REST(ctx->re)));
+ depth--;
+ if (!(ctx->cflags & (REG_EXTENDED | REG_ENHANCED)))
+ ctx->re += 2;
+ break;
+ }
+#ifdef REG_LITERAL
+ }
+#endif /* REG_LITERAL */
+
+#ifdef REG_LEFT_ASSOC
+ if (ctx->cflags & REG_LEFT_ASSOC)
+ {
+ /* 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, 0); // bre_branch_begin
+ STACK_PUSHX(stack, int, PARSE_PIECE);
+ }
+ else
+#endif /* REG_LEFT_ASSOC */
+ {
+ /* Default case, 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, 0); // bre_branch_begin
+ 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 */
+ if (!(ctx->cflags & REG_EXTENDED))
+ {
+ if (*ctx->re != CHAR_BACKSLASH || ctx->re + 1 >= ctx->re_end)
+ break;
+ ctx->re++;
+ }
+ 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, (void *)ctx->re);
+ STACK_PUSHX(stack, voidptr, result);
+ STACK_PUSHX(stack, int, PARSE_POST_UNION);
+ /* We need to pass a boolean (eventually) to PARSE_ATOM to
+ indicate if this is the beginning of a BRE extended branch. */
+ STACK_PUSHX(stack, int, (ctx->cflags & (REG_EXTENDED | REG_ENHANCED)) == REG_ENHANCED); // bre_branch_begin
+ STACK_PUSHX(stack, int, PARSE_BRANCH);
+ ctx->re++;
+ break;
+
+ case CHAR_RPAREN:
+ ctx->re++;
+ break;
+
+ default:
+ if (!(ctx->cflags & REG_EXTENDED))
+ ctx->re--;
+ break;
+ }
+ break;
+
+ case PARSE_POST_UNION:
+ {
+ tre_ast_node_t *tmp_node;
+ tre_ast_node_t *tree = tre_stack_pop_voidptr(stack);
+ const tre_char_t *pipechar = tre_stack_pop_voidptr(stack);
+ /* error on empty expression at end of union */
+ if (pipechar == ctx->re - 1)
+ {
+ return REG_EMPTY;
+ }
+ 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 */
+ int minimal = (ctx->cflags & REG_UNGREEDY) ? 1 : 0;
+ int rep_min = 0;
+ int rep_max = -1;
+#ifdef TRE_DEBUG
+ int lbrace_off;
+#endif
+ 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;
+#ifdef TRE_DEBUG
+ const char *tstr = "star";
+ tmp_re = ctx->re;
+#endif
+
+ handle_plus_or_question:
+ /* error on iteration of raw assertion (not in subexpression) */
+ if (result->type == LITERAL && result->submatch_id < 0 &&
+ IS_ASSERTION((tre_literal_t *)result->obj))
+ {
+ if (!(ctx->cflags & REG_EXTENDED)) break;
+ return REG_BADRPT;
+ }
+ if (*ctx->re == CHAR_PLUS)
+ {
+ rep_min = 1;
+#ifdef TRE_DEBUG
+ tstr = "plus";
+#endif
+ }
+ if (*ctx->re == CHAR_QUESTIONMARK)
+ {
+ rep_max = 1;
+#ifdef TRE_DEBUG
+ tstr = "questionmark";
+#endif
+ }
+
+ if (ctx->cflags & REG_EXTENDED)
+ {
+ if (ctx->re + 1 < ctx->re_end)
+ {
+ if (*(ctx->re + 1) == CHAR_QUESTIONMARK)
+ {
+ /* Process the question mark only in enhanced mode.
+ Otherwise, the question mark is an error in ERE */
+ if (ctx->cflags & REG_ENHANCED)
+ {
+ minimal = !(ctx->cflags & REG_UNGREEDY);
+ ctx->re++;
+ }
+ else return REG_BADRPT;
+ }
+ else if (*(ctx->re + 1) == CHAR_STAR
+ || *(ctx->re + 1) == CHAR_PLUS)
+ {
+ /* These are reserved for future extensions. */
+ return REG_BADRPT;
+ }
+ }
+ }
+ else
+ {
+ if (ctx->re + 1 < ctx->re_end && *(ctx->re + 1) == CHAR_STAR)
+ {
+ /* This is reserved for future extensions. */
+ return REG_BADRPT;
+ }
+ if (ctx->re + 2 < ctx->re_end)
+ {
+ if (*(ctx->re + 1) == CHAR_BACKSLASH && *(ctx->re + 1) == CHAR_QUESTIONMARK)
+ {
+ /* Process the question mark only in enhanced mode.
+ Otherwise, the question mark is a literal in BRE */
+ if (ctx->cflags & REG_ENHANCED)
+ {
+ minimal = !(ctx->cflags & REG_UNGREEDY);
+ ctx->re += 2;
+ }
+ }
+ else if (*(ctx->re + 1) == CHAR_BACKSLASH && *(ctx->re + 2) == CHAR_PLUS)
+ {
+ /* This is reserved for future extensions. */
+ return REG_BADRPT;
+ }
+ }
+ }
+
+ if (minimal)
+ ctx->num_reorder_tags++;
+
+ DPRINT(("tre_parse: %s %s: '%.*" STRF "'\n",
+ minimal ? " minimal" : "greedy", tstr, REST(tmp_re)));
+ if (result == NULL)
+ {
+ if (ctx->cflags & REG_EXTENDED) return REG_BADRPT;
+ else goto parse_literal;
+ }
+ 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;
+
+ /* Set the iterator with a submatch id in the invisible range
+ * (which will be overridden if a real submatch is needed) */
+ result->submatch_id = ctx->submatch_id_invisible++;
+
+#if 0
+ /* We don't allow multiple postfixes, but this might be needed
+ to support approximate matching */
+ STACK_PUSHX(stack, int, PARSE_POSTFIX);
+#endif
+ }
+ break;
+
+ case CHAR_BACKSLASH:
+ /* "\{" is special without REG_EXTENDED */
+ /* "\+" and "\?" are special with REG_ENHANCED for BRE */
+ if (!(ctx->cflags & REG_EXTENDED)
+ && ctx->re + 1 < ctx->re_end)
+ {
+ switch (*(ctx->re + 1))
+ {
+ case CHAR_LBRACE:
+ ctx->re++;
+#ifdef TRE_DEBUG
+ lbrace_off = 2;
+#endif
+ goto parse_brace;
+ case CHAR_PLUS:
+ case CHAR_QUESTIONMARK:
+ if (ctx->cflags & REG_ENHANCED)
+ {
+#ifdef TRE_DEBUG
+ tmp_re = ctx->re;
+#endif
+ ctx->re++;
+ goto handle_plus_or_question;
+ }
+ break;
+ }
+ break;
+ }
+ else
+ break;
+
+ case CHAR_LBRACE:
+ {
+ int raw_assertion;
+
+ /* "{" is literal without REG_EXTENDED */
+ if (!(ctx->cflags & REG_EXTENDED))
+ break;
+#ifdef TRE_DEBUG
+ lbrace_off = 1;
+#endif
+
+ parse_brace:
+ /* error on iteration of raw assertion (not in subexpression),
+ but wait until after parsing bounds */
+ raw_assertion = (result->type == LITERAL
+ && result->submatch_id < 0
+ && IS_ASSERTION((tre_literal_t *)result->obj));
+ ctx->re++;
+
+ status = tre_parse_bound(ctx, &result);
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ /* For ERE, if status is REG_NOMATCH, this mean the lbrace
+ is to be treated as a literal. */
+ if (status == REG_NOMATCH)
+ {
+ ctx->re--;
+ break;
+ }
+#endif /* ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ DPRINT(("tre_parse: bound: '%.*" STRF "'\n",
+ REST(ctx->re - lbrace_off)));
+ if (status != REG_OK)
+ return status;
+ if (raw_assertion) return REG_BADRPT;
+
+ /* Set the iterator with a submatch id in the invisible range
+ * (which will be overridden if a real submatch is needed) */
+ if (result->type == ITERATION)
+ result->submatch_id = ctx->submatch_id_invisible++;
+
+#if 0
+ /* We don't allow multiple postfixes, but this might be needed
+ to support approximate matching */
+ STACK_PUSHX(stack, int, PARSE_POSTFIX);
+#endif
+ 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. */
+
+ /* The stack contains a boolean value, whether PARSE_ATOM is
+ being called just after the start of a group (left paren)
+ in a BRE */
+ bre_branch_begin = tre_stack_pop_int(stack);
+
+ /* 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|REG_ENHANCED)) ==
+ (REG_EXTENDED|REG_ENHANCED)
+ && *(ctx->re + 1) == CHAR_QUESTIONMARK)
+ {
+ int new_cflags = ctx->cflags;
+ int bit = 1;
+ int invisible_submatch = 0;
+ 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_LEFT_ASSOC
+ else if (*ctx->re == L'l')
+ {
+ DPRINT(("tre_parse: left assoc: '%.*" STRF "'\n",
+ REST(ctx->re)));
+ if (bit)
+ new_cflags |= REG_LEFT_ASSOC;
+ else
+ new_cflags &= ~REG_LEFT_ASSOC;
+ ctx->re++;
+ }
+#endif /* REG_LEFT_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
+ "', (invisible submatch %d)\n",
+ REST(ctx->re), ctx->submatch_id_invisible));
+ ctx->re++;
+ depth++;
+ invisible_submatch = 1;
+ 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_BADRPT;
+ }
+
+ /* Turn on the cflags changes for the rest of the
+ enclosing group. */
+ if (invisible_submatch)
+ {
+ STACK_PUSHX(stack, int, ctx->cflags);
+ STACK_PUSHX(stack, int, ctx->submatch_id_invisible);
+ STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH);
+ ctx->submatch_id_invisible++;
+ STACK_PUSHX(stack, int, 0); // bre_branch_begin
+ STACK_PUSHX(stack, int, PARSE_RE);
+ }
+ else {
+ STACK_PUSHX(stack, int, 0); // bre_branch_begin
+ STACK_PUSHX(stack, int, PARSE_ATOM);
+ }
+ ctx->cflags = new_cflags;
+ break;
+ }
+
+ if (ctx->cflags & REG_EXTENDED)
+ {
+ parse_bre_lparen:
+ 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->cflags);
+ STACK_PUSHX(stack, int, ctx->submatch_id);
+ STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH);
+ /* We need to pass a boolean (eventually) to PARSE_ATOM to
+ indicate if this is the beginning of a BRE group. */
+ STACK_PUSHX(stack, int, !(ctx->cflags & REG_EXTENDED));
+ STACK_PUSHX(stack, int, PARSE_RE);
+ ctx->submatch_id++;
+ depth++;
+ }
+ else
+ goto parse_literal;
+ break;
+
+ case CHAR_RPAREN: /* end of current subexpression */
+ if (ctx->cflags & REG_EXTENDED && depth > 0)
+ {
+ parse_bre_rparen_empty:
+ if (!(ctx->cflags & REG_EXTENDED) && depth == 0)
+ return REG_EPAREN;
+ 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:
+ /* Deal with "\(", "\)" or "\{" for BREs */
+ if (!(ctx->cflags & REG_EXTENDED)
+ && ctx->re + 1 < ctx->re_end)
+ {
+ if (*(ctx->re + 1) == CHAR_LPAREN)
+ {
+ ctx->re++;
+ goto parse_bre_lparen;
+ }
+ else if (*(ctx->re + 1) == CHAR_RPAREN)
+ {
+ ctx->re++;
+ goto parse_bre_rparen_empty;
+ }
+ if (*(ctx->re + 1) == CHAR_LBRACE) goto parse_literal;
+ }
+
+ if (ctx->re + 1 >= ctx->re_end)
+ /* Trailing backslash. */
+ return REG_EESCAPE;
+
+ if (!(ctx->cflags & REG_ENHANCED))
+ {
+ DPRINT(("tre_parse: unenhanced bleep: '%.*" STRF "'\n", REST(ctx->re)));
+ ctx->re++;
+ goto unenhanced_backslash;
+ }
+
+ /* 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;
+ }
+ }
+
+#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, 0);
+ 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_l(ctx->re[0], ctx->loc) &&
+ ctx->re < ctx->re_end)
+ {
+ tmp[0] = (char)ctx->re[0];
+ ctx->re++;
+ }
+ if (tre_isxdigit_l(ctx->re[0], ctx->loc) &&
+ 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_l(ctx->re[0], ctx->loc))
+ {
+ 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:
+ unenhanced_backslash:
+ if ((ctx->cflags & (REG_EXTENDED | REG_ENHANCED)) !=
+ REG_EXTENDED &&
+ tre_isdigit_l(*ctx->re, ctx->loc) && *ctx->re != L'0')
+ {
+ /* Back reference (only in BRE or enhanced). */
+ 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;
+
+ /* Set the backref with a submatch id in the invisible
+ * range (which will be overridden if a real submatch
+ * is needed) */
+ result->submatch_id = ctx->submatch_id_invisible++;
+
+ ctx->position++;
+ ctx->num_reorder_tags++;
+ 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, at the
+ beginning of the RE and after \( is BREs. It is also
+ special in enhanced BREs at the beginning of each branches
+ of a union */
+ if (ctx->cflags & REG_EXTENDED
+ || bre_branch_begin
+ || 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;
+ if (ctx->re < ctx->re_end)
+ {
+ STACK_PUSHX(stack, int, 0);
+ STACK_PUSHX(stack, int, PARSE_ATOM);
+ }
+ else
+ {
+ result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
+ if (!result) return REG_ESPACE;
+ }
+ 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), which is an error.
+ Iterations of an empty expression is also an error. */
+#ifdef REG_LITERAL
+ if (!(ctx->cflags & REG_LITERAL))
+ {
+#endif /* REG_LITERAL */
+ /* error on end of string */
+ if (ctx->re >= ctx->re_end) return depth > 0 ? REG_EPAREN
+ : REG_EMPTY;
+ /* error on unions and iterations of empty expressions */
+ if (ctx->cflags & REG_EXTENDED)
+ {
+ if (ctx->re < ctx->re_end)
+ {
+ if (*ctx->re == CHAR_PIPE) return REG_EMPTY;
+ if (*ctx->re == CHAR_LBRACE)
+ {
+ ctx->re++;
+ empty_parse_bound:
+ /* We need to parse the bound first and return
+ any error, before returning REG_BADRPT */
+ status = tre_parse_bound(ctx, NULL);
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ /* For ERE, if REG_NOMATCH is returned, we
+ treat the lbrace as a literal. */
+ if (status == REG_NOMATCH)
+ {
+ ctx->re--;
+ /* Drop down to literal-handling code */
+ }
+ else
+ {
+#endif /* ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ if (status != REG_OK)
+ return status;
+ return REG_BADRPT;
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ }
+#endif /* ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ }
+#ifdef ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND
+ else
+#endif /* ERE_LITERAL_LBRACE_ON_NON_NUMERIC_BOUND */
+ if (*ctx->re == CHAR_STAR
+ || *ctx->re == CHAR_PLUS
+ || *ctx->re == CHAR_QUESTIONMARK)
+ {
+ return REG_BADRPT;
+ }
+ }
+ }
+ else if (ctx->re + 1 < ctx->re_end
+ && *ctx->re == CHAR_BACKSLASH
+ && *(ctx->re + 1) == CHAR_LBRACE)
+ {
+ ctx->re += 2;
+ goto empty_parse_bound;
+ }
+#ifdef REG_LITERAL
+ }
+#endif /* REG_LITERAL */
+
+ 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_l(*ctx->re, ctx->loc) ||
+ tre_islower_l(*ctx->re, ctx->loc)))
+ {
+ 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_l(*ctx->re, ctx->loc),
+ tre_toupper_l(*ctx->re, ctx->loc),
+ ctx->position);
+ if (!tmp1)
+ return REG_ESPACE;
+ tmp2 = tre_ast_new_literal(ctx->mem,
+ tre_tolower_l(*ctx->re, ctx->loc),
+ tre_tolower_l(*ctx->re, ctx->loc),
+ 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);
+
+ ctx->cflags = tre_stack_pop_int(stack); /* restore cflags */
+ if (result->submatch_id >= 0 &&
+ result->submatch_id < SUBMATCH_ID_INVISIBLE_START)
+ {
+ tre_ast_node_t *n, *tmp_node;
+ if (submatch_id >= SUBMATCH_ID_INVISIBLE_START)
+ break;
+ 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;
+ if (submatch_id < SUBMATCH_ID_INVISIBLE_START)
+ result->num_submatches++;
+ break;
+ }
+
+ default:
+ assert(0);
+ break;
+ }
+ }
+
+ /* Check for missing closing parentheses. */
+ if (depth > 0)
+ return REG_EPAREN;
+
+ ctx->result = result;
+
+ return REG_OK;
+}
+
+/* EOF */
projects / apple / libc.git / blobdiff