2005-02-10 Paolo Bonzini <bonzini@gnu.org>
* lib/regcomp.c (lower_subexp): Do not optimize empty
subexpressions even with REG_NOSUB.
* testsuite/SPENCER.tests: Add a previously failing testcase.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-43
2005-01-26 Paolo Bonzini <bonzini@gnu.org>
* posix/regcomp.c (peek_token): Fix ctx_type for \B.
(parse_expression): Lower token->opr.ctx_type == NOT_WORD_DELIM.
* posix/regex_internal.h (re_context_type): Add NOT_WORD_DELIM
and OUTSIDE_WORD.
* posix/PCRE.tests: Adjust \B tests to check if it matches outside
a word.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-36
2005-01-25 Paolo Bonzini <bonzini@gnu.org>
* sed/regexp.c: Fix building on GCC 2.95 and earlier.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-35
2004-12-31 Paolo Bonzini <bonzini@gnu.org>
* regcomp.c (calc_inveclosure): Return reg_errcode_t.
Initialize the node sets in dfa->inveclosures.
(analyze): Initialize inveclosures only if it is needed.
Check errors from calc_inveclosure.
* regex_internal.c (re_dfa_add_node): Do not initialize
the inveclosure node set.
* regexec.c (re_search_internal): If nmatch includes unused
subexpressions, reset them to { rm_so: -1, rm_eo: -1 } here.
Limit to preg->re_nsubs the nmatch that is passed to set_regs.
(set_regs): Remove the real_nmatch variable, the nmatch
parameter now is <= preg->re_nsubs.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-34
2004-12-27 Paolo Bonzini <bonzini@gnu.org>
* lib/regexec.c (transit_state_mb): Do not examine nodes where
the ACCEPT_MB is not set.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-30
2004-12-13 Paolo Bonzini <bonzini@gnu.org>
Separate parsing and creation of the NFA. Avoided recursion on
the (very unbalanced) parse tree.
* regcomp.c (struct subexp_optimize, analyze_tree, calc_epsdest,
re_dfa_add_tree_node, mark_opt_subexp_iter): Removed.
(optimize_subexps, duplicate_tree, calc_first, calc_next,
mark_opt_subexp): Rewritten.
(preorder, postorder, lower_subexps, lower_subexp, link_nfa_nodes,
create_token_tree, free_tree, free_token): New.
(analyze): Accept a regex_t *. Invoke the passes via the preorder and
postorder generic visitors. Do not initialize the fields in the
re_dfa_t that represent the transitions.
(free_dfa_content): Use free_token.
(re_compile_internal): Analyze before UTF-8 optimizations. Do not
include optimization of subexpressions.
(create_initial_state): Fetch the DFA node index from the first node's
bin_tree_t *.
(optimize_utf8): Abort on unexpected nodes, including OP_DUP_QUESTION.
Return on COMPLEX_BRACKET.
(duplicate_node_closure): Fix comment.
(duplicate_node): Do not initialize the fields in the
re_dfa_t that represent the transitions.
(calc_eclosure, calc_inveclosure): Do not handle OP_DELETED_SUBEXP.
(create_tree): Remove final argument. All callers adjusted. Rewritten
to use create_token_tree.
(parse_reg_exp, parse_branch, parse_expression, parse_bracket_exp,
build_charclass_op): Use create_tree or create_token_tree instead
of re_dfa_add_tree_node.
(parse_dup_op): Likewise. Also free the tree using free_tree for
"<re>{0}", and lower OP_DUP_QUESTION to OP_ALT: "a?" is equivalent
to "a|". Adjust invocation of mark_opt_subexp.
(parse_sub_exp): Create a single SUBEXP node.
* regex_internal.c (re_dfa_add_node): Remove last parameter, always
perform as if it was 1. Do not initialize OPT_SUBEXP and DUPLICATED,
and initialize the DFA fields representing the transitions.
* regex_internal.h (re_dfa_add_node): Adjust prototype.
(re_token_type_t): Move OP_DUP_PLUS and OP_DUP_QUESTION to the tokens
section. Add a tree-only code SUBEXP. Remove OP_DELETED_SUBEXP.
(bin_tree_t): Include a full re_token_t for TOKEN. Turn FIRST and
NEXT into pointers to trees. Remove ECLOSURE.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-29
2004-12-07 Paolo Bonzini <bonzini@gnu.org>
* regexec.c (proceed_next_node): Simplify treatment of epsilon
nodes. Pass the pushed node to push_fail_stack.
(push_fail_stack): Accept a single node rather than an array
of two epsilon destinations.
(build_sifted_states): Only walk non-epsilon nodes.
(check_arrival): Don't pass epsilon nodes to
check_arrival_add_next_nodes.
(check_arrival_add_next_nodes) [DEBUG]: Abort if an epsilon node is
found.
(check_node_accept): Do expensive checks later.
(add_epsilon_src_nodes): Cache result of merging the inveclosures.
* regex-internal.h (re_dfastate_t): Add non_eps_nodes and inveclosure.
(re_string_elem_size_at, re_string_char_size_at, re_string_wchar_at,
re_string_context_at, re_string_peek_byte_case,
re_string_fetch_byte_case, re_node_set_compare, re_node_set_contains):
Declare as pure.
* regex-internal.c (create_newstate_common): Remove.
(register_state): Move part of it here. Initialize non_eps_nodes.
(free_state): Free inveclosure and non_eps_nodes.
(create_cd_newstate, create_ci_newstate): Allocate the new
re_dfastate_t here.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-28
2004-12-03 Paolo Bonzini <bonzini@gnu.org>
* regcomp.c (peek_token, parse_expression, build_charclass_op): Do
not set accept_mb in the token.
(parse_bracket_exp): Do not modify existing DFA nodes.
* regex-internal.c (re_node_set_insert_last): Remove unused variable.
(re_dfa_add_node): Set accept_mb in the DFA node.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-27
2004-11-30 Paolo Bonzini <bonzini@gnu.org>
* posix/regexec.c (check_dst_limits_calc_pos_1): Check
for bkref_idx == -1, and don't recurse in that case.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-24
2004-09-11 Paolo Bonzini <bonzini@gnu.org>
* posix/regex_internal.h (struct re_backref_cache_entry):
Add a map of reachable subexpression nodes from each backreference
cache entry.
* posix/regexec.c (check_dst_limits_calc_pos_1): Use the map
to cut recursive paths. Make exit condition more precise.
(match_ctx_add_entry): Initialize the map.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-17
2004-09-08 Paolo Bonzini <bonzini@gnu.org>
* regcomp.c (init_dfa): Get the codeset name outside glibc as
well. Check if it is spelled UTF8 as well as UTF-8, and check
case-insensitively. Set dfa->map_notascii manually when outside
glibc.
* regex_internal.c (build_wcs_upper_buffer) [!_LIBC]: Enable
optimizations based on map_notascii.
* regex_internal.h [HAVE_LANGINFO_H || HAVE_LANGINFO_CODESET
|| _LIBC]: Include langinfo.h.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-14
2004-11-03 Paolo Bonzini <bonzini@gnu.org>
* regex_internal.h (struct re_backref_cache_entry): Add "more" field.
* regexec.c (check_dst_limits): Hoist computation of the source
and destination bkref_idx out of the loop. Pass it to
check_dst_limits_calc_pos.
(check_dst_limits_calc_pos_1): New function, containing the recursive
loop of check_dst_limits_calc_pos; uses the "more" field of
struct re_backref_cache to control the loop.
(check_dst_limits_calc_pos): Store into "boundaries" the position
relative to lim's start and end positions. Do not accept eclosures,
accept bkref_idx instead. Call check_dst_limits_calc_pos_1 to do the
work.
(sift_states_bkref): Use the "more" field of struct re_backref_cache
to control the loop. A big "if" was turned into a continue and the
function was reindented.
(get_subexp): Use the "more" field of struct re_backref_cache
to control the loop.
(match_ctx_add_entry): Initialize the bkref_ents' "more" field.
(search_cur_bkref_entry): Return -1 if out of bounds.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-12
2004-11-03 Paolo Bonzini <bonzini@gnu.org>
* regexec.c (empty_set): Remove.
(sift_states_backward): Remove cur_src variable. Move inner loop
to build_sifted_states.
(build_sifted_states): Extract from sift_states_backward. Do not
use empty_set.
(update_cur_sifted_state): Do not use empty_set. Special case
dest_nodes->nelem == 0.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-11
2004-11-03 Paolo Bonzini <bonzini@gnu.org>
* regex_internal.h (struct re_backref_cache): Remove flag field.
(struct re_sift_context_t): Remove cur_bkref, cls_subexp_idx,
check_subexp fields. Move limits last.
* regex.c (match_ctx_clear_flag): Remove.
(sift_ctx_init): Remove check_subexp parameter. Do not set removed
fields. Callers adjusted.
(expand_bkref_cache): Remove last_str parameter. Callers adjusted.
(re_search_internal): Remove fast_translate variable.
(update_cur_sifted_state): Pass candidates as the final parameter
to sift_states_bkref.
(sift_states_bkref): Change last unused parameter to be "candidates",
do not fetch candidates into a local variable.
Remove dead test for "node == sctx->bkref", and the cur_bkref_idx
variable.
Remove loops that set/reset the flag field of backref cache entries.
(check_arrival_add_next_nodes): Use a signed int to hold the return
value of re_node_set_insert.
(group_nodes_into_DFAstates): Likewise.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-10
2004-10-27 Paolo Bonzini <bonzini@gnu.org>
* regex_internal.h (struct re_dfastate_t): Make
word_trtable a pointer to the 512-item transition table.
* regexec.c (build_trtable): Fill in either state->trtable
or state->word_trtable. Return a boolean indicating success.
(transit_state): Expect state->trtable to be a 256-item
transition table. Reorganize code to have less tests in
the common case, and to save an indentation level.
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-5