Avoid O(n^2) recursion in m4sugar

[Eric Blake]

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

I'm committing this.  Without it, there were a surprising number of
quadratic macros when m4sugar is running atop m4 1.4.x; running on m4 1.6
made them linear, but we might as well be nice to people who aren't
running bleeding edge builds (seeing as how m4 1.6 isn't released yet ;).
~ The rewrite is a rather interesting idiom - define a temporary macro
whose contents are made from m4_for iterating over boilerplate text, with
necessary m4 tricks to get $n inserted into the definition, then finally
invoke the temporary macro with $@; it relies on the fact that m4 1.4.x
expands $10 as the tenth argument without issuing a warning (although in a
future m4 version, this will either issue a warning, or obey POSIX
altogether by expanding to the first argument concatenated with a literal
0).  By keeping $@ out of the iteration, m4 1.4.x no longer has to scan a
quadratic number of arguments as each iteration trims one the list by one
element; meanwhile, m4_for is already linear, since the recursion is based
on the contents of a counter rather than the length of a list.

In every case, the rewrite guarantees linear behavior, but is more
expensive in time and memory than the counterpart using linear recursion
on $@ (at least, when testing both methods on 1.6).  On the other hand,
all it takes is one large usage changed from quadratic to linear to more
than recover that time and memory when running on m4 1.4.x.  The patch
makes a runtime decision during m4_init on which version to use, so that
m4 1.6 users automatically benefit from the faster of two available linear
methods, while m4 1.4.x users get the only linear method.  The other
reason for the runtime decision is so that if future m4 versions warn
about the switch to POSIX semantics in $10, we won't be using the m4_for
rewrites and won't be tripping the warning.

For a demonstration of how much a good algorithm matters, I intentionally
wrote a stress test that hands 10000 arguments to the various improved
macros.  When I was writing the testsuite, I temporarily replaced my new
foreach.m4 with an empty file, and had to kill m4-1.4.11 after taking
minutes and more than half a gigabyte with no apparent end in sight; but
the full patch, the test completed successfully in just a few seconds, and
with a memory peak well under 8M.  But most users of these macros aren't
doing huge recursions; so the difference in time between quadratic and
linear on small input is hardly noticeable.  Running 'autoconf -f' on
coreutils yielded these results (best time/peak memory):

                pre             post
m4-1.4.11       21.485/4.9M     21.375/4.9M
branch-1.6      22.580/5.3M     23.140/5.3M

In my timings, the various runs were all so close together that I could
not cleanly declare any noticeable speedup for either m4-1.4.11 (which
uses the new foreach-based iteration) or m4-1.6 (which is theoretically
unchanged except for the time lost in m4_init deciding to stick with the
slightly faster $@ recursion), and no real memory differences.  I think
the largest recursion I found was a m4_text_wrap (m4_foreach_w under the
hood) on a lengthy help message, and that was still less than 100 iterations.

The only remaining recursive macros which are still quadratic in 1.4.x but
linear in 1.6 are m4_bmatch, m4_bpatsubsts, and m4_cond.  I still haven't
been able to come up with a clean way to convert those into m4_for-based
iteration followed by an application of address@hidden

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

iEYEARECAAYFAkiKaBMACgkQ84KuGfSFAYDgZgCg1o3CaLATzG0Xysh+Of31TKdM
KSkAoMnOGGL3isuTV52ByVkEJ1VI+nR4
=apUg
-----END PGP SIGNATURE-----

>From dbb9fe36bfb9cdd2d1c4b13a752ca3bb7bb049a7 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 25 Jul 2008 15:17:38 -0600
Subject: [PATCH] Provide O(n) replacement macros for M4 1.4.x.

* lib/m4sugar/foreach.m4: New file.
(m4_foreach, m4_case, _m4_shiftn, m4_do, m4_dquote_elt, _m4_map)
(m4_join, m4_joinall, m4_list_cmp, _m4_minmax): Replace m4sugar
macros based on $@ recursion [fast on M4 1.6, but quadratic on M4
1.4.x] with versions based on m4_for/m4_foreach [slow on 1.6, but
linear on 1.4.x].
* lib/m4sugar/m4sugar.m4 (m4_init): Dynamically load new file if
older M4 is assumed.
(m4_map_sep): Optimize.
(m4_max, m4_min): Refactor, by adding...
(_m4_max, _m4_min, _m4_minmax): ...more efficient helpers.
(m4_defn, m4_popdef, m4_undefine): Use foreach recursion.
* lib/m4sugar/Makefile.am (dist_m4sugarlib_DATA): Distribute new
file.
* tests/m4sugar.at (M4 loops): Add a stress test that takes
forever if m4_foreach and friends are quadratic.
* NEWS: Mention this.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog               |   21 ++++
 NEWS                    |    7 ++
 lib/m4sugar/Makefile.am |    4 +-
 lib/m4sugar/foreach.m4  |  236 +++++++++++++++++++++++++++++++++++++++++++++++
 lib/m4sugar/m4sugar.m4  |   59 +++++++++----
 tests/m4sugar.at        |   84 +++++++++++++++++
 6 files changed, 392 insertions(+), 19 deletions(-)
 create mode 100644 lib/m4sugar/foreach.m4

diff --git a/ChangeLog b/ChangeLog
index eda6995..1cc7cd6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,24 @@
+2008-07-25  Eric Blake  <address@hidden>
+
+       Provide O(n) replacement macros for M4 1.4.x.
+       * lib/m4sugar/foreach.m4: New file.
+       (m4_foreach, m4_case, _m4_shiftn, m4_do, m4_dquote_elt, _m4_map)
+       (m4_join, m4_joinall, m4_list_cmp, _m4_minmax): Replace m4sugar
+       macros based on $@ recursion [fast on M4 1.6, but quadratic on M4
+       1.4.x] with versions based on m4_for/m4_foreach [slow on 1.6, but
+       linear on 1.4.x].
+       * lib/m4sugar/m4sugar.m4 (m4_init): Dynamically load new file if
+       older M4 is assumed.
+       (m4_map_sep): Optimize.
+       (m4_max, m4_min): Refactor, by adding...
+       (_m4_max, _m4_min, _m4_minmax): ...more efficient helpers.
+       (m4_defn, m4_popdef, m4_undefine): Use foreach recursion.
+       * lib/m4sugar/Makefile.am (dist_m4sugarlib_DATA): Distribute new
+       file.
+       * tests/m4sugar.at (M4 loops): Add a stress test that takes
+       forever if m4_foreach and friends are quadratic.
+       * NEWS: Mention this.
+
 2008-07-21  Eric Blake  <address@hidden>
 
        Ignore undefined macros, necessary with m4 1.6.
diff --git a/NEWS b/NEWS
index 232ec86..83f43a4 100644
--- a/NEWS
+++ b/NEWS
@@ -26,6 +26,13 @@ GNU Autoconf NEWS - User visible changes.
    case with underlying m4:
    m4_defn  m4_popdef  m4_undefine
 
+** The following m4sugar macros now guarantee linear scaling; they
+   previously had linear scaling with m4 1.6 but quadratic scaling
+   when using m4 1.4.x.  All macros built on top of these also gain
+   the scaling improvements.
+   m4_case  m4_do  m4_dquote_elt  m4_foreach  m4_join  m4_list_cmp
+   m4_map  m4_map_sep  m4_max  m4_min  m4_shiftn
+
 ** AT_KEYWORDS once again performs expansion on its argument, such that
    AT_KEYWORDS([m4_if([$1], [], [default])]) no longer complains about
    the possibly unexpanded m4_if [regression introduced in 2.62].
diff --git a/lib/m4sugar/Makefile.am b/lib/m4sugar/Makefile.am
index 39da620..98654a0 100644
--- a/lib/m4sugar/Makefile.am
+++ b/lib/m4sugar/Makefile.am
@@ -1,6 +1,6 @@
 # Make Autoconf library for M4sugar.
 
-# Copyright (C) 2001, 2002, 2006, 2007 Free Software Foundation, Inc.
+# Copyright (C) 2001, 2002, 2006, 2007, 2008 Free Software Foundation, Inc.
 
 # This program is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -16,7 +16,7 @@
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
 m4sugarlibdir = $(pkgdatadir)/m4sugar
-dist_m4sugarlib_DATA = m4sugar.m4 m4sh.m4
+dist_m4sugarlib_DATA = m4sugar.m4 foreach.m4 m4sh.m4
 nodist_m4sugarlib_DATA = version.m4 m4sugar.m4f m4sh.m4f
 CLEANFILES = $(nodist_m4sugarlib_DATA)
 
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
new file mode 100644
index 0000000..935dbff
--- /dev/null
+++ b/lib/m4sugar/foreach.m4
@@ -0,0 +1,236 @@
+#                                                  -*- Autoconf -*-
+# This file is part of Autoconf.
+# foreach-based replacements for recursive functions.
+# Speeds up GNU M4 1.4.x by avoiding quadratic $@ recursion, but penalizes
+# GNU M4 1.6 by requiring more memory and macro expansions.
+#
+# Copyright (C) 2008 Free Software Foundation, Inc.
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2, or (at your option)
+# any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.
+#
+# As a special exception, the Free Software Foundation gives unlimited
+# permission to copy, distribute and modify the configure scripts that
+# are the output of Autoconf.  You need not follow the terms of the GNU
+# General Public License when using or distributing such scripts, even
+# though portions of the text of Autoconf appear in them.  The GNU
+# General Public License (GPL) does govern all other use of the material
+# that constitutes the Autoconf program.
+#
+# Certain portions of the Autoconf source text are designed to be copied
+# (in certain cases, depending on the input) into the output of
+# Autoconf.  We call these the "data" portions.  The rest of the Autoconf
+# source text consists of comments plus executable code that decides which
+# of the data portions to output in any given case.  We call these
+# comments and executable code the "non-data" portions.  Autoconf never
+# copies any of the non-data portions into its output.
+#
+# This special exception to the GPL applies to versions of Autoconf
+# released by the Free Software Foundation.  When you make and
+# distribute a modified version of Autoconf, you may extend this special
+# exception to the GPL to apply to your modified version as well, *unless*
+# your modified version has the potential to copy into its output some
+# of the text that was the non-data portion of the version that you started
+# with.  (In other words, unless your change moves or copies text from
+# the non-data portions to the data portions.)  If your modification has
+# such potential, you must delete any notice of this special exception
+# to the GPL from your modified version.
+#
+# Written by Eric Blake.
+#
+
+# In M4 1.4.x, every byte of $@ is rescanned.  This means that an
+# algorithm on n arguments that recurses with one less argument each
+# iteration will scan n * (n + 1) / 2 arguments, for O(n^2) time.  In
+# M4 1.6, this was fixed so that $@ is only scanned once, then
+# back-references are made to information stored about the scan.
+# Thus, n iterations need only scan n arguments, for O(n) time.
+# Additionally, in M4 1.4.x, recursive algorithms did not clean up
+# memory very well, requiring O(n^2) memory rather than O(n) for n
+# iterations.
+#
+# This file is designed to overcome the quadratic nature of $@
+# recursion by writing a variant of m4_foreach that uses m4_for rather
+# than $@ recursion to operate on the list.  This involves more macro
+# expansions, but avoids the need to rescan a quadratic number of
+# arguments, making these replacements very attractive for M4 1.4.x.
+# On the other hand, in any version of M4, expanding additional macros
+# costs additional time; therefore, in M4 1.6, where $@ recursion uses
+# fewer macros, these replacements actually pessimize performance.
+# Additionally, the use of $10 to mean the tenth argument violates
+# POSIX; although all versions of m4 1.4.x support this meaning, a
+# future m4 version may switch to take it as the first argument
+# concatenated with a literal 0, so the implementations in this file
+# are not future-proof.  Thus, this file is conditionally included as
+# part of m4_init(), only when it is detected that M4 probably has
+# quadratic behavior (ie. it lacks the macro __m4_version__).
+
+# m4_foreach(VARIABLE, LIST, EXPRESSION)
+# --------------------------------------
+# Expand EXPRESSION assigning each value of the LIST to VARIABLE.
+# LIST should have the form `item_1, item_2, ..., item_n', i.e. the
+# whole list must *quoted*.  Quote members too if you don't want them
+# to be expanded.
+#
+# This version minimizes the number of times that $@ is evaluated by
+# using m4_for to generate a boilerplate into VARIABLE then passing $@
+# to that temporary macro.  Thus, the recursion is done in m4_for
+# without reparsing any user input, and is not quadratic.  For an idea
+# of how this works, note that m4_foreach(i,[1,2],[i]) defines i to be
+#   m4_define([$1],[$3])$2[]m4_define([$1],[$4])$2[]m4_popdef([i])
+# then calls i([i],[i],[1],[2]).
+m4_define([m4_foreach],
+[m4_if([$2], [], [], [_$0([$1], [$3], $2)])])
+
+m4_define([_m4_foreach],
+[m4_define([$1], m4_pushdef([$1], [3])_m4_for([$1], [$#], [1],
+    [$0_([1], [2], m4_indir([$1]))])[m4_popdef([$1])])m4_indir([$1], $@)])
+
+m4_define([_m4_foreach_],
+[[m4_define([$$1], [$$3])$$2[]]])
+
+# m4_case(SWITCH, VAL1, IF-VAL1, VAL2, IF-VAL2, ..., DEFAULT)
+# -----------------------------------------------------------
+# Find the first VAL that SWITCH matches, and expand the corresponding
+# IF-VAL.  If there are no matches, expand DEFAULT.
+#
+# Use m4_for to create a temporary macro in terms of a boilerplate
+# m4_if with final cleanup.  If $# is even, we have DEFAULT; if it is
+# odd, then rounding the last $# up in the temporary macro is
+# harmless.  For example, both m4_case(1,2,3,4,5) and
+# m4_case(1,2,3,4,5,6) result in the intermediate _m4_case being
+#   m4_if([$1],[$2],[$3],[$1],[$4],[$5],_m4_popdef([_m4_case])[$6])
+m4_define([m4_case],
+[m4_if(m4_eval([$# <= 2]), [1], [$2],
+[m4_pushdef([_$0], [m4_if(]m4_for([_m4_count], [2], m4_decr([$#]), [2],
+     [_$0_([1], _m4_count, m4_incr(_m4_count))])[_m4_popdef(
+        [_$0])]m4_dquote($m4_eval([($# + 1) & ~1]))[)])_$0($@)])])
+
+m4_define([_m4_case_],
+[[[$$1],[$$2],[$$3],]])
+
+# m4_shiftn(N, ...)
+# -----------------
+# Returns ... shifted N times.  Useful for recursive "varargs" constructs.
+#
+# m4_shiftn already validated arguments; we only need to speed up
+# _m4_shiftn.  If N is 3, then we build the temporary _m4_s, defined as
+#   ,[$5],[$6],...,[$m]_m4_popdef([_m4_s])
+# before calling m4_shift(_m4_s($@)).
+m4_define([_m4_shiftn],
+[m4_define([_m4_s], m4_pushdef([_m4_s],
+                       m4_incr(m4_incr([$1])))_m4_for([_m4_s], [$#], [1],
+    [[,]m4_dquote([$]_m4_s)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])
+
+# m4_do(STRING, ...)
+# ------------------
+# This macro invokes all its arguments (in sequence, of course).  It is
+# useful for making your macros more structured and readable by dropping
+# unnecessary dnl's and have the macros indented properly.
+#
+# Here, we use the temporary macro _m4_do, defined as
+#   $1$2...$n[]_m4_popdef([_m4_do])
+m4_define([m4_do],
+[m4_define([_$0], m4_pushdef([_$0], [1])_m4_for([_$0], [$#], [1],
+    [$][_$0])[[]_m4_popdef([_$0])])_$0($@)])
+
+# m4_dquote_elt(ARGS)
+# -------------------
+# Return ARGS as an unquoted list of double-quoted arguments.
+#
+# m4_foreach to the rescue.  It's easier to shift off the leading comma.
+m4_define([m4_dquote_elt],
+[m4_shift(m4_foreach([_m4_elt], address@hidden, 
[,m4_dquote(_m4_defn([_m4_elt]))]))])
+
+# m4_map(MACRO, LIST)
+# -------------------
+# Invoke MACRO($1), MACRO($2) etc. where $1, $2... are the elements
+# of LIST.  $1, $2... must in turn be lists, appropriate for m4_apply.
+#
+# m4_map/m4_map_sep only execute once; the speedup comes in fixing
+# _m4_map.  m4_foreach to the rescue.
+m4_define([_m4_map],
+[m4_if([$#], [1], [],
+       [m4_foreach([_m4_elt], [m4_shift($@)],
+                  [m4_apply([$1], m4_defn([_m4_elt]))])])])
+
+# m4_join(SEP, ARG1, ARG2...)
+# ---------------------------
+# Produce ARG1SEPARG2...SEPARGn.  Avoid back-to-back SEP when a given ARG
+# is the empty string.  No expansion is performed on SEP or ARGs.
+#
+# Use a self-modifying separator, since we don't know how many
+# arguments might be skipped before a separator is first printed, but
+# be careful if the separator contains $.  m4_foreach to the rescue.
+m4_define([m4_join],
+[m4_pushdef([_m4_sep], [m4_define([_m4_sep], _m4_defn([m4_echo]))])]dnl
+[m4_foreach([_m4_arg], [m4_shift($@)],
+           [m4_ifset([_m4_arg], [_m4_sep([$1])_m4_defn([_m4_arg])])])]dnl
+[_m4_popdef([_m4_sep])])
+
+# m4_joinall(SEP, ARG1, ARG2...)
+# ------------------------------
+# Produce ARG1SEPARG2...SEPARGn.  An empty ARG results in back-to-back SEP.
+# No expansion is performed on SEP or ARGs.
+#
+# A bit easier than m4_join.  m4_foreach to the rescue.
+m4_define([m4_joinall],
+[[$2]m4_if([$#], [1], [], [$#], [2], [],
+          [m4_foreach([_m4_arg], [m4_shift2($@)],
+                      [[$1]_m4_defn([_m4_arg])])])])
+
+# m4_list_cmp(A, B)
+# -----------------
+# Compare the two lists of integer expressions A and B.
+#
+# First, insert padding so that both lists are the same length; the
+# trailing +0 is necessary to handle a missing list.  Next, create a
+# temporary macro to perform pairwise comparisons until an inequality
+# is found.  For example, m4_list_cmp([1], [1,2]) creates _m4_cmp as
+#   m4_if([($1) != ($3)], [1], [m4_cmp([$1], [$3])],
+#         [($2) != ($4)], [1], [m4_cmp([$2], [$4])],
+#         [0]_m4_popdef([_m4_cmp], [_m4_size]))
+# then calls _m4_cmp([1+0], [0], [1], [2+0])
+m4_define([m4_list_cmp],
+[m4_if([$1], [$2], 0,
+       [_$0($1+0_m4_list_pad(m4_count($1), m4_count($2)),
+           $2+0_m4_list_pad(m4_count($2), m4_count($1)))])])
+
+m4_define([_m4_list_pad],
+[m4_if(m4_eval($1 < $2), [1], [m4_for([], [$1 + 1], [$2], [], [,0])])])
+
+m4_define([_m4_list_cmp],
+[m4_pushdef([_m4_size], m4_eval([$# >> 1]))]dnl
+[m4_define([_m4_cmp], m4_pushdef([_m4_cmp], [1])[m4_if(]_m4_for([_m4_cmp],
+   _m4_size, [1], [$0_(_m4_cmp, m4_eval(_m4_cmp + _m4_size))])[
+      [0]_m4_popdef([_m4_cmp], [_m4_size]))])_m4_cmp($@)])
+
+m4_define([_m4_list_cmp_],
+[[m4_eval([($$1) != ($$2)]), [1], [m4_cmp([$$1], [$$2])],
+]])
+
+# m4_max(EXPR, ...)
+# m4_min(EXPR, ...)
+# -----------------
+# Return the decimal value of the maximum (or minimum) in a series of
+# integer expressions.
+#
+# m4_foreach to the rescue; we only need to replace _m4_minmax.  Here,
+# we need a temporary macro to track the best answer so far, so that
+# the foreach expression is tractable.
+m4_define([_m4_minmax],
+[m4_pushdef([_m4_best], m4_eval([$2]))m4_foreach([_m4_arg], [m4_shift2($@)],
+    [m4_define([_m4_best], $1(_m4_best, _m4_defn([_m4_arg])))])]dnl
+[_m4_best[]_m4_popdef([_m4_best])])
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 5ef7836..1480953 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -523,9 +523,10 @@ m4_define([m4_default],
 m4_copy([m4_defn], [_m4_defn])
 m4_ifdef([__m4_version__], [],
 [m4_define([m4_defn],
-[m4_ifdef([$1], [],
-         [m4_fatal([$0: undefined macro: $1])])]dnl
-[_m4_defn([$1])m4_if([$#], [1], [], [$0(m4_shift($@))])])])
+[m4_if([$#], [0], [[$0]],
+       [$#], [1], [m4_ifdef([$1], [_m4_defn([$1])],
+                           [m4_fatal([$0: undefined macro: $1])])],
+       [m4_foreach([_m4_macro], address@hidden, 
[$0(_m4_defn([_m4_macro]))])])])])
 
 
 # _m4_dumpdefs_up(NAME)
@@ -571,9 +572,10 @@ _m4_dumpdefs_down([$1])])
 m4_copy([m4_popdef], [_m4_popdef])
 m4_ifdef([__m4_version__], [],
 [m4_define([m4_popdef],
-[m4_ifdef([$1], [],
-         [m4_fatal([$0: undefined macro: $1])])]dnl
-[_m4_popdef([$1])m4_if([$#], [1], [], [$0(m4_shift($@))])])])
+[m4_if([$#], [0], [[$0]],
+       [$#], [1], [m4_ifdef([$1], [_m4_popdef([$1])],
+                           [m4_fatal([$0: undefined macro: $1])])],
+       [m4_foreach([_m4_macro], address@hidden, 
[$0(_m4_defn([_m4_macro]))])])])])
 
 
 # m4_shiftn(N, ...)
@@ -635,9 +637,10 @@ m4_define([_m4_shift3],
 m4_copy([m4_undefine], [_m4_undefine])
 m4_ifdef([__m4_version__], [],
 [m4_define([m4_undefine],
-[m4_ifdef([$1], [],
-         [m4_fatal([$0: undefined macro: $1])])]dnl
-[_m4_undefine([$1])m4_if([$#], [1], [], [$0(m4_shift($@))])])])
+[m4_if([$#], [0], [[$0]],
+       [$#], [1], [m4_ifdef([$1], [_m4_undefine([$1])],
+                           [m4_fatal([$0: undefined macro: $1])])],
+       [m4_foreach([_m4_macro], address@hidden, 
[$0(_m4_defn([_m4_macro]))])])])])
 
 # _m4_wrap(PRE, POST)
 # -------------------
@@ -926,7 +929,9 @@ m4_if(m4_defn([$1]), [$2], [],
 # Hence the design below.
 #
 # The M4 manual now includes a chapter devoted to this issue, with
-# the lessons learned from m4sugar.
+# the lessons learned from m4sugar.  And still, this design is only
+# optimal for M4 1.6; see foreach.m4 for yet more comments on why
+# M4 1.4.x uses yet another implementation.
 
 
 # m4_foreach(VARIABLE, LIST, EXPRESSION)
@@ -1001,7 +1006,7 @@ m4_define([_m4_map],
 # SEPARATOR is not further expanded.
 m4_define([m4_map_sep],
 [m4_if([$3], [], [],
-       [m4_apply([$1], m4_car($3))m4_map([[$2]$1]_m4_cdr($3))])])
+       [m4_apply([$1], m4_car($3))_m4_map([[$2]$1]_m4_shift2(,$3))])])
 
 
 ## --------------------------- ##
@@ -2167,16 +2172,29 @@ m4_define([m4_max],
 [m4_if([$#], [0], [m4_fatal([too few arguments to $0])],
        [$#], [1], [m4_eval([$1])],
        [$#$1], [2$2], [m4_eval([$1])],
-       [$#], [2],
-       [m4_eval((([$1]) > ([$2])) * ([$1]) + (([$1]) <= ([$2])) * ([$2]))],
-       [$0($0([$1], [$2]), m4_shift2($@))])])
+       [$#], [2], [_$0($@)],
+       [_m4_minmax([_$0], $@)])])
+
+m4_define([_m4_max],
+[m4_eval((([$1]) > ([$2])) * ([$1]) + (([$1]) <= ([$2])) * ([$2]))])
+
 m4_define([m4_min],
 [m4_if([$#], [0], [m4_fatal([too few arguments to $0])],
        [$#], [1], [m4_eval([$1])],
        [$#$1], [2$2], [m4_eval([$1])],
-       [$#], [2],
-       [m4_eval((([$1]) < ([$2])) * ([$1]) + (([$1]) >= ([$2])) * ([$2]))],
-       [$0($0([$1], [$2]), m4_shift2($@))])])
+       [$#], [2], [_$0($@)],
+       [_m4_minmax([_$0], $@)])])
+
+m4_define([_m4_min],
+[m4_eval((([$1]) < ([$2])) * ([$1]) + (([$1]) >= ([$2])) * ([$2]))])
+
+# _m4_minmax(METHOD, ARG1, ARG2...)
+# ---------------------------------
+# Common recursion code for m4_max and m4_min.  METHOD must be _m4_max
+# or _m4_min, and there must be at least two arguments to combine.
+m4_define([_m4_minmax],
+[m4_if([$#], [3], [$1([$2], [$3])],
+       [$0([$1], $1([$2], [$3]), m4_shift3($@))])])
 
 
 # m4_sign(A)
@@ -2293,6 +2311,13 @@ m4_define([m4_init],
 m4_pattern_forbid([^_?m4_])
 m4_pattern_forbid([^dnl$])
 
+# If __m4_version__ is defined, we assume that we are being run by M4
+# 1.6 or newer, and thus that $@ recursion is linear; nothing further
+# needs to be done.  But if it is missing, we assume we are being run
+# by M4 1.4.x, that $@ recursion is quadratic, and that we need
+# foreach-based replacement macros.
+m4_ifndef([__m4_version__], [m4_include([m4sugar/foreach.m4])])
+
 # _m4_divert_diversion should be defined:
 m4_divert_push([KILL])
 
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 9dd953a..f34f50c 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -429,6 +429,8 @@ AT_CLEANUP
 
 AT_SETUP([m4@&address@hidden)
 
+AT_KEYWORDS([m4@&address@hidden)
+
 AT_CHECK_M4SUGAR_TEXT(
 [[m4_version_compare([1.1], [2.0])
 m4_version_compare([2.0b], [2.0a])
@@ -607,6 +609,7 @@ AT_CHECK_M4SUGAR([], 1, [],
 script.4s:3: the top level
 autom4te: m4 failed with exit status: 1
 ]])
+
 AT_CLEANUP
 
 
@@ -745,3 +748,84 @@ m4_max(m4_for([i], 100, 2, , [i,])1)
 ]], [])
 
 AT_CLEANUP
+
+
+## ----------- ##
+## Recursion.  ##
+## ----------- ##
+
+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)
+
+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,
+dnl only the slower foreach.m4 implementation will work.  But if we
+dnl are testing with m4 1.6, we can rerun the test with __m4_version__
+dnl undefined to exercise the alternate code path.
+AT_DATA_M4SUGAR([script.4s],
+[[m4_init
+m4_divert_push(0)[]dnl
+m4_len(m4_foreach_w([j], m4_do(m4_for([i], [1], [10000], [], [,i ])), [j ]))
+m4_shiftn(9998m4_for([i], [1], [10000], [], [,i]))
+m4_len(m4_join([--],, m4_dquote_elt(m4_for([i], [1], [10000], [], [,i])),))
+m4_len(m4_joinall([--], m4_map([, m4_echo],
+  m4_dquote([1]m4_for([i], [2], [10000], [], [,i])))))
+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_for([i], [1], [10000], [], [m4_define(i)])dnl
+m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
+m4_divert_pop(0)
+]])
+
+AT_CHECK_M4SUGAR([-o-], [0], [[48894
+9999,10000
+78896
+58894
+10000
+end
+0
+]])
+
+AT_DATA_M4SUGAR([script.4s],
+[[m4_ifdef([__m4_version__],
+[m4_undefine([__m4_version__])],
+[m4_divert_push(0)48894
+9999,10000
+78896
+58894
+10000
+end
+0
+m4_exit([0])])
+m4_init
+m4_divert_push(0)[]dnl
+m4_len(m4_foreach_w([j], m4_do(m4_for([i], [1], [10000], [], [,i ])), [j ]))
+m4_shiftn(9998m4_for([i], [1], [10000], [], [,i]))
+m4_len(m4_join([--],, m4_dquote_elt(m4_for([i], [1], [10000], [], [,i])),))
+m4_len(m4_joinall([--], m4_map([, m4_echo],
+  m4_dquote([1]m4_for([i], [2], [10000], [], [,i])))))
+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_for([i], [1], [10000], [], [m4_define(i)])dnl
+m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
+m4_divert_pop(0)
+]])
+
+AT_CHECK_M4SUGAR([-o-], [0], [[48894
+9999,10000
+78896
+58894
+10000
+end
+0
+]])
+
+AT_CLEANUP
-- 
1.5.6.3