This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GNU M4 source repository".
http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=72506c2eb1d10571bcd2351aa1f3d2427be3c669 The branch, branch-1.4 has been updated via 72506c2eb1d10571bcd2351aa1f3d2427be3c669 (commit) from d499df171ddb2161d1e75055009a9b3d18131591 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 72506c2eb1d10571bcd2351aa1f3d2427be3c669 Author: Eric Blake <[email protected]> Date: Thu Feb 12 14:59:08 2009 -0700 Avoid quadratic code when walking definition stack. * examples/stack_sep.m4: Use linear, not quadratic implementation. * doc/m4.texinfo (Improved copy): Fix documentation and add test, based on recent autoconf bug fix. Signed-off-by: Eric Blake <[email protected]> ----------------------------------------------------------------------- Summary of changes: ChangeLog | 8 ++++++++ doc/m4.texinfo | 45 +++++++++++++++++++++++++++++++++++---------- examples/stack_sep.m4 | 6 +++--- 3 files changed, 46 insertions(+), 13 deletions(-) diff --git a/ChangeLog b/ChangeLog index c55e79f..3495018 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2009-02-12 Eric Blake <[email protected]> + + Avoid quadratic code when walking definition stack. + * examples/stack_sep.m4: Use linear, not quadratic + implementation. + * doc/m4.texinfo (Improved copy): Fix documentation and add test, + based on recent autoconf bug fix. + 2009-01-24 Eric Blake <[email protected]> Add URLs to --help output. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index c09d771..9bbfcfd 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -8199,13 +8199,21 @@ equivalent to @code{stack_foreach_sep(`...@var{macro}', `...@var{action}(', construct macro calls with more than one argument, without passing builtin tokens through a macro call. It is likewise possible to directly reference the stack definitions without a macro call, by -leaving @var{pre} and @var{post} empty. The new macro also adds a -separator that is only output after the first iteration of the helper -...@code{_stack_reverse_sep}, implemented by prepending the original -...@var{sep} to @var{pre} and omitting a @var{sep} argument in subsequent -iterations. As an added bonus, using @code{stack_foreach_sep} to -implement @code{copy} performs fewer macro invocations. The improved -stack walking macros are available in +leaving @var{pre} and @var{post} empty. Thus, in addition to fixing +...@code{copy} on builtin tokens, it also executes with fewer macro +invocations. + +The new macro also adds a separator that is only output after the first +iteration of the helper @code{_stack_reverse_sep}, implemented by +prepending the original @var{sep} to @var{pre} and omitting a @var{sep} +argument in subsequent iterations. Note that the empty string that +separates @var{sep} from @var{pre} is provided as part of the fourth +argument when originally calling @code{_stack_reverse_sep}, and not by +writing @code{$4`'$3} as the third argument in the recursive call; while +the other approach would give the same output, it does so at the expense +of increasing the argument size on each iteration of +...@code{_stack_reverse_sep}, which results in quadratic instead of linear +execution time. The improved stack walking macros are available in @file{...@value{version}/@/examples/@/stack_sep.m4}: @comment examples @@ -8238,18 +8246,35 @@ undivert(`stack_sep.m4')dnl @result{}# separated by SEP between definitions. @result{}define(`stack_foreach_sep', @result{}`_stack_reverse_sep(`$1', `tmp-$1')'dnl -...@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')') +...@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')') @result{}# stack_foreach_sep_lifo(macro, pre, post, sep) @result{}# Like stack_foreach_sep, but starting with the newest definition. @result{}define(`stack_foreach_sep_lifo', -...@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl +...@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl @result{}`_stack_reverse_sep(`tmp-$1', `$1')') @result{}define(`_stack_reverse_sep', @result{}`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0( -...@result{} `$1', `$2', `$4`'$3')')') +...@result{} `$1', `$2', `$4$3')')') @result{}divert`'dnl @end example +...@ignore +...@comment Not worth putting in the manual, but make sure that +...@comment stack_foreach_sep has linear performance. + +...@comment examples +...@example +$ @kbd {m4 -I examples} +include(`forloop3.m4')include(`stack_sep.m4')dnl +forloop(`i', `1', `10000', `pushdef(`s', i)') +...@result{} +define(`colon', `:')define(`dash', `-') +...@result{} +len(stack_foreach_sep(`s', `dash', `', `colon')) +...@result{}58893 +...@end example +...@end ignore + @node Improved m4wrap @section Solution for @code{m4wrap} diff --git a/examples/stack_sep.m4 b/examples/stack_sep.m4 index b11bc83..767d15e 100644 --- a/examples/stack_sep.m4 +++ b/examples/stack_sep.m4 @@ -5,13 +5,13 @@ divert(`-1') # separated by SEP between definitions. define(`stack_foreach_sep', `_stack_reverse_sep(`$1', `tmp-$1')'dnl -`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')') +`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')') # stack_foreach_sep_lifo(macro, pre, post, sep) # Like stack_foreach_sep, but starting with the newest definition. define(`stack_foreach_sep_lifo', -`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl +`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl `_stack_reverse_sep(`tmp-$1', `$1')') define(`_stack_reverse_sep', `ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0( - `$1', `$2', `$4`'$3')')') + `$1', `$2', `$4$3')')') divert`'dnl hooks/post-receive -- GNU M4 source repository
