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=8c26ddfb1acdeb708111c2f410027af0dc25978e The branch, master has been updated via 8c26ddfb1acdeb708111c2f410027af0dc25978e (commit) from 3e12364a5a32e5947b0c31a2ee6dc5351b7af5e6 (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 8c26ddfb1acdeb708111c2f410027af0dc25978e Author: Eric Blake <[email protected]> Date: Thu Feb 12 15:29:53 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, based on recent autoconf bug fix. * tests/others.at (recursion): Enhance test. Signed-off-by: Eric Blake <[email protected]> (cherry picked from commit 72506c2eb1d10571bcd2351aa1f3d2427be3c669) ----------------------------------------------------------------------- Summary of changes: ChangeLog | 9 +++++++++ doc/m4.texinfo | 28 ++++++++++++++++++---------- examples/stack_sep.m4 | 6 +++--- tests/others.at | 9 +++++++++ 4 files changed, 39 insertions(+), 13 deletions(-) diff --git a/ChangeLog b/ChangeLog index 278093f..a0802ed 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +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, based on + recent autoconf bug fix. + * tests/others.at (recursion): Enhance test. + 2009-02-11 Eric Blake <[email protected]> Stage 28c: Warn on embedded NUL in remaining cases. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index 62fed45..e574bd5 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -10036,13 +10036,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 @@ -10075,15 +10083,15 @@ 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 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 diff --git a/tests/others.at b/tests/others.at index 779fd3c..e9b7a1b 100644 --- a/tests/others.at +++ b/tests/others.at @@ -483,6 +483,15 @@ AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt=4 in.m4], [0], [[48894 ]]) +dnl foreach via definition stack +AT_DATA([in.m4], [[include(`forloop3.m4')include(`stack_sep.m4')dnl +forloop(`i', `1', `10000', `pushdef(`s', i)')dnl +define(`colon', `:')define(`dash', `-')dnl +len(stack_foreach_sep(`s', `dash', `', `colon')) +]]) +AT_CHECK_M4([-I "$top_srcdir/examples" in.m4], [0], [[58893 +]]) + AT_CLEANUP hooks/post-receive -- GNU M4 source repository
