From 8c26ddfb1acdeb708111c2f410027af0dc25978e Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Thu, 12 Feb 2009 15:29:53 -0700 Subject: [PATCH] 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 (cherry picked from commit 72506c2eb1d10571bcd2351aa1f3d2427be3c669) --- 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 278093fe..a0802edd 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2009-02-12 Eric Blake + + 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 Stage 28c: Warn on embedded NUL in remaining cases. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index 62fed45f..e574bd5d 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{m4-@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 b11bc839..767d15e2 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 779fd3cc..e9b7a1b8 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 -- 2.11.4.GIT