m4_reverse

[Eric Blake]

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

Since m4_set_dump outputs data in reverse order, I decided to add
m4_reverse, borrowed from the m4 manual.  It turns out that m4_reverse
doesn't help m4_set_dump (first, the output of m4_set_dump is a single
string, rather than a list of arguments, so there is nothing to reverse;
second, the point of m4_set_dump is to be fast, and reversing the order of
the elements defeats the speed gains), but it still makes sense as an
m4sugar primitive for any other uses.

In the process of testing it, I discovered that the current m4_list_cmp
implementation on an m4_reverse'd list was tricky enough to foil the
current m4 branch-1.6 heuristics on whether $@ recursion is occurring:
behavior broke down into quadratic time because the m4_cdr calls hid the
lists to the point that m4 failed to create back-references and ended up
reparsing the list on every iteration.  This patch includes a rewrite of
m4_list_cmp to skip m4_cdr and make the $@ recursion explicit to the
current m4 (although I might still try to patch m4 to recognize the
admittedly corner-case recursion pattern); in addition to giving linear
instead of quadratic behavior, it also reduces m4_list_cmp from 17 to 15
macros per iteration.

- --
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

iEYEARECAAYFAkiPGG8ACgkQ84KuGfSFAYBCFgCZAZt25T5VtdqpinHk1awBo8kV
/8sAoLGSjY+nClLQX8RUo/2s6lxhygsz
=3ny9
-----END PGP SIGNATURE-----

>From 4766c77f4256ff3e854cb2b7155ebae6bf20fdf5 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 07:12:26 -0600
Subject: [PATCH] Add m4_reverse, and improve m4_list_cmp.

* lib/m4sugar/m4sugar.m4 (m4_reverse): New macro.
(m4_list_cmp): Rewrite to give linear behavior with M4 1.6 on an
m4_reverse'd list.
* lib/m4sugar/foreach.m4 (m4_reverse): Add the M4 1.4.x
counterpart.
* tests/m4sugar.at (recursion): Test it.
* doc/autoconf.texi (Evaluation Macros) <m4_reverse>: Document
it.
(Text processing Macros) <m4_append>: Cross-reference to m4_set.
* NEWS: Mention new macro.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   14 ++++++++++++++
 NEWS                   |    2 +-
 doc/autoconf.texi      |   16 +++++++++++++++-
 lib/m4sugar/foreach.m4 |   13 +++++++++++++
 lib/m4sugar/m4sugar.m4 |   28 +++++++++++++++++++++-------
 tests/m4sugar.at       |    7 ++++---
 6 files changed, 68 insertions(+), 12 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 1a58651..7019f37 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2008-07-29  Eric Blake  <address@hidden>
+
+       Add m4_reverse, and improve m4_list_cmp.
+       * lib/m4sugar/m4sugar.m4 (m4_reverse): New macro.
+       (m4_list_cmp): Rewrite to give linear behavior with M4 1.6 on an
+       m4_reverse'd list.
+       * lib/m4sugar/foreach.m4 (m4_reverse): Add the M4 1.4.x
+       counterpart.
+       * tests/m4sugar.at (recursion): Test it.
+       * doc/autoconf.texi (Evaluation Macros) <m4_reverse>: Document
+       it.
+       (Text processing Macros) <m4_append>: Cross-reference to m4_set.
+       * NEWS: Mention new macro.
+
 2008-07-28  Eric Blake  <address@hidden>
 
        Avoid _m4_shiftn for m4 1.6 speedup.
diff --git a/NEWS b/NEWS
index e7d1d1c..9737c34 100644
--- a/NEWS
+++ b/NEWS
@@ -20,7 +20,7 @@ GNU Autoconf NEWS - User visible changes.
    allowing the output of unbalanced parantheses in more contexts.
 
 ** The following m4sugar macros are new:
-   m4_joinall  m4_set_add  m4_set_add_all  m4_set_contains
+   m4_joinall  m4_reverse  m4_set_add  m4_set_add_all  m4_set_contains
    m4_set_contents  m4_set_delete  m4_set_difference  m4_set_dump
    m4_set_empty  m4_set_foreach  m4_set_intersection  m4_set_list
    m4_set_listc  m4_set_remove  m4_set_size  m4_set_union
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index 6ac8449..b3b416c 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -10997,6 +10997,19 @@ quotes.  This effectively collapses multiple arguments 
into one,
 although it loses whitespace after unquoted commas in the process.
 @end defmac
 
address@hidden m4_reverse (@var{arg}, @dots{})
address@hidden
+Outputs each argument with the same level of quoting, but in reverse
+order, and with space following each comma for readability.
+
address@hidden
+m4_define([active], [ACT,IVE])
address@hidden
+m4_reverse(active, [active])
address@hidden, IVE, ACT
address@hidden example
address@hidden defmac
+
 @defmac m4_unquote (@var{arg}, @dots{})
 @msindex{unquote}
 This macro was introduced in Autoconf 2.62.  Expand each argument,
@@ -11082,7 +11095,8 @@ Note that @code{m4_append} can scale linearly in the 
length of the final
 string, depending on the quality of the underlying M4 implementation,
 while @code{m4_append_uniq} has an inherent quadratic scaling factor.
 If an algorithm can tolerate duplicates in the final string, use the
-former for speed.
+former for speed.  If duplicates must be avoided, consider using
address@hidden instead (@pxref{Set manipulation Macros}).
 
 @example
 m4_define([active], [ACTIVE])dnl
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 0b1d05c..7cc4358 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -154,6 +154,19 @@ m4_define([m4_do],
 m4_define([m4_dquote_elt],
 [m4_shift(m4_foreach([_m4_elt], address@hidden, 
[,m4_dquote(_m4_defn([_m4_elt]))]))])
 
+# m4_reverse(ARGS)
+# ----------------
+# Output ARGS in reverse order.
+#
+# Invoke _m4_r($@) with the temporary _m4_r built as
+#   [$m], [$m-1], ..., [$2], [$1]_m4_popdef([_m4_r])
+m4_define([m4_reverse],
+[m4_if([$#], [0], [], [$#], [1], [[$1]],
+[m4_define([_m4_r], m4_dquote([$$#])m4_pushdef([_m4_r],
+    m4_decr([$#]))_m4_for([_m4_r], [1], [-1],
+    [[, ]m4_dquote([$]_m4_r)])[_m4_popdef([_m4_r])])_m4_r($@)])])
+
+
 # m4_map(MACRO, LIST)
 # -------------------
 # Invoke MACRO($1), MACRO($2) etc. where $1, $2... are the elements
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 293e38e..54439ce 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -802,6 +802,14 @@ m4_define([_m4_quote],
 [m4_if([$#], [0], [], [[$*]])])
 
 
+# m4_reverse(ARGS)
+# ----------------
+# Output ARGS in reverse order.
+m4_define([m4_reverse],
+[m4_if([$#], [0], [], [$#], [1], [[$1]],
+       [$0(m4_shift($@)), [$1]])])
+
+
 # m4_unquote(ARGS)
 # ----------------
 # Remove one layer of quotes from each ARG, performing one level of
@@ -2151,15 +2159,21 @@ m4_define([m4_cmp],
 # expansion includes the name of the macro to invoke on the tail, either
 # m4_ignore or m4_unquote.  This is particularly useful when comparing
 # long lists, since less text is being expanded for deciding when to end
-# recursion.
+# recursion.  The recursion is between a pair of macros that alternate
+# which list is trimmed by one element; this is more efficient than
+# calling m4_cdr on both lists from a single macro.
 m4_define([m4_list_cmp],
-[m4_if([$1$2], [], 0,
-       [$1], [], [$0(0, [$2])],
-       [$2], [], [$0([$1], 0)],
-       [$1], [$2], 0,
-       [_$0(m4_cmp(m4_car($1), m4_car($2)))([$0(m4_cdr($1), m4_cdr($2))])])])
+[m4_if([$1], [$2], [0], [_m4_list_cmp_1([$1], $2)])])
+
 m4_define([_m4_list_cmp],
-[m4_if([$1], 0, [m4_unquote], [$1m4_ignore])])
+[m4_if([$1], [], [0m4_ignore], [$2], [0], [m4_unquote], [$2m4_ignore])])
+
+m4_define([_m4_list_cmp_1],
+[_m4_list_cmp_2([$2], [m4_shift2($@)], $1)])
+
+m4_define([_m4_list_cmp_2],
+[_m4_list_cmp([$1$3], m4_cmp([$3+0], [$1+0]))(
+  [_m4_list_cmp_1(m4_dquote(m4_shift3($@)), $2)])])
 
 # m4_max(EXPR, ...)
 # m4_min(EXPR, ...)
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index d82675e..c69e37e 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -757,7 +757,8 @@ AT_CLEANUP
 AT_SETUP([recursion])
 
 AT_KEYWORDS([m4@&address@hidden m4@&address@hidden m4@&address@hidden 
m4@&address@hidden
-m4@&address@hidden m4@&address@hidden m4@&address@hidden m4@&address@hidden 
m4@&address@hidden)
+m4@&address@hidden m4@&address@hidden m4@&address@hidden m4@&address@hidden 
m4@&address@hidden
+m4@&address@hidden)
 
 dnl This test completes in a reasonable time if m4_foreach is linear,
 dnl but thrashes if it is quadratic.  If we are testing with m4 1.4.x,
@@ -776,7 +777,7 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
   [,i]))m4_for([i], [2], [10000], [], [,i]))
 m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
 m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
-            m4_dquote(1m4_for([i], [2], [10000], [], [,i]), [0]))
+  m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
 m4_divert_pop(0)
@@ -813,7 +814,7 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
   [,i]))m4_for([i], [2], [10000], [], [,i]))
 m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
 m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
-            m4_dquote(1m4_for([i], [2], [10000], [], [,i]), [0]))
+  m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
 m4_divert_pop(0)
-- 
1.5.6.4