- 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;
- wchar_t wc;
- int clen;
-
- 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;
-
-
- /* 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 `|'. */
- if (ctx->cflags & REG_EXTENDED)
- 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. */
- 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)
- break;
- c = *ctx->re;
- 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;
- depth--;
- if (!(ctx->cflags & REG_EXTENDED))
- ctx->re += 2;
- break;
- }
-
- {
- /* 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:
- switch (*ctx->re)
- {
- case CHAR_PIPE:
- 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. */
- switch (*ctx->re)
- {
- case CHAR_PLUS:
- case CHAR_QUESTIONMARK:
- if (!(ctx->cflags & REG_EXTENDED))
- break;
- /*FALLTHROUGH*/
- case CHAR_STAR:
- {
- tre_ast_node_t *tmp_node;
- int minimal = 0;
- int rep_min = 0;
- int rep_max = -1;
-
- if (*ctx->re == CHAR_PLUS)
- rep_min = 1;
- if (*ctx->re == CHAR_QUESTIONMARK)
- rep_max = 1;
-
- ctx->re++;
- tmp_node = tre_ast_new_iter(ctx->mem, result, rep_min, rep_max,
- minimal);
- if (tmp_node == NULL)
- return REG_ESPACE;
- result = tmp_node;
- STACK_PUSHX(stack, int, PARSE_POSTFIX);
- }
- break;
-
- case CHAR_BACKSLASH:
- /* "\{" is special without REG_EXTENDED */
- if (!(ctx->cflags & REG_EXTENDED)
- && *(ctx->re + 1) == CHAR_LBRACE)
- {
- ctx->re++;
- goto parse_brace;
- }
- else
- break;
-
- case CHAR_LBRACE:
- /* "{" is literal without REG_EXTENDED */
- if (!(ctx->cflags & REG_EXTENDED))
- break;
-
- parse_brace:
- ctx->re++;