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 <ebb9@byu.net>
(cherry picked from commit 72506c2eb1d10571bcd2351aa1f3d2427be3c669)

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  <ebb9@byu.net>
+
+	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  <ebb9@byu.net>
 
 	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