/* * $Id$ * Copyright (c) 2006-2019 Chung, Hyung-Hwan. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* tre-parse.c - Regexp parser This is the license, copyright notice, and disclaimer for TRE, a regex matching package (library and tools) with support for approximate matching. Copyright (c) 2001-2009 Ville Laurikari All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* 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. */ #include "tre.h" #include #include #include "tre-ast.h" #include "tre-stack.h" #include "tre-parse.h" /* Characters with special meanings in regexp syntax. */ #define CHAR_PIPE QSE_T('|') #define CHAR_LPAREN QSE_T('(') #define CHAR_RPAREN QSE_T(')') #define CHAR_LBRACE QSE_T('{') #define CHAR_RBRACE QSE_T('}') #define CHAR_LBRACKET QSE_T('[') #define CHAR_RBRACKET QSE_T(']') #define CHAR_MINUS QSE_T('-') #define CHAR_STAR QSE_T('*') #define CHAR_QUESTIONMARK QSE_T('?') #define CHAR_PLUS QSE_T('+') #define CHAR_PERIOD QSE_T('.') #define CHAR_COLON QSE_T(':') #define CHAR_EQUAL QSE_T('=') #define CHAR_COMMA QSE_T(',') #define CHAR_CARET QSE_T('^') #define CHAR_DOLLAR QSE_T('$') #define CHAR_BACKSLASH QSE_T('\\') #define CHAR_HASH QSE_T('#') #define CHAR_TILDE QSE_T('~') /* 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 } }; static QSE_INLINE int xdigit_to_num (qse_char_t c) { return QSE_XDIGITTONUM (c); } /* 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(mem->mmgr, 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; } #if defined(QSE_CHAR_IS_MCHAR) /* 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; /* QSE: deleted */ /*assert(TRE_MB_CUR_MAX == 1);*/ /* END QSE */ 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; } #endif static int tre_compare_items(const void *a, const void *b, void* ctx) { 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; } /* 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; } /* QSE: handle \ as an escaper */ else if (re + 1 < ctx->re_end && *re == CHAR_BACKSLASH) { /* escaped character inside [] */ min = max = *(re + 1); re += 2; } /* END QSE */ 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) { 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) { /* QSE: bug fix of not checking ending ] */ if (*(endptr + 1) != CHAR_RBRACKET) status = REG_ECTYPE; else { /* END QSE */ len = MIN(endptr - re - 2, 63); if (qse_strntoctype (re + 2, len, &class) <= -1) status = REG_ECTYPE; /* Optimize character classes for 8 bit character sets. */ #if defined(QSE_CHAR_IS_MCHAR) /* QSE: not possible to count on MB_CUR_MAX since * this library is designed to support per-object * or per-context character encoding using qse_cmgr_t */ /* if (status == REG_OK && TRE_MB_CUR_MAX == 1) */ /* END QSE */ if (status == REG_OK) { status = tre_expand_ctype(ctx->mem, class, items, &i, &max_i, ctx->cflags); class = (tre_ctype_t)0; skip = 1; } #endif 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(ctx->mem->mmgr, 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) qse_qsort(items, (unsigned)i, sizeof(*items), tre_compare_items, QSE_NULL); 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(ctx->mem->mmgr, 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 >= QSE_T('0') && *r <= QSE_T('9')) { if (num < 0) num = 0; num = num * 10 + *r - QSE_T('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 >= QSE_T('0') && *r <= QSE_T('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; hyunghwan.chung: this original check still allows something like {100000,} while it does not allow {1,256}. Why is RE_DUP_MAX necessary? */ if ((max >= 0 && min > 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 = QSE_TYPE_MAX(int); 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 = QSE_TYPE_MAX(int); 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 = QSE_TYPE_MAX(int); 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 = QSE_TYPE_MAX(int); approx = 1; break; case CHAR_COMMA: r++; break; case QSE_T(' '): r++; break; case QSE_T('}'): 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 QSE_T(' '): r++; break; case QSE_T('<'): DPRINT(("tre_parse: max cost: '%.*" STRF "'\n", REST(r))); r++; while (*r == QSE_T(' ')) r++; cost_max = tre_parse_int(&r, ctx->re_end); if (cost_max < 0) cost_max = QSE_TYPE_MAX(int); else cost_max--; approx = 1; break; case CHAR_COMMA: r++; done = 1; break; default: if (*r >= QSE_T('0') && *r <= QSE_T('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 QSE_T('i'): /* Insert cost */ DPRINT(("tre_parse: ins cost: '%.*" STRF "'\n", REST(sr))); r++; cost_ins = cost; costs_set = 1; break; case QSE_T('d'): /* Delete cost */ DPRINT(("tre_parse: del cost: '%.*" STRF "'\n", REST(sr))); r++; cost_del = cost; costs_set = 1; break; case QSE_T('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++; } /* QSE - commented out for minimal impact on backward compatibility. * X{x,y}* X{x,y}+ */ #if 0 else if (*r == CHAR_STAR || *r == CHAR_PLUS) { /* These are reserved for future extensions. */ return REG_BADRPT; } #endif } /* 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 = QSE_TYPE_MAX(int); } if (limit_del == TRE_PARAM_UNSET) { if (cost_del == TRE_PARAM_UNSET) limit_del = 0; else limit_del = QSE_TYPE_MAX(int); } if (limit_subst == TRE_PARAM_UNSET) { if (cost_subst == TRE_PARAM_UNSET) limit_subst = 0; else limit_subst = QSE_TYPE_MAX(int); } } if (cost_max == TRE_PARAM_UNSET) cost_max = QSE_TYPE_MAX(int); if (limit_err == TRE_PARAM_UNSET) limit_err = QSE_TYPE_MAX(int); 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: /* QSE - added this label */ parse_star: /* END QSE */ { 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) /* QSE: case CHAR_PLUS fell through down here */ rep_min = 1; if (*ctx->re == CHAR_QUESTIONMARK) /* QSE: case CHAR_QUESTIONMARK fell though down here */ rep_max = 1; #ifdef TRE_DEBUG tmp_re = ctx->re; #endif if (ctx->re + 1 < ctx->re_end) { if (*(ctx->re + 1) == CHAR_QUESTIONMARK) /* QSE: +?, ??, *? */ { minimal = !(ctx->cflags & REG_UNGREEDY); ctx->re++; } /* QSE - TRE has provisions for ** or *+ as a special repetition operator. * however, that seems to break backward compatibility. * '+' in 'a*+' is not treated as a normal character with the * following block enabled. So let me comment it out */ #if 0 else if (*(ctx->re + 1) == CHAR_STAR || *(ctx->re + 1) == CHAR_PLUS) { /* These are reserved for future extensions. */ return REG_BADRPT; } #endif } 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 */ /* QSE - also handle \+ and \? */ /* if (!(ctx->cflags & REG_EXTENDED) && ctx->re + 1 < ctx->re_end && *(ctx->re + 1) == CHAR_LBRACE) { ctx->re++; goto parse_brace; } else break; */ if (!(ctx->cflags & REG_EXTENDED) && ctx->re + 1 < ctx->re_end) { if (*(ctx->re + 1) == CHAR_LBRACE) { ctx->re++; goto parse_brace; } else if (*(ctx->re + 1) == CHAR_PLUS || *(ctx->re + 1) == CHAR_QUESTIONMARK) { ctx->re++; goto parse_star; } } break; /* END QSE */ case CHAR_LBRACE: /* "{" is literal without REG_EXTENDED */ if (!(ctx->cflags & REG_EXTENDED)) break; /* QSE */ if (ctx->cflags & REG_NOBOUND) break; /* END QSE */ 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. */ /* QSE: added ctx->cflags & REG_NONSTDEXT */ if ((ctx->cflags & REG_NONSTDEXT) && (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 == QSE_T('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 == QSE_T('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 == QSE_T('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 == QSE_T('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++; /* QSE: added ctx->cflags & REG_NONSTDEXT */ if ((ctx->cflags & REG_NONSTDEXT) && ctx->re + 2 < ctx->re_end && *(ctx->re + 1) == CHAR_QUESTIONMARK && *(ctx->re + 2) == CHAR_COLON) { /* QSE: \(?: or (?: depending on REG_EXTENDED */ 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, QSE_COUNTOF(buf)); if (buf[0] != 0) { tre_parse_ctx_t subctx; QSE_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) == QSE_T('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 QSE_T('b'): result = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB, -1); ctx->re++; break; case QSE_T('B'): result = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB_NEG, -1); ctx->re++; break; case QSE_T('<'): result = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOW, -1); ctx->re++; break; case QSE_T('>'): result = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOW, -1); ctx->re++; break; case QSE_T('x'): ctx->re++; if (ctx->re[0] != CHAR_LBRACE && ctx->re < ctx->re_end) { /* QSE */ #if 0 /* 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); #endif long val = 0; int tmp; if ((tmp = xdigit_to_num(ctx->re[0])) >= 0 && ctx->re < ctx->re_end) { val = val * 16 + tmp; ctx->re++; } if ((tmp = xdigit_to_num(ctx->re[1])) >= 0 && ctx->re < ctx->re_end) { val = val * 16 + tmp; ctx->re++; } 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. */ /* QSE */ #if 0 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); #endif long val = 0; int tmp; ctx->re++; while (ctx->re_end - ctx->re >= 0) { if (ctx->re[0] == CHAR_RBRACE) break; tmp = xdigit_to_num(ctx->re[0]); if (tmp >= 0) { val = val * 16 + tmp; ctx->re++; continue; } return REG_EBRACE; } 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 - QSE_T('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; /* exclude new line */ tmp1 = tre_ast_new_literal(ctx->mem, 0, QSE_T('\n') - 1, ctx->position); if (!tmp1) return REG_ESPACE; tmp2 = tre_ast_new_literal(ctx->mem, QSE_T('\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 { /* all characters */ 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) == QSE_T('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 /* QSE */ /*|| *ctx->re == CHAR_LBRACE*/ || (*ctx->re == CHAR_LBRACE && !(ctx->cflags & REG_NOBOUND)) /* END QSE */ || *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 */