43 Commits
Author SHA1 Message Date
Paolo Bonzini 59ee990c6b gnulibify part 2, use gnulib-tool in autoboot and remove PO files from repo
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-76
2008-01-09 16:12:14 +01:00
Paolo Bonzini e2fe13c4f8 gnulib .gitignore files 2008-01-09 16:12:14 +01:00
Paolo Bonzini ac9a20b3fb gnulibify and add ACL support
2006-09-24  Paolo Bonzini  <bonzini@gnu.org>

	* sed/execute.c: Support ACLs.
	* lib/utils.c: Move...
	* sed/utils.c: ... here, and remove xmalloc.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-74
2008-01-09 16:12:13 +01:00
Paolo Bonzini 3a8e165ab0 treat cygwin CR/LF correctly (and by design, not by chance)
2006-08-03  Paolo Bonzini  <bonzini@gnu.org>
            Corinna Vinschen  <vinschen@redhat.com>

        * lib/getline.c (getline): Remove Windows special casing.
        * lib/utils.c (register_open_file, ck_fdopen): New.
        (ck_fopen, ck_mkstemp): Use register_open_file.
        * lib/utils.h (ck_fdopen): New.
        * sed/execute.c (open_next_file): Reopen stdin.
        * sed/sed.h (read_mode): New.
        * sed/sed.c (read_mode): New.
        (main): Set it on --binary.
        (usage): Document --binary.
        * sed/compile.c (get_openfile): Change second argument to char
        and turn it into a string within the function.  Adjust callers.
        * sed/execute.c (dump_append_queue, open_next_file): Use it
        as mode for ck_fopen.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-71
2008-01-09 16:12:11 +01:00
Paolo Bonzini 4ca34ac568 don't rely on malloc(0) != NULL
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-69
2008-01-09 16:12:09 +01:00
Paolo Bonzini ec9561cfa4 robustify bootstrap process, ensure distribution of updated boostrap.sh
2006-07-13  Paolo Bonzini  <bonzini@gnu.org>

	* bootstrap.sh.in: Add a few autoconfy tests.
	* Makefile.am: Update distributed bootstrap.sh.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-68
2008-01-09 16:12:08 +01:00
Paolo Bonzini 3cfe7fdf8a Fix compilation on non-GCC compilers, update po files
2006-05-15  Hans-Bernhard Bröker <broeker@physik.rwth-aachen.de>

	* sed/basicdefs.h (OB_MALLOC): Turn VCAST into void * cast.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-66
2008-01-09 16:12:07 +01:00
Paolo Bonzini 811c3446c6 merge with glibc regex
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-59
2008-01-09 16:12:01 +01:00
Paolo Bonzini 6cf9fe5b1b add LANG_SORBIAN and other mingw fixes
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-57
2008-01-09 16:11:59 +01:00
Paolo Bonzini 912c1770ac update regex from upstream
2005-09-07  Paolo Bonzini  <bonzini@gnu.org>

	* lib/regcomp.c: Update from upstream.
	* lib/regex.c: Update from upstream.
	* lib/regex_.h: Update from upstream.
	* lib/regex_internal.c: Update from upstream.
	* lib/regex_internal.h: Update from upstream.
	* lib/regexec.c: Update from upstream.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-54
2008-01-09 16:11:57 +01:00
Paolo Bonzini bdbfe6d711 merge regex with glibc and adjust doc/.arch-inventory
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-51
2008-01-09 16:11:54 +01:00
Paolo Bonzini 584e5cedc2 more updates to the FSF address
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-50
2008-01-09 16:11:53 +01:00
Paolo Bonzini 07e543c45f update FSF address
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-49
2008-01-09 16:11:52 +01:00
Paolo Bonzini 20a67b75e7 fix crash on /\(\)/x
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
2008-01-09 16:11:48 +01:00
Paolo Bonzini cf7d4aadd2 include config.h from within obstack.h
2005-02-08  Paolo Bonzini  <bonzini@gnu.org>

	* lib/obstack.h: include config.h.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-41
2008-01-09 16:11:46 +01:00
Paolo Bonzini 5b8a413620 finally resync with glibc
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-38
2008-01-09 16:11:44 +01:00
Paolo Bonzini 87cdf72890 fix meaning of \B
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
2008-01-09 16:11:43 +01:00
Paolo Bonzini b48e80e8ad prepare for 4.1.4 release
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
2008-01-09 16:11:42 +01:00
Paolo Bonzini 32cf31f2ba compute inveclosure only if actually needed.
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
2008-01-09 16:11:41 +01:00
Paolo Bonzini 65048613e4 speed up transit_state_mb
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
2008-01-09 16:11:38 +01:00
Paolo Bonzini 312aa45e81 separate parsing and creation of the NFA. Avoid recursion on the parse tree.
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
2008-01-09 16:11:38 +01:00
Paolo Bonzini 827706c007 speed up parentheses
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
2008-01-09 16:11:37 +01:00
Paolo Bonzini 14f43c2486 Fix bugs in the accept_mb optimization.
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
2008-01-09 16:11:36 +01:00
Paolo Bonzini 52e232ab96 do not make single-byte searches go through slow MBCS paths
2004-01-12  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regcomp.c (peek_token, parse_bracket_exp, build_charclass_op)
	[RE_ENABLE_I18N]: Initialize the tokens' accept_mb field.
	* posix/regex_internal.c (create_ci_newstate, create_cd_newstate)
	[RE_ENABLE_I18N]: Initialize the DFA state's accept_mb field
	from the nodes'.
	* posix/regex_internal.h (re_token_t) [RE_ENABLE_I18N]: Add the
	accept_mb bitfield.
	(ACCEPT_MB_NODE): Remove.
	* posix/regexec.c (transit_state_mb, check_arrival_add_next_nodes,
	proceed_next_node, build_sifted_states): Look at the nodes' accept_mb
	field.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-26
2008-01-09 16:11:36 +01:00
Paolo Bonzini 8a00600bfc simplify handling of subexpressions
2004-12-01  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regcomp.c (free_dfa_content, init_dfa): Remove
	references to re_dfa_t's subexps field.
	(parse_sub_exp, parse_expression): Do not use it.  Use
	completed_bkref_map instead.
	(create_initial_state, peek_token): Store a backreference \N
	with opr.idx = N-1.
	* posix/regexec.c (proceed_next_node, check_dst_limits,
	get_subexp): Likewise.
	(check_subexp_limits): Remove useless condition.
	* posix/regex_internal.h (re_subexp_t): Remove.
	(re_dfa_t): Remove subexps and subexps_alloc field, add
	completed_bkref_map.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-25
2008-01-09 16:11:35 +01:00
Paolo Bonzini d7af1f9383 fix off by one error in check_dst_limits_calc_pos_1
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
2008-01-09 16:11:34 +01:00
Paolo Bonzini deb1e06415 speed up .{1,2048}
2004-11-23  Paolo Bonzini  <bonzini@gnu.org>

	* regcomp.c (analyze_tree): Always call calc_epsdest.
	(calc_inveclosure): Use re_node_set_insert_last.
	(parse_dup_op): Lower X{1,5} to (X(X(X(XX?)?)?)?)?
	rather than X?X?X?X?X?.
	* regex_internal.h (re_node_set_insert_last): New declaration.
	* regex_internal.c (re_node_set_insert_last): New function.
	* PCRE.tests: Add testcases.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-22
2008-01-09 16:10:55 +01:00
Paolo Bonzini 2e543b5d13 restore transit_state optimization, lost in previous checkin
previous checkin was a merge from glibc

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-21
2008-01-09 16:10:54 +01:00
Paolo Bonzini 611e77d579 git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-20 2008-01-09 16:10:54 +01:00
Paolo Bonzini 8da18b06bb cache result of check_dst_limits_calc_pos_1
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
2008-01-09 16:10:52 +01:00
Paolo Bonzini a525606abd merge from glibc
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-16
2008-01-09 16:10:51 +01:00
Paolo Bonzini 6a02cd80dc use utf8 optimizations outside glibc
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
2008-01-09 16:10:49 +01:00
Paolo Bonzini a9676b50f0 speedup regex by up to 50%
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
2008-01-09 16:10:48 +01:00
Paolo Bonzini 8ace1b487a Remove empty_set variable to speed up regexec.c
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
2008-01-09 16:10:47 +01:00
Paolo Bonzini 38367c6269 regex dead code removal
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
2008-01-09 16:10:47 +01:00
Paolo Bonzini 8219cef2eb fix build when _REGEX_RE_COMP is defined
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-8
2008-01-09 16:10:45 +01:00
Paolo Bonzini 21555923d4 fix builds with included gettext
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-6
2008-01-09 16:10:44 +01:00
Paolo Bonzini 974f9f12da speedup transit_state
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
2008-01-09 16:10:43 +01:00
Paolo Bonzini 7246bc1021 speedup fastmap searching, special casing forward searches
2004-10-27  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regexec.c (acquire_init_state_context): Do not
	always inline.
	(transit_state): Remove the check for out-of-bounds buffers.
	(check_matching): Check here for out-of-bounds buffers.
	(re_search_internal): Store into match_kind a set of bits
	indicating which incantation of fastmap scanning must be
	used.  Use a switch statement instead of multiple ifs.
	Exit the final "for (;;)" with goto free_return unless
	the match succeeded, thus simplifying some conditionals.

diff -ru lib_mio/regexec.c lib/regexec.c
*** lib_mio/regexec.c	2004-10-27 13:03:14.000000000 +0200
--- lib/regexec.c	2004-10-27 12:56:46.000000000 +0200
***************
*** 57,63 ****
  			      int nregs, int regs_allocated) internal_function;
  static inline re_dfastate_t *acquire_init_state_context
       (reg_errcode_t *err, const re_match_context_t *mctx, int idx)
!      __attribute ((always_inline)) internal_function;
  static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
       internal_function;
  static int check_matching (re_match_context_t *mctx, int fl_longest_match,
--- 55,61 ----
  			      int nregs, int regs_allocated) internal_function;
  static inline re_dfastate_t *acquire_init_state_context
       (reg_errcode_t *err, const re_match_context_t *mctx, int idx)
!      internal_function;
  static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
       internal_function;
  static int check_matching (re_match_context_t *mctx, int fl_longest_match,
***************
*** 603,617 ****
    reg_errcode_t err;
    re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
    int left_lim, right_lim, incr;
!   int fl_longest_match, match_first, match_last = -1;
!   int fast_translate, sb;
  #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
    re_match_context_t mctx = { .dfa = dfa };
  #else
    re_match_context_t mctx;
  #endif
!   char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
! 		    && range && !preg->can_be_null) ? preg->fastmap : NULL);

  #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
    memset (&mctx, '\0', sizeof (re_match_context_t));
--- 601,616 ----
    reg_errcode_t err;
    re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
    int left_lim, right_lim, incr;
!   int fl_longest_match, match_first, match_kind, match_last = -1;
!   int fast_translate, sb, ch;
  #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
    re_match_context_t mctx = { .dfa = dfa };
  #else
    re_match_context_t mctx;
  #endif
!   char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
! 		   && range && !preg->can_be_null) ? preg->fastmap : NULL;
!   unsigned RE_TRANSLATE_TYPE t = (unsigned RE_TRANSLATE_TYPE) preg->translate;

  #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
    memset (&mctx, '\0', sizeof (re_match_context_t));
***************
*** 684,771 ****
    left_lim = (range < 0) ? start + range : start;
    right_lim = (range < 0) ? start : start + range;
    sb = dfa->mb_cur_max == 1;
!   fast_translate = sb || !(preg->syntax & RE_ICASE || preg->translate);

!   for (;;)
      {
!       /* At first get the current byte from input string.  */
!       if (fastmap)
! 	{
! 	  if (BE (fast_translate, 1))
! 	    {
! 	      unsigned RE_TRANSLATE_TYPE t
! 		= (unsigned RE_TRANSLATE_TYPE) preg->translate;
! 	      if (BE (range >= 0, 1))
! 		{
! 		  if (BE (t != NULL, 0))
! 		    {
! 		      while (BE (match_first < right_lim, 1)
! 			     && !fastmap[t[(unsigned char) string[match_first]]])
! 			++match_first;
! 		    }
! 		  else
! 		    {
! 		      while (BE (match_first < right_lim, 1)
! 			     && !fastmap[(unsigned char) string[match_first]])
! 			++match_first;
! 		    }
! 		  if (BE (match_first == right_lim, 0))
! 		    {
! 		      int ch = match_first >= length
! 			       ? 0 : (unsigned char) string[match_first];
! 		      if (!fastmap[t ? t[ch] : ch])
! 			break;
! 		    }
! 		}
! 	      else
! 		{
! 		  while (match_first >= left_lim)
! 		    {
! 		      int ch = match_first >= length
! 			       ? 0 : (unsigned char) string[match_first];
! 		      if (fastmap[t ? t[ch] : ch])
! 			break;
! 		      --match_first;
! 		    }
! 		  if (match_first < left_lim)
! 		    break;
! 		}
  	    }
! 	  else
! 	    {
! 	      int ch;

! 	      do
  		{
! 		  /* In this case, we can't determine easily the current byte,
! 		     since it might be a component byte of a multibyte
! 		     character.  Then we use the constructed buffer
! 		     instead.  */
! 		  /* If MATCH_FIRST is out of the valid range, reconstruct the
! 		     buffers.  */
! 		  if (mctx.input.raw_mbs_idx + mctx.input.valid_raw_len
! 		      <= match_first
! 		      || match_first < mctx.input.raw_mbs_idx)
! 		    {
! 		      err = re_string_reconstruct (&mctx.input, match_first,
! 						   eflags);
! 		      if (BE (err != REG_NOERROR, 0))
! 			goto free_return;
! 		    }
! 		  /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
! 		     Note that MATCH_FIRST must not be smaller than 0.  */
! 		  ch = ((match_first >= length) ? 0
! 		       : re_string_byte_at (&mctx.input,
! 					    match_first
! 					    - mctx.input.raw_mbs_idx));
! 		  if (fastmap[ch])
! 		    break;
! 		  match_first += incr;
  		}
! 	      while (match_first >= left_lim && match_first <= right_lim);
! 	      if (! fastmap[ch])
  		break;
  	    }
  	}

        /* Reconstruct the buffers so that the matcher can assume that
--- 683,781 ----
    left_lim = (range < 0) ? start + range : start;
    right_lim = (range < 0) ? start : start + range;
    sb = dfa->mb_cur_max == 1;
!   match_kind =
!     (fastmap ? 8 : 0)
!     | (sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
!     | (range >= 0 ? 2 : 0)
!     | (t != NULL ? 1 : 0);

!   for (;; match_first += incr)
      {
!       err = REG_NOMATCH;
!       if (match_first < left_lim || right_lim < match_first)
! 	goto free_return;
!
!       /* Advance as rapidly as possible through the string, until we
! 	 find a plausible place to start matching.  This may be done
! 	 with varying efficiency, so there are various possibilities:
! 	 only the most common of them are specialized, in order to
! 	 save on code size.  We use a switch statement for speed.  */
!       switch (match_kind)
! 	{
! 	case 0: case 1: case 2: case 3:
! 	case 4: case 5: case 6: case 7:
! 	  /* No fastmap.  */
! 	  break;
!
! 	case 15:
! 	  /* Fastmap with single-byte translation, match forward.  */
! 	  while (BE (match_first < right_lim, 1)
! 		 && !fastmap[t[(unsigned char) string[match_first]]])
! 	    ++match_first;
! 	  goto forward_match_found_start_or_reached_end;
!
! 	case 14:
! 	  /* Fastmap without translation, match forward.  */
! 	  while (BE (match_first < right_lim, 1)
! 		 && !fastmap[(unsigned char) string[match_first]])
! 	    ++match_first;
!
! 	forward_match_found_start_or_reached_end:
! 	  if (BE (match_first == right_lim, 0))
! 	    {
! 	      ch = match_first >= length
! 		       ? 0 : (unsigned char) string[match_first];
! 	      if (!fastmap[t ? t[ch] : ch])
! 		goto free_return;
  	    }
! 	  break;

! 	case 12:
! 	case 13:
! 	  /* Fastmap without multi-byte translation, match backwards.  */
! 	  while (match_first >= left_lim)
! 	    {
! 	      ch = match_first >= length
! 		       ? 0 : (unsigned char) string[match_first];
! 	      if (fastmap[t ? t[ch] : ch])
! 		break;
! 	      --match_first;
! 	    }
! 	  if (match_first < left_lim)
! 	    goto free_return;
! 	  break;
!
! 	default:
! 	  /* In this case, we can't determine easily the current byte,
! 	     since it might be a component byte of a multibyte
! 	     character.  Then we use the constructed buffer instead.  */
! 	  for (;;)
! 	    {
! 	      /* If MATCH_FIRST is out of the valid range, reconstruct the
! 		 buffers.  */
! 	      if (mctx.input.raw_mbs_idx + mctx.input.valid_raw_len <= match_first
! 		  || match_first < mctx.input.raw_mbs_idx)
  		{
! 		  err = re_string_reconstruct (&mctx.input, match_first,
! 					       eflags);
! 		  if (BE (err != REG_NOERROR, 0))
! 		    goto free_return;
  		}
! 	      /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
! 		 Note that MATCH_FIRST must not be smaller than 0.  */
! 	      ch = ((match_first >= length) ? 0
! 		    : re_string_byte_at (&mctx.input,
! 					 match_first - mctx.input.raw_mbs_idx));
! 	      if (fastmap[ch])
  		break;
+ 	      match_first += incr;
+ 	      if (match_first < left_lim || match_first > right_lim)
+ 	        {
+ 	          err = REG_NOMATCH;
+ 	          goto free_return;
+ 	        }
  	    }
+ 	  break;
  	}

        /* Reconstruct the buffers so that the matcher can assume that
***************
*** 773,829 ****
        err = re_string_reconstruct (&mctx.input, match_first, eflags);
        if (BE (err != REG_NOERROR, 0))
  	goto free_return;
  #ifdef RE_ENABLE_I18N
!      /* Eliminate it when it is a component of a multibyte character
! 	 and isn't the head of a multibyte character.  */
!       if (sb || re_string_first_byte (&mctx.input, 0))
  #endif
  	{
! 	  /* It seems to be appropriate one, then use the matcher.  */
! 	  /* We assume that the matching starts from 0.  */
! 	  mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
! 	  match_last = check_matching (&mctx, fl_longest_match,
! 				       range >= 0 ? &match_first : NULL);
! 	  if (match_last != -1)
  	    {
! 	      if (BE (match_last == -2, 0))
  		{
! 		  err = REG_ESPACE;
! 		  goto free_return;
  		}
! 	      else
  		{
! 		  mctx.match_last = match_last;
! 		  if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
! 		    {
! 		      re_dfastate_t *pstate = mctx.state_log[match_last];
! 		      mctx.last_node = check_halt_state_context (&mctx, pstate,
! 								 match_last);
! 		    }
! 		  if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
! 		      || dfa->nbackref)
! 		    {
! 		      err = prune_impossible_nodes (&mctx);
! 		      if (err == REG_NOERROR)
! 			break;
! 		      if (BE (err != REG_NOMATCH, 0))
! 			goto free_return;
! 		      match_last = -1;
! 		    }
! 		  else
! 		    break; /* We found a match.  */
  		}
  	    }
- 	  match_ctx_clean (&mctx);
  	}
!       /* Update counter.  */
!       match_first += incr;
!       if (match_first < left_lim || right_lim < match_first)
! 	break;
      }

    /* Set pmatch[] if we need.  */
!   if (match_last != -1 && nmatch > 0)
      {
        int reg_idx;

--- 783,842 ----
        err = re_string_reconstruct (&mctx.input, match_first, eflags);
        if (BE (err != REG_NOERROR, 0))
  	goto free_return;
+
  #ifdef RE_ENABLE_I18N
!      /* Don't consider this char as a possible match start if it part,
! 	yet isn't the head, of a multibyte character.  */
!       if (!sb && !re_string_first_byte (&mctx.input, 0))
! 	continue;
  #endif
+
+       /* It seems to be appropriate one, then use the matcher.  */
+       /* We assume that the matching starts from 0.  */
+       mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
+       match_last = check_matching (&mctx, fl_longest_match,
+ 				   range >= 0 ? &match_first : NULL);
+       if (match_last != -1)
  	{
! 	  if (BE (match_last == -2, 0))
  	    {
! 	      err = REG_ESPACE;
! 	      goto free_return;
! 	    }
! 	  else
! 	    {
! 	      mctx.match_last = match_last;
! 	      if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
  		{
! 		  re_dfastate_t *pstate = mctx.state_log[match_last];
! 		  mctx.last_node = check_halt_state_context (&mctx, pstate,
! 							     match_last);
  		}
! 	      if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
! 		  || dfa->nbackref)
  		{
! 		  err = prune_impossible_nodes (&mctx);
! 		  if (err == REG_NOERROR)
! 		    break;
! 		  if (BE (err != REG_NOMATCH, 0))
! 		    goto free_return;
! 		  match_last = -1;
  		}
+ 	      else
+ 		break; /* We found a match.  */
  	    }
  	}
!
!       match_ctx_clean (&mctx);
      }

+ #ifdef DEBUG
+   assert (match_last != -1);
+   assert (err == REG_NOERROR);
+ #endif
+
    /* Set pmatch[] if we need.  */
!   if (nmatch > 0)
      {
        int reg_idx;

***************
*** 868,874 ****
  	    pmatch[reg_idx].rm_eo += match_first;
  	  }
      }
!   err = (match_last == -1) ? REG_NOMATCH : REG_NOERROR;
   free_return:
    re_free (mctx.state_log);
    if (dfa->nbackref)
--- 881,887 ----
  	    pmatch[reg_idx].rm_eo += match_first;
  	  }
      }
!
   free_return:
    re_free (mctx.state_log);
    if (dfa->nbackref)
***************
*** 1073,1078 ****
--- 1086,1105 ----
    while (!re_string_eoi (&mctx->input))
      {
        re_dfastate_t *old_state = cur_state;
+       int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
+
+       if (BE (next_char_idx >= mctx->input.bufs_len, 0)
+           || (BE (next_char_idx >= mctx->input.valid_len, 0)
+               && mctx->input.valid_len < mctx->input.len))
+         {
+           err = extend_buffers (mctx);
+           if (BE (err != REG_NOERROR, 0))
+ 	    {
+ 	      assert (err == REG_ESPACE);
+ 	      return -2;
+ 	    }
+         }
+
        cur_state = transit_state (&err, mctx, cur_state);
        if (mctx->state_log != NULL)
  	cur_state = merge_state_with_log (&err, mctx, cur_state);
***************
*** 1091,1100 ****
  	    break;
  	}

!       if (at_init_state)
  	{
  	  if (old_state == cur_state)
! 	    next_start_idx = re_string_cur_idx (&mctx->input);
  	  else
  	    at_init_state = 0;
  	}
--- 1118,1127 ----
  	    break;
  	}

!       if (BE (at_init_state, 0))
  	{
  	  if (old_state == cur_state)
! 	    next_start_idx = next_char_idx;
  	  else
  	    at_init_state = 0;
  	}
***************
*** 1110,1122 ****
  	      /* We found an appropriate halt state.  */
  	      match_last = re_string_cur_idx (&mctx->input);
  	      match = 1;
  	      if (!fl_longest_match)
  		break;
  	    }
  	}
!    }

!   if (match_last == -1 && p_match_first)
      *p_match_first += next_start_idx;

    return match_last;
--- 1137,1152 ----
  	      /* We found an appropriate halt state.  */
  	      match_last = re_string_cur_idx (&mctx->input);
  	      match = 1;
+
+ 	      /* We found a match, do not modify match_first below.  */
+ 	      p_match_first = NULL;
  	      if (!fl_longest_match)
  		break;
  	    }
  	}
!     }

!   if (p_match_first)
      *p_match_first += next_start_idx;

    return match_last;
***************
*** 2171,2188 ****
    re_dfastate_t **trtable;
    unsigned char ch;

-   if (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.bufs_len
-       || (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.valid_len
- 	  && mctx->input.valid_len < mctx->input.len))
-     {
-       *err = extend_buffers (mctx);
-       if (BE (*err != REG_NOERROR, 0))
- 	return NULL;
-     }
-
  #ifdef RE_ENABLE_I18N
        /* If the current state can accept multibyte.  */
!       if (state->accept_mb)
  	{
  	  *err = transit_state_mb (mctx, state);
  	  if (BE (*err != REG_NOERROR, 0))
--- 2201,2209 ----
    re_dfastate_t **trtable;
    unsigned char ch;

  #ifdef RE_ENABLE_I18N
        /* If the current state can accept multibyte.  */
!       if (BE (state->accept_mb, 0))
  	{
  	  *err = transit_state_mb (mctx, state);
  	  if (BE (*err != REG_NOERROR, 0))

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-4
2008-01-09 16:10:43 +01:00
Paolo Bonzini 2546daaded add branch predictions to re_string functions
2004-10-27  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regex_internal.c (re_string_reconstruct,
	re_string_context_at): Add several branch predictions for
	case-sensitive matching and no transition table being used.

diff -ru lib_mio/regex_internal.c lib/regex_internal.c
--- lib_mio/regex_internal.c	2004-10-27 12:47:44.000000000 +0200
+++ lib/regex_internal.c	2004-10-27 12:51:22.000000000 +0200
@@ -577,7 +577,7 @@
      int idx, eflags;
 {
   int offset = idx - pstr->raw_mbs_idx;
-  if (offset < 0)
+  if (BE (offset < 0, 0))
     {
       /* Reset buffer.  */
 #ifdef RE_ENABLE_I18N
@@ -597,10 +597,10 @@
       offset = idx;
     }

-  if (offset != 0)
+  if (BE (offset != 0, 1))
     {
       /* Are the characters which are already checked remain?  */
-      if (offset < pstr->valid_raw_len
+      if (BE (offset < pstr->valid_raw_len, 1)
 #ifdef RE_ENABLE_I18N
 	  /* Handling this would enlarge the code too much.
 	     Accept a slowdown in that case.  */
@@ -615,7 +615,7 @@
 	    memmove (pstr->wcs, pstr->wcs + offset,
 		     (pstr->valid_len - offset) * sizeof (wint_t));
 #endif /* RE_ENABLE_I18N */
-	  if (pstr->mbs_allocated)
+	  if (BE (pstr->mbs_allocated, 0))
 	    memmove (pstr->mbs, pstr->mbs + offset,
 		     pstr->valid_len - offset);
 	  pstr->valid_len -= offset;
@@ -713,7 +713,7 @@
 				      ? CONTEXT_NEWLINE : 0));
 	    }
 	}
-      if (!pstr->mbs_allocated)
+      if (!BE (pstr->mbs_allocated, 0))
 	pstr->mbs += offset;
     }
   pstr->raw_mbs_idx = idx;
@@ -735,16 +735,17 @@
     }
   else
 #endif /* RE_ENABLE_I18N */
+  if (BE (pstr->mbs_allocated, 0))
     {
       if (pstr->icase)
 	build_upper_buffer (pstr);
       else if (pstr->trans != NULL)
 	re_string_translate_buffer (pstr);
-      else
-	pstr->valid_len = pstr->len;
     }
-  pstr->cur_idx = 0;
+  else
+    pstr->valid_len = pstr->len;

+  pstr->cur_idx = 0;
   return REG_NOERROR;
 }

@@ -842,16 +843,13 @@
      int idx, eflags;
 {
   int c;
-  if (idx < 0 || idx == input->len)
-    {
-      if (idx < 0)
-	/* In this case, we use the value stored in input->tip_context,
-	   since we can't know the character in input->mbs[-1] here.  */
-	return input->tip_context;
-      else /* (idx == input->len) */
-	return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
-		: CONTEXT_NEWLINE | CONTEXT_ENDBUF);
-    }
+  if (BE (idx < 0, 0))
+    /* In this case, we use the value stored in input->tip_context,
+       since we can't know the character in input->mbs[-1] here.  */
+    return input->tip_context;
+  if (BE (idx == input->len, 0))
+    return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
+	    : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
 #ifdef RE_ENABLE_I18N
   if (input->mb_cur_max > 1)
     {

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-3
2008-01-09 16:10:42 +01:00
Paolo Bonzini 42e453acf4 cleanup match_ctx_clean
2004-10-27  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regexec.c (match_ctx_free_subtops): Remove, merge into...
	(match_ctx_clean): ... this function.
	(match_ctx_free): Call match_ctx_clean.

diff -ru lib_mio/regexec.c lib/regexec.c
--- lib_mio/regexec.c	2004-10-27 13:03:14.000000000 +0200
+++ lib/regexec.c	2004-10-27 12:56:46.000000000 +0200
@@ -22,8 +22,6 @@
 				     int n) internal_function;
 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
 static void match_ctx_free (re_match_context_t *cache) internal_function;
-static void match_ctx_free_subtops (re_match_context_t *mctx)
-     internal_function;
 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
 					  int str_idx, int from, int to)
      internal_function;
@@ -4103,28 +4101,6 @@
 match_ctx_clean (mctx)
     re_match_context_t *mctx;
 {
-  match_ctx_free_subtops (mctx);
-  mctx->nsub_tops = 0;
-  mctx->nbkref_ents = 0;
-}
-
-/* Free all the memory associated with MCTX.  */
-
-static void
-match_ctx_free (mctx)
-    re_match_context_t *mctx;
-{
-  match_ctx_free_subtops (mctx);
-  re_free (mctx->sub_tops);
-  re_free (mctx->bkref_ents);
-}
-
-/* Free all the memory associated with MCTX->SUB_TOPS.  */
-
-static void
-match_ctx_free_subtops (mctx)
-     re_match_context_t *mctx;
-{
   int st_idx;
   for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
     {
@@ -4144,6 +4118,21 @@
 	}
       free (top);
     }
+
+  mctx->nsub_tops = 0;
+  mctx->nbkref_ents = 0;
+}
+
+/* Free all the memory associated with MCTX.  */
+
+static void
+match_ctx_free (mctx)
+    re_match_context_t *mctx;
+{
+  /* First, free all the memory associated with MCTX->SUB_TOPS.  */
+  match_ctx_clean (mctx);
+  re_free (mctx->sub_tops);
+  re_free (mctx->bkref_ents);
 }

 /* Add a new backreference entry to MCTX.

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-2
2008-01-09 16:10:41 +01:00
Paolo Bonzini 87c703bf63 get back to glibc regex
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-1
2008-01-09 16:10:41 +01:00
Paolo Bonzini 9c9919efe2 initial import
(automatically generated log message)

git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--base-0
2004-10-20 21:42:31 +00:00