Re: [PATCH] add m4_stack_foreach and m4_stack_foreach_lifo

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Paolo Bonzini on 10/28/2008 5:57 AM:
> This patch extracts the pushdef-stack manipulation code of m4_copy into
> new general-purpose macros.  The resulting m4_copy implementation is quite
> elegant, using m4_curry to push new definitions.

m4_dumpdefs can be rewritten to this interface.

m4_set also uses pushdef stack manipulation, and it may be possible to
rewrite _m4_set_contents_{1,1c,2} to use this idiom.

m4_curry is nice and general, but it may be possible to write a more
efficient interface where the user supplies pre/post/sep (and can use
constructs like [foo(argpre,], [,argpost])], [[]], rather than having to
use m4_curry to supply argpre and with no elegant way to supply argpost).
 But the lack of a better interface shouldn't stop this patch.  Maybe
something along the lines of:
m4_stack_foreach_sep(stack, pre, post, sep)
such that m4_stack_foreach is a convenience wrapper for:
m4_define([m4_stack_foreach], [$0_sep([$1], [$2(], [)])])

> 
> The disadvantage is that more macros cannot be copied with m4_copy,
> including m4_curry and m4_stack_foreach.

Again, I already proposed a solution for that; maybe it's time to
implement it?  The idea is that if the witness [_m4_nostack(macro)] is
defined, then it is a contract that [macro] will never be a pushdef stack
(because it is so intrinsic to m4sugar operation), therefore, we can
directly call func(m4_defn(macro)) rather than going through a pushdef
stack.  But that can be a followup patch, if we decide it is worth it.
Technically, we could rewrite m4_pushdef as a wrapper that enforces the
contract of _m4_nostack(macro), but if we did that, I would want to
provide a faster _m4_pushdef that avoids the overhead, for internal use
(similar to the current m4_popdef/_m4_popdef).

> 
> The next patch will use the macros to implement the m4 diversion and
> expansion stacks in a nicer way, and without possibly quadratic behavior.

Sweet - I was thinking about that very inefficiency as my next project; it
looks like you are beating me to it!  There is no maybe about the
behavior; the current implementation IS quadratic (at least in memory, but
since it mallocs, probably also in time), because every round of
m4_expansion_stack_push is copying all previous rounds of text into the
new definition.

> 
> Ok?

I want to see a resubmission with these issues addressed, before I give
approval.

> 
>       * lib/m4sugar/m4sugar.m4 (_m4_stack_reverse): New from _m4_copy.
>       (m4_stack_foreach, m4_stack_foreach_lifo): New.
>       (m4_copy): Use m4_stack_foreach and m4_curry.
>       * tests/m4sugar.at (m4_stack_foreach): New test.

Do we want to document this in the manual and NEWS, or leave it
undocumented until we've played with it a bit longer?

>  
> +# m4_stack_foreach(MACRO, FUNC)
> +# m4_stack_foreach_lifo(MACRO, FUNC)
> +# -----------------------------

Extend the ---.

> +# Pass each stacked definition of MACRO to the one-argument macro FUNC.
> +# m4_stack_foreach proceeds in FIFO order, while m4_stack_foreach_lifo
> +# processes the topmost definitions first.
> +#
> +# The recursive worker _m4_stack_reverse destructively swaps the order of a
> +# stack.  We use a temporary stack, and swap directions twice.  Some macros
> +# simply can't be examined with this method: namely, anything involved
> +# in the implementation of _m4_stack_reverse.

One more caveat to document - FUNC must not arbitrarily pushdef or popdef
MACRO, or traversal will be broken.  Except maybe we want to document that
a single m4_popdef is supported, as a way to prune intermediate stack
values without affecting the topmost definition.

> +m4_define([_m4_stack_reverse],
> +[m4_ifdef([$1], [m4_pushdef([$2], 
> _m4_defn([$1]))$3[]_m4_popdef([$1])$0($@)])])
> +
> +m4_define([m4_stack_foreach],
> +[_m4_stack_reverse([$1], [m4_tmp])]dnl
> +[_m4_stack_reverse([m4_tmp], [$1], [$2(_m4_defn([m4_tmp]))])])

In the context of m4_copy, using m4_tmp was safe, since the user could not
inject arbitrary macro expansions into the traversal.  But it is now
conceivable that the user could pass a FUNC that does a nested
m4_stack_foreach on a different macro.  Therefore, we need to use a
temporary macro name based on composition with MACRO (note how
_m4_set_contents_1 does this), so that nested traversals don't collide on
the same m4_tmp temporary name.

> +# Some macros simply can't be renamed with this method: namely, anything
> +# involved in the implementation of m4_stack_foreach and m4_curry.
>  m4_define([m4_copy],
>  [m4_ifdef([$2], [m4_fatal([$0: won't overwrite defined macro: $2])],
> +       [m4_stack_foreach([$1], [m4_curry([m4_pushdef], 
> [$2])])m4_ifdef([m4_location($1)],
> +[m4_define([m4_location($2)], m4_location)])])])

That IS slick.  I think I'm going to add something like that to the m4 manual!

> +AT_SETUP([m4@&address@hidden)
> +
> +AT_KEYWORDS([m4@&address@hidden m4@&address@hidden m4@&address@hidden 
> m4@&address@hidden)

The test title is automatically a keyword, so the second listing of
m4_stack_foreach is redundant.  Let's also add a test of m4_dumpdefs to
this test.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkkHDmEACgkQ84KuGfSFAYDWsACeLL5iOP13LX229a/q5+hpxd6z
yIkAniA9B4c8UXe0Ott1jPYeTH07jLcp
=H0y1
-----END PGP SIGNATURE-----