O(n) foreach loop on m4 1.4.x

From eeaceb311464f6d88d2782ed8773c01d49f83aba Mon Sep 17 00:00:00 2001
From: Eric Blake <[email protected]>
Date: Sat, 26 Jul 2008 15:39:48 -0600
Subject: [PATCH] Give example for O(n) foreach on m4 1.4.x.

* examples/foreachq4.m4: New file.
* examples/Makefile.am (EXTRA_DIST): Distribute it.
* doc/m4.texinfo (Improved foreach): Document linear foreach with
m4 1.4.5 and greater.

Signed-off-by: Eric Blake <[email protected]>
---
 ChangeLog             |    6 +++
 doc/m4.texinfo        |   83 +++++++++++++++++++++++++++++++++++++++++++++++++
 examples/Makefile.am  |    1 +
 examples/foreachq4.m4 |   13 ++++++++
 examples/loop.m4      |    5 ++-
 5 files changed, 106 insertions(+), 2 deletions(-)
 create mode 100644 examples/foreachq4.m4

diff --git a/ChangeLog b/ChangeLog
index de44226..9572436 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2008-07-26  Eric Blake  <[email protected]>
 
+	Give example for O(n) foreach on m4 1.4.x.
+	* examples/foreachq4.m4: New file.
+	* examples/Makefile.am (EXTRA_DIST): Distribute it.
+	* doc/m4.texinfo (Improved foreach): Document linear foreach with
+	m4 1.4.5 and greater.
+
 	Use hash module for self-growing symbol table.
 	* m4/gnulib-cache.m4: Import hash module.
 	* src/m4.h (struct symbol): Remove next member, change stack to be
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index e78061c..0185ba5 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -7879,6 +7879,61 @@ noticeable; in fact, after the change, the @file{foreachq2.m4} version
 uses slightly less memory since it tracks fewer arguments per macro
 invocation.
 
+@cindex nine arguments, more than
+@cindex more than nine arguments
+@cindex 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
+@code{m4_define(`$1', `$n')$2`'}, with @samp{n} set to successive
+integers corresponding to each argument.  The helper macro
+@code{_foreachq_} 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
+@code{shift} calls are even needed!  However, when linear recursion is
+available in new enough M4, the time and memory cost of using
+@code{forloop} 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 @samp{$@{10@}} can be used instead, although that alternative
+syntax is not yet supported.
+
+@comment examples
+@example
+$ @kbd{m4 -I examples}
+include(`foreachq4.m4')
+@result{}
+undivert(`foreachq4.m4')dnl
+@result{}include(`forloop2.m4')dnl
+@result{}divert(`-1')
+@result{}# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+@result{}#   quoted list, version based on forloop
+@result{}define(`foreachq',
+@result{}`ifelse(`$2', `', `', `_$0(`$1', `$3', $2)')')
+@result{}define(`_foreachq',
+@result{}`pushdef(`$1', forloop(`$1', `3', `$#',
+@result{}  `$0_(`1', `2', indir(`$1'))')`popdef(
+@result{}    `$1')')indir(`$1', $@@)')
+@result{}define(`_foreachq_',
+@result{}``define(`$$1', `$$3')$$2`''')
+@result{}divert`'dnl
+traceon(`shift')debugmode(`aq')
+@result{}
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
+@result{}1
+@result{}2
+@result{}3
+@result{}4
+@end example
+
 For yet another approach, the improved version of @code{foreach},
 available in @file{m4-@value{VERSION}/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @code{@w{_foreach}} to begin with, using
@@ -8065,6 +8120,34 @@ include(`loop.m4')dnl
 @result{}10000
 @end example
 
+@comment foreach via forloop recursion
+
+@comment examples
+@comment options: -Dlimit=10 -Dverbose -Dalt=4
+@example
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose -Dalt=4}
+include(`loop.m4')dnl
+@result{} 1 2 3 4 5 6 7 8 9 10
+@end example
+
+@comment examples
+@comment options: -Dlimit=2500 -Dalt=4
+@example
+$ @kbd {m4 -I examples -Dlimit=2500 -Dalt=4}
+include(`loop.m4')dnl
+@end example
+
+@comment examples
+@comment options: -Dlimit=10000 -Dalt=4
+@example
+$ @kbd {m4 -I examples -Dlimit=10000 -Dalt=4}
+define(`foo', `divert`'len(popdef(`_foreachq')_foreachq($@@))')dnl
+define(`debug', `pushdef(`_foreachq', defn(`foo'))')
+@result{}
+include(`loop.m4')dnl
+@result{}48894
+@end example
+
 @end ignore
 
 @node Improved m4wrap
diff --git a/examples/Makefile.am b/examples/Makefile.am
index 254d2ab..47bf0c0 100644
--- a/examples/Makefile.am
+++ b/examples/Makefile.am
@@ -34,6 +34,7 @@ foreach2.m4 \
 foreachq.m4 \
 foreachq2.m4 \
 foreachq3.m4 \
+foreachq4.m4 \
 forloop.m4 \
 forloop2.m4 \
 fstab.m4 \
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
-- 
1.5.6.4