more m4sugar speedups

[Eric Blake]

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

Here's some more m4sugar speedups, inspired in part from analyzing how
ltsugar got some speedups.  Namely - when processing long lists (either
$@, or an argument that contains a boxed list), the fewer times the list
is expanded, the faster the processing can occur.  So this factors out
some places where long lists were being used.

2007-10-16  Eric Blake  <address@hidden>

        A few more m4sugar improvements, to benefit libtool.
        * lib/m4sugar/m4sugar.m4 (m4_bpatsubsts, _m4_shiftn): Reduce size
        of expansion by avoiding extra uses of address@hidden
        (m4_shiftn): Avoid extra dnl, and forbid shifting by 0.
        (_m4_cdr): New helper macro.
        (_m4_map, m4_map_sep): Use it to reduce size of expansion.
        (_m4_shift3): New helper macro.
        (_m4_foreach): Swap argument order, and use new macro to reduce
        size of expansion.
        * doc/autoconf.texi (Looping constructs) <m4_shiftn>: Mention that
        count must be positive.

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

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

iD8DBQFHFK+s84KuGfSFAYARAltlAJ9ZscZ7C6WYbgvcu1Wgsh5b+uJ8bQCghWBf
NHtNMlhkfHvbA3uNRbOqMwE=
=BwTr
-----END PGP SIGNATURE-----

>From f3b4cc104eddf0a124832094d3fc9bce03926520 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 16 Oct 2007 06:22:56 -0600
Subject: [PATCH] A few more m4sugar improvements, to benefit libtool.

* lib/m4sugar/m4sugar.m4 (m4_bpatsubsts, _m4_shiftn): Reduce size
of expansion by avoiding extra uses of address@hidden
(m4_shiftn): Avoid extra dnl, and forbid shifting by 0.
(_m4_cdr): New helper macro.
(_m4_map, m4_map_sep): Use it to reduce size of expansion.
(_m4_shift3): New helper macro.
(_m4_foreach): Swap argument order, and use new macro to reduce
size of expansion.
* doc/autoconf.texi (Looping constructs) <m4_shiftn>: Mention that
count must be positive.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   12 +++++++++
 doc/autoconf.texi      |    3 +-
 lib/m4sugar/m4sugar.m4 |   65 +++++++++++++++++++++++++++++++++++++----------
 3 files changed, 65 insertions(+), 15 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 65a2d4c..930f3ba 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,17 @@
 2007-10-16  Eric Blake  <address@hidden>
 
+       A few more m4sugar improvements, to benefit libtool.
+       * lib/m4sugar/m4sugar.m4 (m4_bpatsubsts, _m4_shiftn): Reduce size
+       of expansion by avoiding extra uses of address@hidden
+       (m4_shiftn): Avoid extra dnl, and forbid shifting by 0.
+       (_m4_cdr): New helper macro.
+       (_m4_map, m4_map_sep): Use it to reduce size of expansion.
+       (_m4_shift3): New helper macro.
+       (_m4_foreach): Swap argument order, and use new macro to reduce
+       size of expansion.
+       * doc/autoconf.texi (Looping constructs) <m4_shiftn>: Mention that
+       count must be positive.
+
        * doc/autoconf.texi (Evaluation Macros) <m4_expand>: Fix typo.
        Reported by Ralf Wildenhues.
 
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index 22f608a..19ad110 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -10670,7 +10670,8 @@ The deprecated macro @code{AC_FOREACH} is an alias of
 @msindex{shiftn}
 @code{m4_shiftn} performs @var{count} iterations of @code{m4_shift},
 along with validation that enough arguments were passed in to match the
-shift count.  @code{m4_shift2} and @code{m4_shift3} are specializations
+shift count, and that the count is positive.  @code{m4_shift2} and
address@hidden are specializations
 of @code{m4_shiftn}, introduced in Autoconf 2.62, and are more efficient
 for two and three shifts, respectively.
 @end defmac
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 9b3a615..e63d470 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -398,6 +398,18 @@ m4_define([m4_cdr],
        [$#], 1, [],
        [m4_dquote(m4_shift($@))])])
 
+# _m4_cdr(LIST)
+# -------------
+# Like m4_cdr, except include a leading comma unless only one element
+# remains.  Why?  Because comparing a large list against [] is more
+# expensive in expansion time than comparing the number of arguments; so
+# _m4_cdr can be used to reduce the number of arguments when it is time
+# to end recursion.
+m4_define([_m4_cdr],
+[m4_if([$#], 1, [],
+       [, m4_dquote(m4_shift($@))])])
+
+
 
 # m4_cond(TEST1, VAL1, IF-VAL1, TEST2, VAL2, IF-VAL2, ..., [DEFAULT])
 # -------------------------------------------------------------------
@@ -439,13 +451,12 @@ m4_define([m4_cond],
 # -------------------
 # Invoke MACRO($1), MACRO($2) etc. where $1, $2... are the elements
 # of LIST (which can be lists themselves, for multiple arguments MACROs).
-m4_define([m4_fst], [$1])
 m4_define([m4_map],
 [m4_if([$2], [[]], [],
        [_m4_map([$1], [$2])])])
 m4_define([_m4_map],
-[m4_ifval([$2],
-         [$1(m4_fst($2))[]_m4_map([$1], m4_cdr($2))])])
+[m4_if([$#], [1], [],
+       [$1(m4_unquote(m4_car($2)))[]_m4_map([$1]_m4_cdr($2))])])
 
 
 # m4_map_sep(MACRO, SEPARATOR, LIST)
@@ -455,7 +466,7 @@ m4_define([_m4_map],
 # arguments MACROs).
 m4_define([m4_map_sep],
 [m4_if([$3], [[]], [],
-       [$1(m4_fst($3))[]_m4_map([$2[]$1], m4_cdr($3))])])
+       [$1(m4_unquote(m4_car($3)))[]_m4_map([$2[]$1]_m4_cdr($3))])])
 
 
 ## ---------------------------------------- ##
@@ -483,7 +494,7 @@ m4_define([m4_map_sep],
 m4_define([m4_bpatsubsts],
 [m4_if([$#], 0, [m4_fatal([$0: too few arguments: $#])],
        [$#], 1, [m4_fatal([$0: too few arguments: $#: $1])],
-       [$#], 2, [m4_builtin([patsubst], $@)],
+       [$#], 2, [m4_builtin([patsubst], [$1], [$2])],
        [_$0(address@hidden(m4_eval($# & 1), 0, [,]))])])
 m4_define([_m4_bpatsubsts],
 [m4_if([$#], 2, [$1],
@@ -565,14 +576,24 @@ m4_define([m4_popdef],
 # m4_shiftn(N, ...)
 # -----------------
 # Returns ... shifted N times.  Useful for recursive "varargs" constructs.
+#
+# Autoconf does not use this macro, because it is inherently slower than
+# calling the common cases of m4_shift2 or m4_shift3 directly.  But it
+# might as well be fast for other clients, such as Libtool.  One way to
+# do this is to expand $@ only once in _m4_shiftn (otherwise, for long
+# lists, the expansion of m4_if takes twice as much memory as what the
+# list itself occupies, only to throw away the unused branch).  The end
+# result is strictly equivalent to
+#   m4_if([$1], 1, [m4_shift(,m4_shift(m4_shift($@)))],
+#         [_m4_shiftn(m4_decr([$1]), m4_shift(m4_shift($@)))])
+# but with the final `m4_shift(m4_shift($@)))' shared between the two
+# paths.  The first leg uses a no-op m4_shift(,$@) to balance out the ().
 m4_define([m4_shiftn],
-[m4_assert(0 <= $1 && $1 < $#)dnl
-_m4_shiftn($@)])
+[m4_assert(0 < $1 && $1 < $#)_$0($@)])
 
 m4_define([_m4_shiftn],
-[m4_if([$1], 0,
-       [m4_shift($@)],
-       [_m4_shiftn(m4_eval([$1]-1), m4_shift(m4_shift($@)))])])
+[m4_if([$1], 1, [m4_shift(],
+       [$0(m4_decr([$1])]), m4_shift(m4_shift($@)))])
 
 # m4_shift2(...)
 # m4_shift3(...)
@@ -581,6 +602,17 @@ m4_define([_m4_shiftn],
 m4_define([m4_shift2], [m4_shift(m4_shift($@))])
 m4_define([m4_shift3], [m4_shift(m4_shift(m4_shift($@)))])
 
+# _m4_shift3(...)
+# ---------------
+# Like m4_shift3, except include a leading comma unless there were exactly
+# three arguments.  Why?  Because in recursion, it is nice to distinguish
+# between 1 element left and 0 elements left, based on how many arguments
+# this shift expands to.
+m4_define([_m4_shift3],
+[m4_if([$#], [3], [],
+       [, m4_shift(m4_shift(m4_shift($@)))])])
+
+
 # m4_undefine(NAME)
 # -----------------
 # Like the original, except don't tolerate undefining something which is
@@ -827,13 +859,18 @@ m4_if(m4_defn([$1]), [$2], [],
 #     => -active--active-
 #
 # This macro is called frequently, so avoid extra expansions such as
-# m4_ifval and dnl.
+# m4_ifval and dnl.  Also, since $2 might be quite large, try to use it
+# as little as possible in _m4_foreach; each extra use requires that much
+# more memory for expansion.  So, rather than directly compare $2 against
+# [] and use m4_car/m4_cdr for recursion, we instead unbox the list (which
+# requires swapping the argument order in the helper) and use _m4_shift3
+# to detect when recursion is complete.
 m4_define([m4_foreach],
-[m4_pushdef([$1])_$0($@)m4_popdef([$1])])
+[m4_pushdef([$1])_$0([$1], [$3]m4_if([$2], [], [], [, $2]))m4_popdef([$1])])
 
 m4_define([_m4_foreach],
-[m4_if([$2], [], [],
-       [m4_define([$1], m4_car($2))$3[]$0([$1], m4_cdr($2), [$3])])])
+[m4_if([$#], [2], [],
+       [m4_define([$1], [$3])$2[]$0([$1], [$2]_m4_shift3($@))])])
 
 
 # m4_foreach_w(VARIABLE, LIST, EXPRESSION)
-- 
1.5.3.2