Re: documentation ideas from autoconf

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

> Fortunately, autoconf had already resolved the issue, as a side effect of 
> writing a more efficient copy algorithm.  So I'm applying this followup to 
> branch-1.6 and master, then backporting the series of doc patches to branch-
1.4:

> +++ b/examples/stack_sep.m4
> @@ -0,0 +1,17 @@
> +divert(`-1')
> +# stack_foreach_sep(macro, pre, post, sep)
> +# Invoke PRE`'defn`'POST with a single argument of each definition
> +# from the definition stack of MACRO, starting with the oldest, and
> +# separated by SEP between definitions.
> +define(`stack_foreach_sep',
> +`_stack_reverse_sep(`$1', `tmp-$1')'dnl
> +`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
> +# stack_foreach_sep_lifo(macro, pre, post, sep)
> +# Like stack_foreach_sep, but starting with the newest definition.
> +define(`stack_foreach_sep_lifo',
> +`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
> +`_stack_reverse_sep(`tmp-$1', `$1')')
> +define(`_stack_reverse_sep',
> +`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0(
> +  `$1', `$2', `$4`'$3')')')
> +divert`'dnl

Oops.  That implementation is quadratic, as I just discovered on the autoconf 
list today.  I'm installing this on all three branches, to provide a linear 
alternative.


From: Eric Blake <[email protected]>
Date: Thu, 12 Feb 2009 14:59:08 -0700
Subject: [PATCH] Avoid quadratic code when walking definition stack.

* examples/stack_sep.m4: Use linear, not quadratic
implementation.
* doc/m4.texinfo (Improved copy): Fix documentation and add test,
based on recent autoconf bug fix.

Signed-off-by: Eric Blake <[email protected]>
---
 ChangeLog             |    8 ++++++++
 doc/m4.texinfo        |   45 +++++++++++++++++++++++++++++++++++----------
 examples/stack_sep.m4 |    6 +++---
 3 files changed, 46 insertions(+), 13 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c55e79f..3495018 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2009-02-12  Eric Blake  <[email protected]>
+
+	Avoid quadratic code when walking definition stack.
+	* examples/stack_sep.m4: Use linear, not quadratic
+	implementation.
+	* doc/m4.texinfo (Improved copy): Fix documentation and add test,
+	based on recent autoconf bug fix.
+
 2009-01-24  Eric Blake  <[email protected]>

 	Add URLs to --help output.
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index c09d771..9bbfcfd 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -8199,13 +8199,21 @@ Improved copy
 construct macro calls with more than one argument, without passing
 builtin tokens through a macro call.  It is likewise possible to
 directly reference the stack definitions without a macro call, by
-leaving @var{pre} and @var{post} empty.  The new macro also adds a
-separator that is only output after the first iteration of the helper
-@code{_stack_reverse_sep}, implemented by prepending the original
-@var{sep} to @var{pre} and omitting a @var{sep} argument in subsequent
-iterations.  As an added bonus, using @code{stack_foreach_sep} to
-implement @code{copy} performs fewer macro invocations.  The improved
-stack walking macros are available in
+leaving @var{pre} and @var{post} empty.  Thus, in addition to fixing
+@code{copy} on builtin tokens, it also executes with fewer macro
+invocations.
+
+The new macro also adds a separator that is only output after the first
+iteration of the helper @code{_stack_reverse_sep}, implemented by
+prepending the original @var{sep} to @var{pre} and omitting a @var{sep}
+argument in subsequent iterations.  Note that the empty string that
+separates @var{sep} from @var{pre} is provided as part of the fourth
+argument when originally calling @code{_stack_reverse_sep}, and not by
+writing @code{$4`'$3} as the third argument in the recursive call; while
+the other approach would give the same output, it does so at the expense
+of increasing the argument size on each iteration of
+@code{_stack_reverse_sep}, which results in quadratic instead of linear
+execution time.  The improved stack walking macros are available in
 @file{m4-@value{VERSION}/@/examples/@/stack_sep.m4}:

 @comment examples
@@ -8238,18 +8246,35 @@ Improved copy
 @result{}# separated by SEP between definitions.
 @result{}define(`stack_foreach_sep',
 @result{}`_stack_reverse_sep(`$1', `tmp-$1')'dnl
-@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
+@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')')
 @result{}# stack_foreach_sep_lifo(macro, pre, post, sep)
 @result{}# Like stack_foreach_sep, but starting with the newest definition.
 @result{}define(`stack_foreach_sep_lifo',
-@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
+@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl
 @result{}`_stack_reverse_sep(`tmp-$1', `$1')')
 @result{}define(`_stack_reverse_sep',
 @result{}`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0(
-@result{}  `$1', `$2', `$4`'$3')')')
+@result{}  `$1', `$2', `$4$3')')')
 @result{}divert`'dnl
 @end example

+@ignore
+@comment Not worth putting in the manual, but make sure that
+@comment stack_foreach_sep has linear performance.
+
+@comment examples
+@example
+$ @kbd {m4 -I examples}
+include(`forloop3.m4')include(`stack_sep.m4')dnl
+forloop(`i', `1', `10000', `pushdef(`s', i)')
+@result{}
+define(`colon', `:')define(`dash', `-')
+@result{}
+len(stack_foreach_sep(`s', `dash', `', `colon'))
+@result{}58893
+@end example
+@end ignore
+
 @node Improved m4wrap
 @section Solution for @code{m4wrap}

diff --git a/examples/stack_sep.m4 b/examples/stack_sep.m4
index b11bc83..767d15e 100644
--- a/examples/stack_sep.m4
+++ b/examples/stack_sep.m4
@@ -5,13 +5,13 @@ divert(`-1')
 # separated by SEP between definitions.
 define(`stack_foreach_sep',
 `_stack_reverse_sep(`$1', `tmp-$1')'dnl
-`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')')
+`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')')
 # stack_foreach_sep_lifo(macro, pre, post, sep)
 # Like stack_foreach_sep, but starting with the newest definition.
 define(`stack_foreach_sep_lifo',
-`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl
+`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl
 `_stack_reverse_sep(`tmp-$1', `$1')')
 define(`_stack_reverse_sep',
 `ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0(
-  `$1', `$2', `$4`'$3')')')
+  `$1', `$2', `$4$3')')')
 divert`'dnl
-- 
1.6.1.2