[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-191-g8c26ddf

[Eric Blake]

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 <address@hidden>
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 <address@hidden>
    (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  <address@hidden>
+
+       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  <address@hidden>
 
        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(address@hidden', address@hidden(',
 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
address@hidden, implemented by prepending the original
address@hidden 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
address@hidden 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
address@hidden, which results in quadratic instead of linear
+execution time.  The improved stack walking macros are available in
 @address@hidden/@/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
address@hidden(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
address@hidden(`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',
address@hidden(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
address@hidden(`$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(
address@hidden  `$1', `$2', `$4`'$3')')')
address@hidden  `$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