Re: more testsuite coverage for autoconf idioms

[Eric Blake]

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 <address@hidden>
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 <address@hidden>
---
 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  <address@hidden>
+
+       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  <address@hidden>
 
        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'))
address@hidden,2,3- 3
+echo2(`1', `2', `3') argn(echo2(`1', `2', `3'))
address@hidden,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)
address@hidden::(hi)
address@hidden:::(hi)
 changecom
 @result{}
 changecom(`((', `))')
 @result{}
 echo(hi)
address@hidden:HI:
address@hidden:HI:HI:
 echo((hi))
address@hidden::((hi))
address@hidden:::((hi))
 changecom(`,', `)')
 @result{}
 echo(hi,hi)bye)
address@hidden:HI,hi)bye:
address@hidden:HI,hi)bye:HI,hi)bye:
+changecom
address@hidden
+echo(hi,`,`'hi',hi)
address@hidden:HI,,HI,HI:HI,,`'hi,HI:
+echo(hi,`,`'hi',hi`'changecom(`,,', `hi'))
address@hidden: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 @address@hidden, which quotes the 
first list
 element, with @address@hidden 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
address@hidden, 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
address@hidden@value{VERSION}/@/examples/@/foreach3.m4}:
+
address@hidden
+$ @kbd{m4 -I examples}
+include(`foreachq3.m4')
address@hidden
+undivert(`foreachq3.m4')dnl
address@hidden(`-1')
address@hidden foreachq(x, `item_1, item_2, ..., item_n', stmt)
address@hidden   quoted list, alternate improved version
address@hidden(`foreachq',
address@hidden(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
address@hidden  `, $2'))popdef(`$1')')
address@hidden(`_foreachq', `ifelse(`$#', `2', `',
address@hidden  `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
address@hidden    `, shift(shift(shift($@@)))'))')')
address@hidden'dnl
+traceon(`shift')debugmode(`aq')
address@hidden
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
address@hidden
address@hidden: -4- shift(`x', `x
address@hidden', `1', `2', `3', `4')
address@hidden: -3- shift(`x
address@hidden', `1', `2', `3', `4')
address@hidden: -2- shift(`1', `2', `3', `4')
address@hidden
address@hidden: -4- shift(`x', `x
address@hidden', `2', `3', `4')
address@hidden: -3- shift(`x
address@hidden', `2', `3', `4')
address@hidden: -2- shift(`2', `3', `4')
address@hidden
address@hidden: -4- shift(`x', `x
address@hidden', `3', `4')
address@hidden: -3- shift(`x
address@hidden', `3', `4')
address@hidden: -2- shift(`3', `4')
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
 @code{dquote_elt}.  Then @address@hidden 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 @address@hidden  But @code{foreachq}
+in preparation for calling @address@hidden, similary for
address@hidden as provided by @file{foreachq3.m4}.  But
address@hidden, as provided by @file{foreachq2.m4},
 evaluates unquoted list elements twice while visiting the first list
 element, once in @address@hidden and once in @address@hidden  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