Re: [PATCH] add m4_stack_foreach and m4_stack_foreach_lifo

[Eric Blake]

[phooey; sent to the wrong list on my first try]

Paolo Bonzini <bonzini <at> gnu.org> writes:

> > [putting my picky maintainer hat on]
> > Can we please maintain lexicographic sorting within the sections of
> > m4sugar?
> 
> Sure, it's just that I'm more used to topological order.

That works fine until you have circular dependencies (which we do; for
example,
before today's patches, m4_popdef used m4_foreach, which uses m4_popdef; the
recursion bottoms out, but which would you list first in topological
order?).
Whereas sorting by name always works ;)

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

In which case, here's my two patches to do it.  Part 1 adds two more macros:
m4_stack_foreach_sep{,_lifo} (using m4_curry in m4_copy is cute, but not as
efficient as directly constructing a macro call with multiple arguments; this
has the nice side effect of even fewer macros that can't be m4_copy'd).  And
part 2 uses _m4_stack_reverse to simplify the m4_set code.  Anyone want to
review this before I push?


>From 5080896aebf85e754ad8bbb3a8f9be8f96a44b8b Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 28 Oct 2008 15:11:16 -0600
Subject: [PATCH] Add m4_stack_foreach_sep.

* lib/m4sugar/m4sugar.m4 (m4_stack_foreach_sep)
(m4_stack_foreach_sep_lifo): New macros.
(_m4_stack_reverse): Adjust prototype, to support it.
(m4_copy): Use fewer macros.
* tests/m4sugar.at (m4@&address@hidden): Rename...
(m4@&address@hidden): ...and add m4_stack_foreach_sep tests.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   10 ++++++++++
 lib/m4sugar/m4sugar.m4 |   47 ++++++++++++++++++++++++++++++++++++++---------
 tests/m4sugar.at       |   18 ++++++++++++------
 3 files changed, 60 insertions(+), 15 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 0451fa9..5e80e94 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
 2008-10-28  Eric Blake  <address@hidden>

+       Add m4_stack_foreach_sep.
+       * lib/m4sugar/m4sugar.m4 (m4_stack_foreach_sep)
+       (m4_stack_foreach_sep_lifo): New macros.
+       (_m4_stack_reverse): Adjust prototype, to support it.
+       (m4_copy): Use fewer macros.
+       * tests/m4sugar.at (m4@&address@hidden): Rename...
+       (m4@&address@hidden): ...and add m4_stack_foreach_sep tests.
+
+2008-10-28  Eric Blake  <address@hidden>
+
        Use m4_map_args in more places.
        * lib/m4sugar/m4sugar.m4 (m4_defn, m4_dumpdef, m4_popdef)
        (m4_undefine, m4_combine): Use m4_map_args, rather than
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 9c24dac..f3481a8 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -536,10 +536,10 @@ m4_define([_m4_bpatsubsts],
 # definition.
 #
 # Some macros simply can't be renamed with this method: namely, anything
-# involved in the implementation of m4_stack_foreach and m4_curry.
+# involved in the implementation of m4_stack_foreach_sep.
 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])])])]dnl
+         [m4_stack_foreach_sep([$1], [m4_pushdef([$2],], [)])])]dnl
 [m4_ifdef([m4_location($1)], [m4_define([m4_location($2)], m4_location)])])


@@ -1194,13 +1194,8 @@ m4_define([m4_map_args_pair],
 # the active definition of MACRO (it will not be the topmost, and may not
 # be the one passed to FUNC either).
 #
-# 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.
-m4_define([_m4_stack_reverse],
-[m4_ifdef([$1], [m4_pushdef([$2],
_m4_defn([$1]))$3[]_m4_popdef([$1])$0($@)])])
-
+# Some macros simply can't be examined with this method: namely,
+# anything involved in the implementation of _m4_stack_reverse.
 m4_define([m4_stack_foreach],
 [_m4_stack_reverse([$1], [m4_tmp-$1])]dnl
 [_m4_stack_reverse([m4_tmp-$1], [$1], [$2(_m4_defn([m4_tmp-$1]))])])
@@ -1209,6 +1204,40 @@ m4_define([m4_stack_foreach_lifo],
 [_m4_stack_reverse([$1], [m4_tmp-$1], [$2(_m4_defn([m4_tmp-$1]))])]dnl
 [_m4_stack_reverse([m4_tmp-$1], [$1])])

+# m4_stack_foreach_sep(MACRO, PRE, POST, SEP)
+# m4_stack_foreach_sep_lifo(MACRO, PRE, POST, SEP)
+# ------------------------------------------------
+# Similar to m4_stack_foreach and m4_stack_foreach_lifo, in that every
+# definition of a pushdef stack will be visited.  But rather than
+# passing the definition as a single argument to a macro, this variant
+# expands the concatenation of PRE[]definition[]POST, and expands SEP
+# between consecutive expansions.  Note that m4_stack_foreach([a], [b])
+# is equivalent to m4_stack_foreach_sep([a], [b(], [)]).
+m4_define([m4_stack_foreach_sep],
+[_m4_stack_reverse([$1], [m4_tmp-$1])]dnl
+[_m4_stack_reverse([m4_tmp-$1], [$1], [$2[]_m4_defn([m4_tmp-$1])$3], [$4])])
+
+m4_define([m4_stack_foreach_sep_lifo],
+[_m4_stack_reverse([$1], [m4_tmp-$1], [$2[]_m4_defn([m4_tmp-$1])$3],
[$4])]dnl
+[_m4_stack_reverse([m4_tmp-$1], [$1])])
+
+
+# _m4_stack_reverse(OLD, NEW, ACTION, SEP)
+# ----------------------------------------
+# A recursive worker for pushdef stack manipulation.  Destructively
+# copy the OLD stack into the NEW, and expanding ACTION for each
+# iteration.  After the first iteration, SEP is promoted to the front
+# of ACTION.  The current definition is examined after the NEW has
+# been pushed but before OLD has been popped; this order is important,
+# as ACTION is permitted to operate on either _m4_defn([OLD]) or
+# _m4_defn([NEW]).  Since the operation is destructive, this macro is
+# generally used twice, with a temporary macro name holding the
+# swapped copy.
+m4_define([_m4_stack_reverse],
+[m4_ifdef([$1], [m4_pushdef([$2],
+  _m4_defn([$1]))$3[]_m4_popdef([$1])$0([$1], [$2], [$4$3])])])
+
+

 ## --------------------------- ##
 ## 9. More diversion support.  ##
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index af4c4d5..900b3eb 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -41,9 +41,11 @@ AT_CHECK_M4SUGAR([-o-],, [$2], [$3])
 ## m4_stack_foreach.  ##
 ## ------------------ ##

-AT_SETUP([m4@&address@hidden)
+AT_SETUP([m4@&address@hidden)

-AT_KEYWORDS([m4@&address@hidden m4@&address@hidden m4@&address@hidden)
+AT_KEYWORDS([m4@&address@hidden m4@&address@hidden)
+AT_KEYWORDS([m4@&address@hidden m4@&address@hidden)
+AT_KEYWORDS([m4@&address@hidden m4@&address@hidden)

 # Test the semantics of macros to walk stacked macro definitions.
 AT_CHECK_M4SUGAR_TEXT([[dnl
@@ -57,9 +59,11 @@ m4_stack_foreach([abc], [m4_n])
 m4_copy([abc], [foo])dnl
 m4_stack_foreach([foo], [m4_n])
 m4_stack_foreach_lifo([foo], [m4_n])
+m4_stack_foreach_sep([abc], [ m4_index([abcdefghijkl],], [)])
+m4_stack_foreach_sep_lifo([abc], [<], [>], [:])
 m4_pushdef([xyz], [123])dnl
 m4_pushdef([xyz], [456])dnl
-m4_define([doit], [[$1](m4_shift(m4_stack_foreach([xyz], [,m4_echo])))
+m4_define([doit], [[$1](m4_stack_foreach_sep([xyz], [m4_dquote(], [)], [,]))
 ])dnl
 m4_stack_foreach([abc], [doit])]],
 [[def
@@ -83,9 +87,11 @@ jkl
 ghi
 def

-def(123,456)
-ghi(123,456)
-jkl(123,456)
+ 3 6 9
+<jkl>:<ghi>:<def>
+def([123],[456])
+ghi([123],[456])
+jkl([123],[456])
 ]])

 AT_CLEANUP
-- 
1.6.0.2


>From 2503c3c972fbfb6a18c99f23bc1ef155ddcd8d55 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 28 Oct 2008 15:35:23 -0600
Subject: [PATCH] Use _m4_stack_reverse in m4_set.

* lib/m4sugar/m4sugar.m4 (_m4_set_contents_1)
(_m4_set_contents_2): Rewrite to share _m4_stack_reverse
implementation.
(m4_set_contents, m4_set_foreach, m4_set_list, m4_set_listc)
(m4_set_map): Adjust callers to new API.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    7 +++++++
 lib/m4sugar/m4sugar.m4 |   48
++++++++++++++++++++++--------------------------
 2 files changed, 29 insertions(+), 26 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 5e80e94..fb5bfde 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
 2008-10-28  Eric Blake  <address@hidden>

+       Use _m4_stack_reverse in m4_set.
+       * lib/m4sugar/m4sugar.m4 (_m4_set_contents_1)
+       (_m4_set_contents_2): Rewrite to share _m4_stack_reverse
+       implementation.
+       (m4_set_contents, m4_set_foreach, m4_set_list, m4_set_listc)
+       (m4_set_map): Adjust callers to new API.
+
        Add m4_stack_foreach_sep.
        * lib/m4sugar/m4sugar.m4 (m4_stack_foreach_sep)
        (m4_stack_foreach_sep_lifo): New macros.
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index f3481a8..fccca08 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -2687,28 +2687,26 @@ m4_define([m4_set_contains],
 # determines which version of _1 helper we use.
 m4_define([m4_set_contents],
 [m4_ifdef([_m4_set_cleanup($1)], [_$0_1c], [_$0_1])([$1])_$0_2([$1],
-    [_m4_defn([_m4_set_($1)])], [[$2]])])
+  [], [], [[$2]])])

 # _m4_set_contents_1(SET)
 # _m4_set_contents_1c(SET)
-# _m4_set_contents_2(SET, SEP, PREP)
-# ----------------------------------
-# Expand to a list of quoted elements currently in the set, separated
-# by SEP, and moving PREP in front of SEP on recursion.  To avoid
-# nesting limit restrictions, the algorithm must be broken into two
-# parts; _1 destructively copies the stack in reverse into
-# _m4_set_($1), producing no output; then _2 destructively copies
-# _m4_set_($1) back into the stack in reverse.  SEP is expanded while
-# _m4_set_($1) contains the current element, so a SEP containing
-# _m4_defn([_m4_set_($1)]) can produce output in the order the set was
-# created.  Behavior is undefined if SEP tries to recursively list or
-# modify SET in any way other than calling m4_set_remove on the
-# current element.  Use _1 if all entries in the stack are guaranteed
-# to be in the set, and _1c to prune removed entries.  Uses _m4_defn
-# and _m4_popdef for speed.
+# _m4_set_contents_2(SET, PRE, POST, SEP)
+# ---------------------------------------
+# Expand to a list of quoted elements currently in the set, each
+# surrounded by PRE and POST, and moving SEP in front of PRE on
+# recursion.  To avoid nesting limit restrictions, the algorithm must
+# be broken into two parts; _1 destructively copies the stack in
+# reverse into _m4_set_($1), producing no output; then _2
+# destructively copies _m4_set_($1) back into the stack in reverse.
+# If no elements were deleted, then this visits the set in the order
+# that elements were inserted.  Behavior is undefined if PRE/POST/SEP
+# tries to recursively list or modify SET in any way other than
+# calling m4_set_remove on the current element.  Use _1 if all entries
+# in the stack are guaranteed to be in the set, and _1c to prune
+# removed entries.  Uses _m4_defn and _m4_popdef for speed.
 m4_define([_m4_set_contents_1],
-[m4_ifdef([_m4_set([$1])], [m4_pushdef([_m4_set_($1)],
-    _m4_defn([_m4_set([$1])]))_m4_popdef([_m4_set([$1])])$0([$1])])])
+[_m4_stack_reverse([_m4_set([$1])], [_m4_set_($1)])])

 m4_define([_m4_set_contents_1c],
 [m4_ifdef([_m4_set([$1])],
@@ -2719,8 +2717,8 @@ m4_define([_m4_set_contents_1c],
          [_m4_popdef([_m4_set_cleanup($1)])])])

 m4_define([_m4_set_contents_2],
-[m4_ifdef([_m4_set_($1)], [m4_pushdef([_m4_set([$1])],
-    _m4_defn([_m4_set_($1)]))$2[]_m4_popdef([_m4_set_($1)])$0([$1],
[$3$2])])])
+[_m4_stack_reverse([_m4_set_($1)], [_m4_set([$1])],
+  [$2[]_m4_defn([_m4_set_($1)])$3], [$4])])

 # m4_set_delete(SET)
 # ------------------
@@ -2806,7 +2804,7 @@ m4_define([m4_set_empty],
 m4_define([m4_set_foreach],
 [m4_pushdef([$2])m4_ifdef([_m4_set_cleanup($1)],
     [_m4_set_contents_1c],
[_m4_set_contents_1])([$1])_m4_set_contents_2([$1],
-       [m4_define([$2], _m4_defn([_m4_set_($1)]))$3[]])m4_popdef([$2])])
+       [m4_define([$2],], [)$3[]])m4_popdef([$2])])

 # m4_set_intersection(SET1, SET2)
 # -------------------------------
@@ -2836,13 +2834,11 @@ m4_define([m4_set_intersection],
 # is output if there are any elements.
 m4_define([m4_set_list],
 [m4_ifdef([_m4_set_cleanup($1)], [_m4_set_contents_1c],
-         [_m4_set_contents_1])([$1])_m4_set_contents_2([$1],
-              [_m4_defn([_m4_set_($1)])], [,])])
+         [_m4_set_contents_1])([$1])_m4_set_contents_2([$1], [], [], [,])])

 m4_define([m4_set_listc],
 [m4_ifdef([_m4_set_cleanup($1)], [_m4_set_contents_1c],
-         [_m4_set_contents_1])([$1])_m4_set_contents_2([$1],
-              [,_m4_defn([_m4_set_($1)])])])
+         [_m4_set_contents_1])([$1])_m4_set_contents_2([$1], [,])])

 # m4_set_map(SET, ACTION)
 # -----------------------
@@ -2855,7 +2851,7 @@ m4_define([m4_set_listc],
 m4_define([m4_set_map],
 [m4_ifdef([_m4_set_cleanup($1)],
     [_m4_set_contents_1c],
[_m4_set_contents_1])([$1])_m4_set_contents_2([$1],
-       [$2(_m4_defn([_m4_set_($1)]))])])
+       [$2(], [)])])

 # m4_set_remove(SET, VALUE, [IF-PRESENT], [IF-ABSENT])
 # ----------------------------------------------------
-- 
1.6.0.2

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

Eric Blake             address@hidden

signature.asc
Description: OpenPGP digital signature