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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> ----------------------------------------------------------------------- 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 <[EMAIL PROTECTED]> + + 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 <[EMAIL PROTECTED]> 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. [EMAIL PROTECTED] nine arguments, more than [EMAIL PROTECTED] more than nine arguments [EMAIL PROTECTED] 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 [EMAIL PROTECTED](`$1', `$n')$2`'}, with @samp{n} set to successive +integers corresponding to each argument. The helper macro [EMAIL PROTECTED] 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 [EMAIL PROTECTED] calls are even needed! However, when linear recursion is +available in new enough M4, the time and memory cost of using [EMAIL PROTECTED] 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 @[EMAIL PROTECTED]@}} can be used instead, although that alternative +syntax is not yet supported. + [EMAIL PROTECTED] examples [EMAIL PROTECTED] +$ @kbd{m4 -I examples} +include(`foreachq4.m4') [EMAIL PROTECTED] +undivert(`foreachq4.m4')dnl [EMAIL PROTECTED](`forloop2.m4')dnl [EMAIL PROTECTED](`-1') [EMAIL PROTECTED] foreachq(x, `item_1, item_2, ..., item_n', stmt) [EMAIL PROTECTED] quoted list, version based on forloop [EMAIL PROTECTED](`foreachq', [EMAIL PROTECTED](`$2', `', `', `_$0(`$1', `$3', $2)')') [EMAIL PROTECTED](`_foreachq', [EMAIL PROTECTED](`$1', forloop(`$1', `3', `$#', [EMAIL PROTECTED] `$0_(`1', `2', indir(`$1'))')`popdef( [EMAIL PROTECTED] `$1')')indir(`$1', $@@)') [EMAIL PROTECTED](`_foreachq_', [EMAIL PROTECTED](`$$1', `$$3')$$2`''') [EMAIL PROTECTED]'dnl +traceon(`shift')debugmode(`aq') [EMAIL PROTECTED] +foreachq(`x', ``1', `2', `3', `4'', `x +')dnl [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] example + For yet another approach, the improved version of @code{foreach}, available in @[EMAIL PROTECTED]/@/examples/@/foreach2.m4}, simply overquotes the arguments to @[EMAIL PROTECTED] 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
