[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-145-g9ede0e4

[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=9ede0e4cda99d061ba9cceb07a8b11efb69a7049

The branch, master has been updated
       via  9ede0e4cda99d061ba9cceb07a8b11efb69a7049 (commit)
      from  02a5291b279c2523ef95f39c12bc07bcd9fdd177 (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 9ede0e4cda99d061ba9cceb07a8b11efb69a7049
Author: Eric Blake <address@hidden>
Date:   Sat Jul 26 16:42:15 2008 -0600

    Give example for O(n) foreach on m4 1.4.x.
    
    * examples/foreachq4.m4: New file.
    * Makefile.am (dist_pkgdata_DATA): Distribute it.
    * tests/others.at (recursion): Test it.
    * doc/m4.texinfo (Improved foreach): Document linear foreach with
    m4 1.4.5 and greater.
    
    Signed-off-by: Eric Blake <address@hidden>

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog             |    9 ++++++++
 Makefile.am           |    1 +
 doc/m4.texinfo        |   55 +++++++++++++++++++++++++++++++++++++++++++++++++
 examples/foreachq4.m4 |   13 +++++++++++
 examples/loop.m4      |    5 ++-
 tests/others.at       |   17 ++++++++++++--
 6 files changed, 95 insertions(+), 5 deletions(-)
 create mode 100644 examples/foreachq4.m4

diff --git a/ChangeLog b/ChangeLog
index 6c36cae..3d89fb8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2008-07-26  Eric Blake  <address@hidden>
+
+       Give example for O(n) foreach on m4 1.4.x.
+       * examples/foreachq4.m4: New file.
+       * Makefile.am (dist_pkgdata_DATA): Distribute it.
+       * tests/others.at (recursion): Test it.
+       * doc/m4.texinfo (Improved foreach): Document linear foreach with
+       m4 1.4.5 and greater.
+
 2008-07-19  Eric Blake  <address@hidden>
 
        Resynchronize docs from branch.
diff --git a/Makefile.am b/Makefile.am
index 1548051..fb8d1b8 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -322,6 +322,7 @@ dist_pkgdata_DATA = \
                  examples/foreachq.m4 \
                  examples/foreachq2.m4 \
                  examples/foreachq3.m4 \
+                 examples/foreachq4.m4 \
                  examples/forloop.m4 \
                  examples/forloop2.m4 \
                  examples/fstab.m4 \
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index 56bb940..67421eb 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -9155,6 +9155,61 @@ noticeable; in fact, after the change, the 
@file{foreachq2.m4} version
 uses slightly less memory since it tracks fewer arguments per macro
 invocation.
 
address@hidden nine arguments, more than
address@hidden more than nine arguments
address@hidden arguments, more than nine
+So far, all of the implementations of @code{foreachq} presented have
+been quadratic with M4 1.4.x.  But @code{forloop} is linear, because
+each iteration parses a constant amount of arguments.  So, it is
+possible to design a variant that uses @code{forloop} to do the
+iteration, then uses @samp{$@@} only once at the end, giving a linear
+result even with older M4 implementations.  This implementation relies
+on the @acronym{GNU} extension that @samp{$10} expands to the tenth
+argument rather than the first argument concatenated with @samp{0}.  The
+trick is to define an intermediate macro that repeats the text
address@hidden(`$1', `$n')$2`'}, with @samp{n} set to successive
+integers corresponding to each argument.  The helper macro
address@hidden is needed in order to generate the literal sequences
+such as @samp{$1} into the intermediate macro, rather than expanding
+them as the arguments of @code{_foreachq}.  With this approach, no
address@hidden calls are even needed!  However, when linear recursion is
+available in new enough M4, the time and memory cost of using
address@hidden to build an intermediate macro outweigh the costs of any
+of the previous implementations.  Additionally, this approach will need
+adjustment when a future version of M4 follows @acronym{POSIX} by no
+longer treating @samp{$10} as the tenth argument; the anticipation is
+that @address@hidden@}} can be used instead, although that alternative
+syntax is not yet supported.
+
address@hidden examples
address@hidden
+$ @kbd{m4 -I examples}
+include(`foreachq4.m4')
address@hidden
+undivert(`foreachq4.m4')dnl
address@hidden(`forloop2.m4')dnl
address@hidden(`-1')
address@hidden foreachq(x, `item_1, item_2, ..., item_n', stmt)
address@hidden   quoted list, version based on forloop
address@hidden(`foreachq',
address@hidden(`$2', `', `', `_$0(`$1', `$3', $2)')')
address@hidden(`_foreachq',
address@hidden(`$1', forloop(`$1', `3', `$#',
address@hidden  `$0_(`1', `2', indir(`$1'))')`popdef(
address@hidden    `$1')')indir(`$1', $@@)')
address@hidden(`_foreachq_',
address@hidden(`$$1', `$$3')$$2`''')
address@hidden'dnl
+traceon(`shift')debugmode(`aq')
address@hidden
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
address@hidden
address@hidden
address@hidden
address@hidden
address@hidden example
+
 For yet another approach, the improved version of @code{foreach},
 available in @address@hidden/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @address@hidden to begin with, using
diff --git a/examples/foreachq4.m4 b/examples/foreachq4.m4
new file mode 100644
index 0000000..3da64c9
--- /dev/null
+++ b/examples/foreachq4.m4
@@ -0,0 +1,13 @@
+include(`forloop2.m4')dnl
+divert(`-1')
+# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+#   quoted list, version based on forloop
+define(`foreachq',
+`ifelse(`$2', `', `', `_$0(`$1', `$3', $2)')')
+define(`_foreachq',
+`pushdef(`$1', forloop(`$1', `3', `$#',
+  `$0_(`1', `2', indir(`$1'))')`popdef(
+    `$1')')indir(`$1', $@)')
+define(`_foreachq_',
+``define(`$$1', `$$3')$$2`''')
+divert`'dnl
diff --git a/examples/loop.m4 b/examples/loop.m4
index 31761c9..b2fc64c 100644
--- a/examples/loop.m4
+++ b/examples/loop.m4
@@ -1,7 +1,7 @@
 dnl Stress test for recursion algorithms.  Usage:
 dnl m4 -Ipath/to/examples [-Doptions] loop.m4
 dnl Options include:
-dnl -Dalt - test with foreachq3 instead of foreachq2
+dnl -Dalt[=<n>] - test with foreachq<n> instead of foreachq2, default 3
 dnl -Dlimit=<num> - set upper limit of sequence to <num>, default 1000
 dnl -Dverbose - print the sequence to the screen, rather than discarding
 dnl -Ddebug[=<code>] - execute <code> after forloop but before foreach
@@ -9,7 +9,8 @@ dnl -Dsleep=<num> - sleep for <num> seconds before exit, to 
allow time
 dnl   to examine peak process memory usage
 include(`forloop2.m4')dnl
 include(`quote.m4')dnl
-include(ifdef(`alt', ``foreachq3.m4'', ``foreachq2.m4''))dnl
+ifelse(alt, `alt', `define(`alt', `2')', alt, `', `define(`alt', `3')')dnl
+include(`foreachq'alt`.m4')dnl
 ifdef(`limit', `', `define(`limit', `1000')')dnl
 ifdef(`verbose', `', `divert(`-1')')dnl
 ifdef(`debug', `', `define(`debug')')dnl
diff --git a/tests/others.at b/tests/others.at
index 781e07a..7928b0d 100644
--- a/tests/others.at
+++ b/tests/others.at
@@ -374,7 +374,8 @@ AT_SETUP([recursion])
 dnl This input exploits contents of loop.m4 to print out the final value
 dnl of the recursion.
 AT_DATA([in.m4],
-[[define(`debug', `define(`popdef', `divert`'i')')dnl
+[[define(`foo', `divert`'len(popdef(`_foreachq')_foreachq($@))')dnl
+define(`debug', `pushdef(`_foreachq', defn(`foo'))')dnl
 include(`loop.m4')dnl
 ]])
 
@@ -383,7 +384,7 @@ AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose 
loop.m4], [0],
 [[ 1 2 3 4 5 6 7 8 9 10
 ]])
 AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 loop.m4], [0])
-AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 in.m4], [0], [[10000
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 in.m4], [0], [[48894
 ]])
 
 dnl unboxed recursion
@@ -391,7 +392,17 @@ AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 
-Dverbose -Dalt loop.m4], [0],
 [[ 1 2 3 4 5 6 7 8 9 10
 ]])
 AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 -Dalt loop.m4], [0])
-AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt in.m4], [0], [[10000
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt in.m4], [0],
+[[48894
+]])
+
+dnl foreach via forloop recursion
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose -Dalt=4 loop.m4],
+[0], [[ 1 2 3 4 5 6 7 8 9 10
+]])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 -Dalt=4 loop.m4], [0])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt=4 in.m4], [0],
+[[48894
 ]])
 
 AT_CLEANUP


hooks/post-receive
--
GNU M4 source repository