[SCM] GNU Autoconf source repository branch, master, updated. v2.62-52-gdbb9fe3

[Eric Blake]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Autoconf source repository".

http://git.sv.gnu.org/gitweb/?p=autoconf.git;a=commitdiff;h=dbb9fe36bfb9cdd2d1c4b13a752ca3bb7bb049a7

The branch, master has been updated
       via  dbb9fe36bfb9cdd2d1c4b13a752ca3bb7bb049a7 (commit)
      from  2c521d7fd687410f008fac8e19d94d7521b34321 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit dbb9fe36bfb9cdd2d1c4b13a752ca3bb7bb049a7
Author: Eric Blake <address@hidden>
Date:   Fri Jul 25 15:17:38 2008 -0600

    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>

-----------------------------------------------------------------------

Summary of changes:
 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


hooks/post-receive
--
GNU Autoconf source repository