Re: more testsuite coverage for autoconf idioms

Eric Blake <ebb9 <at> byu.net> writes:

> I have been working away on a series of patches to speed up recursive
> macro handling (with a goal to make $@ handling linear instead of
> quadratic).  That series is not ready yet,

Still not ready to post, although I have made progress, and uncovered a couple 
more corner cases to be aware of.  Included in the patch below.

Also, as part of my patching progress, I have been hammering on a stress-test 
(also included in this patch).  So far, I have been able to shave the peak 
memory usage of 'm4 -Dlimit=1500 loop.m4' from 41 megabytes down to 14, with a 
slight speedup, once I convinced the input engine to handle references to 
previously parsed arguments; but I'm still trying to hammer out why 'm4 -
Dlimit=1500 -Dalt loop.m4' went from 19 megabytes to 109, even though it 
completes in the same amount of time.  And the quadratic scaling factor of tail-
recursive parsing is not gone yet, until I can convince shift to handle a 
reference to a group of arguments, rather than a group of references to 
individual arguments.

> For the branch, the testsuite is contained entirely within the
> m4.texinfo, hence adding some tests within @ignore blocks.  But for head,
> I will move those tests to a more appropriate tests/*.at file.

Some of these changes are in documented tests, but for those that aren't, the 
same rules will apply to my port of this patch to head.

From: Eric Blake <[email protected]>
Date: Wed, 31 Oct 2007 08:50:30 -0600
Subject: [PATCH] Test more corner cases.

* doc/m4.texinfo (Changecom, Pseudo Arguments): Beef up tests.
(Improved foreach): Document alternate foreachq style.
* examples/foreachq3.m4: New file.
* examples/loop.m4: New file.
* examples/Makefile.am (EXTRA_DIST): Distribute them.

Signed-off-by: Eric Blake <[email protected]>
---
 ChangeLog             |    9 +++++
 doc/m4.texinfo        |   85 +++++++++++++++++++++++++++++++++++++++++++-----
 examples/Makefile.am  |    2 +
 examples/foreachq3.m4 |   10 ++++++
 examples/loop.m4      |   16 +++++++++
 5 files changed, 113 insertions(+), 9 deletions(-)
 create mode 100644 examples/foreachq3.m4
 create mode 100644 examples/loop.m4

diff --git a/ChangeLog b/ChangeLog
index 737a6ec..a25c84d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2007-10-31  Eric Blake  <[email protected]>
+
+	Test more corner cases.
+	* doc/m4.texinfo (Changecom, Pseudo Arguments): Beef up tests.
+	(Improved foreach): Document alternate foreachq style.
+	* examples/foreachq3.m4: New file.
+	* examples/loop.m4: New file.
+	* examples/Makefile.am (EXTRA_DIST): Distribute them.
+
 2007-10-28  Eric Blake  <[email protected]>
 
 	More test coverage for autoconf usage patterns.
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index d7c8140..3fc6dfa 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -1942,11 +1942,17 @@ foo)
 @comment levels.
 
 @example
-define(`echo', `$@')dnl
+define(`echo', `$@@')dnl
 len((echo(`01234567890123456789',
           `01234567890123456789')echo(`98765432109876543210',
                                       `98765432109876543210')))
 @result{}84
+define(`argn', `$#')dnl
+define(`echo1', `-$@@-')define(`echo2', `,$@@,')dnl
+echo1(`1', `2', `3') argn(echo1(`1', `2', `3'))
+@result{}-1,2,3- 3
+echo2(`1', `2', `3') argn(echo2(`1', `2', `3'))
+@result{},1,2,3, 5
 @end example
 @end ignore
 
@@ -3801,26 +3807,32 @@ implementations, it is a good idea to avoid @samp{(}, 
@samp{,}, and
 @samp{)} as the first character in @var{start}.
 
 @example
-define(`echo', `$#:$@@:')
+define(`echo', `$#:$*:$@@:')
 @result{}
 define(`hi', `HI')
 @result{}
 changecom(`(',`)')
 @result{}
 echo(hi)
-@result{}0::(hi)
+@result{}0:::(hi)
 changecom
 @result{}
 changecom(`((', `))')
 @result{}
 echo(hi)
-@result{}1:HI:
+@result{}1:HI:HI:
 echo((hi))
-@result{}0::((hi))
+@result{}0:::((hi))
 changecom(`,', `)')
 @result{}
 echo(hi,hi)bye)
-@result{}1:HI,hi)bye:
+@result{}1:HI,hi)bye:HI,hi)bye:
+changecom
+@result{}
+echo(hi,`,`'hi',hi)
+@result{}3:HI,,HI,HI:HI,,`'hi,HI:
+echo(hi,`,`'hi',hi`'changecom(`,,', `hi'))
+@result{}3:HI,,`'hi,HI:HI,,`'hi,HI:
 @end example
 
 It is an error if the end of file occurs within a comment.
@@ -6803,7 +6815,60 @@ Contrast the use of @code{@w{_arg1q}}, which quotes the 
first list
 element, with @code{@w{_arg1}} of the earlier implementation that
 returned the first list element directly.
 
-For a different approach, the improved version of @code{foreach},
+The astute m4 programmer might notice that the solution above still uses
+more memory, and thus more time, than strictly necessary.  Note that
+@samp{$2}, which contains an arbitrarily long quoted list, is expanded
+and rescanned three times per iteration of @code{_foreachq}.
+Furthermore, every iteration of the algorithm effectively unboxes then
+reboxes the list, which costs a couple of macro invocations.
+It is possible to rewrite the algorithm for a bit more speed by swapping
+the order of the arguments to @code{_foreachq} in order to operate on an
+unboxed list in the first place, and by using the fixed-length @samp{$#}
+instead of an arbitrary length list as the key to end recursion.  This
+alternative approach is available as
+@file{m4-@value{VERSION}/@/examples/@/foreach3.m4}:
+
+@example
+$ @kbd{m4 -I examples}
+include(`foreachq3.m4')
+@result{}
+undivert(`foreachq3.m4')dnl
+@result{}divert(`-1')
+@result{}# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+@result{}#   quoted list, alternate improved version
+@result{}define(`foreachq',
+@result{}`pushdef(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
+@result{}  `, $2'))popdef(`$1')')
+@result{}define(`_foreachq', `ifelse(`$#', `2', `',
+@result{}  `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
+@result{}    `, shift(shift(shift($@@)))'))')')
+@result{}divert`'dnl
+traceon(`shift')debugmode(`aq')
+@result{}
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
+@result{}1
+@error{}m4trace: -4- shift(`x', `x
+@error{}', `1', `2', `3', `4')
+@error{}m4trace: -3- shift(`x
+@error{}', `1', `2', `3', `4')
+@error{}m4trace: -2- shift(`1', `2', `3', `4')
+@result{}2
+@error{}m4trace: -4- shift(`x', `x
+@error{}', `2', `3', `4')
+@error{}m4trace: -3- shift(`x
+@error{}', `2', `3', `4')
+@error{}m4trace: -2- shift(`2', `3', `4')
+@result{}3
+@error{}m4trace: -4- shift(`x', `x
+@error{}', `3', `4')
+@error{}m4trace: -3- shift(`x
+@error{}', `3', `4')
+@error{}m4trace: -2- shift(`3', `4')
+@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
 @code{dquote_elt}.  Then @code{@w{_foreach}} can just use
@@ -6846,9 +6911,11 @@ In summary, recursion over list elements is trickier 
than it appeared at
 first glance, but provides a powerful idiom within @code{m4} processing.
 As a final demonstration, both list styles are now able to handle
 several scenarios that would wreak havoc on the original
-implementations.  This points out one other difference between the two
+implementations.  This points out one other difference between the
 list styles.  @code{foreach} evaluates unquoted list elements only once,
-in preparation for calling @code{@w{_foreach}}.  But @code{foreachq}
+in preparation for calling @code{@w{_foreach}}, similary for
+@code{foreachq} as provided by @file{foreachq3.m4}.  But
+@code{foreachq}, as provided by @file{foreachq2.m4},
 evaluates unquoted list elements twice while visiting the first list
 element, once in @code{@w{_arg1q}} and once in @code{@w{_rest}}.  When
 deciding which list style to use, one must take into account whether
diff --git a/examples/Makefile.am b/examples/Makefile.am
index e7672f9..b1ef68a 100644
--- a/examples/Makefile.am
+++ b/examples/Makefile.am
@@ -33,6 +33,7 @@ foreach.m4 \
 foreach2.m4 \
 foreachq.m4 \
 foreachq2.m4 \
+foreachq3.m4 \
 forloop.m4 \
 forloop2.m4 \
 fstab.m4 \
@@ -41,6 +42,7 @@ incl-test.m4 \
 incl.m4 \
 include.m4 \
 indir.m4 \
+loop.m4 \
 misc.m4 \
 multiquotes.m4 \
 patsubst.m4 \
diff --git a/examples/foreachq3.m4 b/examples/foreachq3.m4
new file mode 100644
index 0000000..beab455
--- /dev/null
+++ b/examples/foreachq3.m4
@@ -0,0 +1,10 @@
+divert(`-1')
+# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+#   quoted list, alternate improved version
+define(`foreachq',
+`pushdef(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
+  `, $2'))popdef(`$1')')
+define(`_foreachq', `ifelse(`$#', `2', `',
+  `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
+    `, shift(shift(shift($@)))'))')')
+divert`'dnl
diff --git a/examples/loop.m4 b/examples/loop.m4
new file mode 100644
index 0000000..ee278fd
--- /dev/null
+++ b/examples/loop.m4
@@ -0,0 +1,16 @@
+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 -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
+dnl -Dsleep=<num> - sleep for <num> seconds before exit, to allow time
+dnl   to examine peak process memory usage
+include(`forloop2.m4')dnl
+include(ifdef(`alt', ``foreachq3.m4'', ``foreachq2.m4''))dnl
+ifdef(`limit', `', `define(`limit', `1000')')dnl
+ifdef(`verbose', `', `divert(`-1')')dnl
+ifdef(`debug', `', `define(`debug')')
+foreachq(`i', dquote(1forloop(`i', `2', limit, `,i'))debug, ` i')
+ifdef(`sleep',`syscmd(`echo done>/dev/tty;sleep 'sleep)')dnl
-- 
1.5.3.2