more m4sugar tweaks

[Eric Blake]

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

Three patches, stemming from inspection of my recent O(n) additions.

1. m4_for was inefficient; and now that m4 1.4.x makes a much heavier
reliance on it, I decided to improve its speed.  One of the ways I made it
faster was via a subtle semantic change; previously, each iteration used
m4_indir([variable]) to read the current counter, and see if iteration
should end.  This meant the user could modify the definition of variable
to skip or replay iterations, potentially even entering an infinite loop.
~  The new implementation ignores user changes to variable, always
performing as many iterations as was determined up front.  In my quick
survey of m4_for clients across several projects, I did not find any code
that was intentionally changing the value of variable during an iteration,
and since the behavior was previously undocumented and untested, I doubt
anyone will be affected by the change.  The patch documents and tests the
new behavior.

2. m4_do was inconsistent.  In the m4 1.6 version, it did $1[]$2, so that
the final expansion was concatenated with text after the m4_do.  In the
1.4.x version, it did $1$2[], so that intermediate expansions were
concatenated, and m4_do without arguments went into a loop.  Both
implementations now behave as $1[]$2[], so that no concatenation of
expansions occur; this is a subtle semantic change, but again, something
that was previously undocumented, untested, and not present in my survey
of clients.

3. m4_bpatsubsts didn't match the documentation if given exactly two
arguments, and was quadratic for m4 1.4.x.  I finally figured out how to
make it linear (leaving just m4_cond and m4_bmatch to go).

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

iEYEARECAAYFAkiQa1UACgkQ84KuGfSFAYBMLQCfWNMtjBw1tBLBiI6j4MG+YYmD
k7EAn3gaYqQ8Wm1WuO0Q99K/UFVEPark
=JzmW
-----END PGP SIGNATURE-----

>From 8f5c14ff9143fb53a395f1a5fad9429a4feac26e Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 12:21:25 -0600
Subject: [PATCH] Optimize m4_for.

* lib/m4sugar/m4sugar.m4 (m4_for): Use fewer macros.
(_m4_for): Take additional parameter, for fewer m4_indir calls.
* lib/m4sugar/foreach.m4 (_m4_foreach, _m4_shiftn, m4_do)
(m4_reverse, _m4_list_pad, _m4_list_cmp): Adjust all callers.
* doc/autoconf.texi (Looping constructs) <m4_for>: Document subtle
semantic change caused by the optimization.
* tests/m4sugar.at (M4 loops): Test the new semantics.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    9 +++++++
 doc/autoconf.texi      |    4 ++-
 lib/m4sugar/foreach.m4 |   31 +++++++++++++------------
 lib/m4sugar/m4sugar.m4 |   57 +++++++++++++++++++++++------------------------
 tests/m4sugar.at       |    3 ++
 5 files changed, 59 insertions(+), 45 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 877eb28..fe6d7b7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
 2008-07-29  Eric Blake  <address@hidden>
 
+       Optimize m4_for.
+       * lib/m4sugar/m4sugar.m4 (m4_for): Use fewer macros.
+       (_m4_for): Take additional parameter, for fewer m4_indir calls.
+       * lib/m4sugar/foreach.m4 (_m4_foreach, _m4_shiftn, m4_do)
+       (m4_reverse, _m4_list_pad, _m4_list_cmp): Adjust all callers.
+       * doc/autoconf.texi (Looping constructs) <m4_for>: Document subtle
+       semantic change caused by the optimization.
+       * tests/m4sugar.at (M4 loops): Test the new semantics.
+
        One more m4_list_cmp tweak.
        * lib/m4sugar/m4sugar.m4 (_m4_list_cmp_1): Don't defer shift.
        * lib/m4sugar/foreach.m4 (m4_list_cmp): Fix comment.
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index b3b416c..7dc4405 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -10779,7 +10779,9 @@ including bounds by increments of @var{step}.  For each 
iteration,
 expand @var{expression} with the numeric value assigned to @var{var}.
 If @var{step} is omitted, it defaults to @samp{1} or @samp{-1} depending
 on the order of the limits.  If given, @var{step} has to match this
-order.
+order.  The number of iterations is determined independently from
+definition of @var{var}; iteration cannot be short-circuited or
+lengthened by modifying @var{var} from within @var{expression}.
 @end defmac
 
 @defmac m4_foreach (@var{var}, @var{list}, @var{expression})
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 1b5d2f9..bedb4f5 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -95,8 +95,8 @@ 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([$1], m4_pushdef([$1])_m4_for([$1], [3], [$#], [1],
+    [$0_([1], [2], _m4_defn([$1]))])[m4_popdef([$1])])m4_indir([$1], $@)])
 
 m4_define([_m4_foreach_],
 [[m4_define([$$1], [$$3])$$2[]]])
@@ -130,9 +130,9 @@ m4_define([_m4_case_],
 #   ,[$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_define([_m4_s],
+          m4_pushdef([_m4_s])_m4_for([_m4_s], m4_eval([$1 + 2]), [$#], [1],
+  [[,]m4_dquote([$]_m4_s)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])
 
 # m4_do(STRING, ...)
 # ------------------
@@ -143,8 +143,8 @@ m4_define([_m4_shiftn],
 # 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_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [1], [$#], [1],
+    [$_$0])[[]_m4_popdef([_$0])])_$0($@)])
 
 # m4_dquote_elt(ARGS)
 # -------------------
@@ -162,8 +162,8 @@ m4_define([m4_dquote_elt],
 #   [$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_define([_m4_r], m4_dquote([$$#])m4_pushdef([_m4_r])_m4_for([_m4_r],
+      m4_decr([$#]), [1], [-1],
     [[, ]m4_dquote([$]_m4_r)])[_m4_popdef([_m4_r])])_m4_r($@)])])
 
 
@@ -218,16 +218,17 @@ m4_define([m4_joinall],
 # 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_pushdef([_m4_size])_$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_if(m4_eval($1 < $2), [1],
+       [_m4_for([_m4_size], m4_incr([$1]), [$2], [1], [,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))])[
+[m4_define([_m4_size], m4_eval([$# >> 1]))]dnl
+[m4_define([_m4_cmp], m4_pushdef([_m4_cmp])[m4_if(]_m4_for([_m4_cmp],
+   [1], _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_],
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index a605947..11692af 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -827,37 +827,36 @@ m4_define([m4_unquote], [$*])
 # m4_for(VARIABLE, FIRST, LAST, [STEP = +/-1], EXPRESSION)
 # --------------------------------------------------------
 # Expand EXPRESSION defining VARIABLE to FROM, FROM + 1, ..., TO with
-# increments of STEP.
-# Both limits are included, and bounds are checked for consistency.
-# The algorithm is robust to indirect VARIABLE names, and uses _m4_defn
-# where possible for speed.
+# increments of STEP.  Both limits are included, and bounds are
+# checked for consistency.  The algorithm is robust to indirect
+# VARIABLE names.  Changing VARIABLE inside EXPRESSION will not impact
+# the number of iterations.
+#
+# Uses _m4_defn for speed, and avoid dnl in the macro body.
 m4_define([m4_for],
-[m4_pushdef([$1], m4_eval([$2]))dnl
-m4_cond([m4_eval(([$3]) > _m4_defn([$1]))], 1,
-[m4_pushdef([_m4_step], m4_eval(m4_default([$4], 1)))dnl
-m4_assert(_m4_step > 0)dnl
-_m4_for([$1], m4_eval((([$3]) - _m4_defn([$1]))
-                     / _m4_step * _m4_step + _m4_defn([$1])),
-       _m4_step, [$5])],
-       [m4_eval(([$3]) < _m4_defn([$1]))], 1,
-[m4_pushdef([_m4_step], m4_eval(m4_default([$4], -1)))dnl
-m4_assert(_m4_step < 0)dnl
-_m4_for([$1], m4_eval((_m4_defn([$1]) - ([$3]))
-                     / -(_m4_step) * _m4_step + _m4_defn([$1])),
-       _m4_step, [$5])],
-       [m4_pushdef([_m4_step])dnl
-$5])[]dnl
-m4_popdef([_m4_step])dnl
-m4_popdef([$1])])
-
-
-# _m4_for(VARIABLE, LAST, STEP, EXPRESSION)
-# -----------------------------------------
-# Core of the loop, no consistency checks, all arguments are plain numbers.
+[m4_pushdef([$1], m4_eval([$2]))]dnl
+[m4_cond([m4_eval(([$3]) > ([$2]))], 1,
+          [m4_pushdef([_m4_step], m4_eval(m4_default([$4],
+             1)))m4_assert(_m4_step > 0)_$0([$1], _m4_defn([$1]),
+  m4_eval((([$3]) - ([$2])) / _m4_step * _m4_step + ([$2])),
+  _m4_step, [$5])],
+        [m4_eval(([$3]) < ([$2]))], 1,
+          [m4_pushdef([_m4_step], m4_eval(m4_default([$4],
+             -1)))m4_assert(_m4_step < 0)_$0([$1], _m4_defn([$1]),
+  m4_eval((([$2]) - ([$3])) / -(_m4_step) * _m4_step + ([$2])),
+  _m4_step, [$5])],
+        [m4_pushdef([_m4_step])$5])[]]dnl
+[m4_popdef([_m4_step], [$1])])
+
+
+# _m4_for(VARIABLE, COUNT, LAST, STEP, EXPRESSION)
+# ------------------------------------------------
+# Core of the loop, no consistency checks, all arguments are plain
+# numbers.  Define VARIABLE to COUNT, expand EXPRESSION, then alter
+# COUNT by STEP and iterate if COUNT is not LAST.
 m4_define([_m4_for],
-[$4[]dnl
-m4_if(m4_defn([$1]), [$2], [],
-      [m4_define([$1], m4_eval(m4_defn([$1])+[$3]))$0($@)])])
+[m4_define([$1], [$2])$5[]m4_if([$2], [$3], [],
+      [$0([$1], m4_eval([$2 + $4]), [$3], [$4], [$5])])])
 
 
 # Implementing `foreach' loops in m4 is much more tricky than it may
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 2b73188..92945a4 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -532,6 +532,8 @@ m4_for([myvar], -2+8, 3-5, , [ myvar])
 m4_for([myvar], 8, 16, 3 * 2, [ myvar])
 m4_for([myvar], 8, 16, -3 * -2, [ myvar])
 m4_for([myvar], [2<<2], [2<<3], [-3 * (-2)], [ myvar])
+dnl Modifying var does not affect the number of iterations
+m4_for([myvar], 1, 5, , [ myvar[]m4_define([myvar], 5)])
 dnl Make sure we can do nameless iteration
 m4_for(, 1, 10, , -)
 dnl foreach tests
@@ -567,6 +569,7 @@ myvar
  8 14
  8 14
  8 14
+ 1 2 3 4 5
 ----------
  a| b, c| d| e
 | f|
-- 
1.5.6.4


>From a40eef5129fccd8238dfd130d5a0ad9baf296127 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 14:17:03 -0600
Subject: [PATCH] Tweak m4_do semantics.

* lib/m4sugar/m4sugar.m4 (m4_do): Don't concat final argument with
subsequent text.
* lib/m4sugar/foreach.m4 (m4_do): Don't concat intermediate
arguments, and avoid infinite loop.
* doc/autoconf.texi (Evaluation Macros) <m4_do>: Document the
behavior.
* tests/m4sugar.at (m4@&address@hidden): New test.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    9 +++++++++
 doc/autoconf.texi      |   19 ++++++++++++++++++-
 lib/m4sugar/foreach.m4 |    9 +++++----
 lib/m4sugar/m4sugar.m4 |    9 ++++++---
 tests/m4sugar.at       |   28 ++++++++++++++++++++++++++++
 5 files changed, 66 insertions(+), 8 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index fe6d7b7..93c8f78 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
 2008-07-29  Eric Blake  <address@hidden>
 
+       Tweak m4_do semantics.
+       * lib/m4sugar/m4sugar.m4 (m4_do): Don't concat final argument with
+       subsequent text.
+       * lib/m4sugar/foreach.m4 (m4_do): Don't concat intermediate
+       arguments, and avoid infinite loop.
+       * doc/autoconf.texi (Evaluation Macros) <m4_do>: Document the
+       behavior.
+       * tests/m4sugar.at (m4@&address@hidden): New test.
+
        Optimize m4_for.
        * lib/m4sugar/m4sugar.m4 (m4_for): Use fewer macros.
        (_m4_for): Take additional parameter, for fewer m4_indir calls.
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index 7dc4405..d27aeb2 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -10882,7 +10882,24 @@ passed.
 @msindex{do}
 This macro loops over its arguments and expands each @var{arg} in
 sequence.  Its main use is for readability; it allows the use of
-indentation and fewer @code{dnl} to result in the same expansion.
+indentation and fewer @code{dnl} to result in the same expansion.  This
+macro guarantees that no expansion will be concatenated with subsequent
+text; to achieve full concatenation, use @code{m4_unquote(m4_join([],
address@hidden@dots{}}))}.
+
address@hidden
+m4_define([ab],[1])m4_define([bc],[2])m4_define([abc],[3])dnl
+m4_do([a],[b])c
address@hidden
+m4_unquote(m4_join([],[a],[b]))c
address@hidden
+m4_define([a],[A])m4_define([b],[B])m4_define([c],[C])dnl
+m4_define([AB],[4])m4_define([BC],[5])m4_define([ABC],[6])dnl
+m4_do([a],[b])c
address@hidden
+m4_unquote(m4_join([],[a],[b]))c
address@hidden
address@hidden example
 @end defmac
 
 @defmac m4_dquote (@var{arg}, @dots{})
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index bedb4f5..3997ff2 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -141,10 +141,11 @@ m4_define([_m4_shiftn],
 # 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])
+#   $1[]$2[]...[]$n[]_m4_popdef([_m4_do])
 m4_define([m4_do],
-[m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [1], [$#], [1],
-    [$_$0])[[]_m4_popdef([_$0])])_$0($@)])
+[m4_if([$#], [0], [],
+       [m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [1], [$#], [1],
+                 [$_$0[[]]])[_m4_popdef([_$0])])_$0($@)])])
 
 # m4_dquote_elt(ARGS)
 # -------------------
@@ -200,7 +201,7 @@ m4_define([m4_join],
 #
 # A bit easier than m4_join.  m4_foreach to the rescue.
 m4_define([m4_joinall],
-[[$2]m4_if([$#], [1], [], [$#], [2], [],
+[[$2]m4_if(m4_eval([$# <= 2]), [1], [],
           [m4_foreach([_m4_arg], [m4_shift2($@)],
                       [[$1]_m4_defn([_m4_arg])])])])
 
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 11692af..b67b1ad 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -692,11 +692,12 @@ m4_define([m4_count], [$#])
 # ------------------
 # 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.
+# unnecessary dnl's and have the macros indented properly.  No concatenation
+# occurs after a STRING; use m4_unquote(m4_join(,STRING)) for that.
 m4_define([m4_do],
 [m4_if([$#], 0, [],
-       [$#], 1, [$1],
-       [$1[]m4_do(m4_shift($@))])])
+       [$#], 1, [$1[]],
+       [$1[]$0(m4_shift($@))])])
 
 
 # m4_dquote(ARGS)
@@ -816,6 +817,8 @@ m4_define([m4_reverse],
 # expansion.  For one argument, m4_unquote([arg]) is more efficient than
 # m4_do([arg]), but for multiple arguments, the difference is that
 # m4_unquote separates arguments with commas while m4_do concatenates.
+# Follow this macro with [] if concatenation with subsequent text is
+# undesired.
 m4_define([m4_unquote], [$*])
 
 
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 92945a4..ce119e0 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -237,6 +237,34 @@ m4_split([a )}@&t@>=- b -=<@&address@hidden( c])
 AT_CLEANUP
 
 
+## ------- ##
+## m4_do.  ##
+## ------- ##
+
+AT_SETUP([m4@&address@hidden)
+
+AT_CHECK_M4SUGAR_TEXT(
+[[m4_define([ab], [1])m4_define([bc], [2])m4_define([abc], [3])dnl
+m4_define([AB], [4])m4_define([BC], [5])m4_define([ABC], [6])dnl
+m4_do
+m4_do([a])
+m4_do([a], [b])c
+m4_unquote(m4_join([], [a], [b]))c
+m4_define([a], [A])m4_define([b], [B])m4_define([c], [C])dnl
+m4_do([a], [b])c
+m4_unquote(m4_join([], [a], [b]))c
+]],
+[[
+a
+abc
+3
+ABC
+3
+]])
+
+AT_CLEANUP
+
+
 ## ----------- ##
 ## m4_append.  ##
 ## ----------- ##
-- 
1.5.6.4


>From 8d81fd7f28c1543bc4d0766dc11e18daadfe851b Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 20:34:06 -0600
Subject: [PATCH] Add linear m4_bpatsubsts for m4 1.4.x.

* lib/m4sugar/m4sugar.m4 (m4_bpatsubsts): Match documentation
about anchors, even for only one substitution.
* lib/m4sugar/foreach.m4 (_m4_bpatsubsts): New implementation.
* doc/autoconf.texi (Conditional constructs) <m4_bpatsubsts>:
Clarify behavior with regard to quoting.
* tests/m4sugar.at (recursion): Test scaling of m4_bpatsubsts.
(m4@&address@hidden): New test.
* NEWS: Document the linear guarantee.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   10 ++++++++++
 NEWS                   |    4 ++--
 doc/autoconf.texi      |    3 ++-
 lib/m4sugar/foreach.m4 |   27 +++++++++++++++++++++++++++
 lib/m4sugar/m4sugar.m4 |    3 ++-
 tests/m4sugar.at       |   35 ++++++++++++++++++++++++++++++++---
 6 files changed, 75 insertions(+), 7 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 93c8f78..5f348b3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
 2008-07-29  Eric Blake  <address@hidden>
 
+       Add linear m4_bpatsubsts for m4 1.4.x.
+       * lib/m4sugar/m4sugar.m4 (m4_bpatsubsts): Match documentation
+       about anchors, even for only one substitution.
+       * lib/m4sugar/foreach.m4 (_m4_bpatsubsts): New implementation.
+       * doc/autoconf.texi (Conditional constructs) <m4_bpatsubsts>:
+       Clarify behavior with regard to quoting.
+       * tests/m4sugar.at (recursion): Test scaling of m4_bpatsubsts.
+       (m4@&address@hidden): New test.
+       * NEWS: Document the linear guarantee.
+
        Tweak m4_do semantics.
        * lib/m4sugar/m4sugar.m4 (m4_do): Don't concat final argument with
        subsequent text.
diff --git a/NEWS b/NEWS
index 9737c34..30f0f4e 100644
--- a/NEWS
+++ b/NEWS
@@ -33,8 +33,8 @@ GNU Autoconf NEWS - User visible changes.
    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
+   m4_bpatsubsts  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
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index d27aeb2..b1b2a24 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -10635,7 +10635,8 @@ macro over-quotes @var{string}; this behavior is 
intentional, so that
 the result of each step of the recursion remains as a quoted string.
 However, it means that anchors (@samp{^} and @samp{$} in the @var{regex}
 will line up with the extra quotations, and not the characters of the
-original string.
+original string.  The overquoting is removed after the final
+substitution.
 @end defmac
 
 @defmac m4_case (@var{string}, @var{value-1}, @var{if-value-1}, @
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 3997ff2..015e0be 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -121,6 +121,33 @@ m4_define([m4_case],
 m4_define([_m4_case_],
 [[[$$1],[$$2],[$$3],]])
 
+# m4_bpatsubsts(STRING, RE1, SUBST1, RE2, SUBST2, ...)
+# ----------------------------------------------------
+# m4 equivalent of
+#
+#   $_ = STRING;
+#   s/RE1/SUBST1/g;
+#   s/RE2/SUBST2/g;
+#   ...
+#
+# m4_bpatsubsts already validated an odd number of arguments; we only
+# need to speed up _m4_bpatsubsts.  To avoid nesting, we build the
+# temporary _m4_p:
+#   m4_define([_m4_p], [$1])m4_define([_m4_p],
+#   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$2], [$3]))m4_define([_m4_p],
+#   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$4], 
[$5]))m4_define([_m4_p],...
+#   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$m-1], [$m]))m4_unquote(
+#   _m4_defn([_m4_p]))[]_m4_popdef([_m4_p])
+m4_define([_m4_bpatsubsts],
+[m4_define([_m4_p], m4_pushdef([_m4_p])[m4_define([_m4_p],
+  [$1])]_m4_for([_m4_p], [3], [$#], [2], [$0_(m4_decr(_m4_p),
+  _m4_p)])[m4_unquote(_m4_defn([_m4_p]))[]_m4_popdef([_m4_p])])_m4_p($@)])
+
+m4_define([_m4_bpatsubsts_],
+[[m4_define([_m4_p],
+m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$$1], [$$2]))]])
+
+
 # m4_shiftn(N, ...)
 # -----------------
 # Returns ... shifted N times.  Useful for recursive "varargs" constructs.
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index b67b1ad..d864f18 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -478,7 +478,8 @@ m4_define([m4_cond],
 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], [$1], [$2])],
+       [$#], 2, [m4_unquote(m4_builtin([patsubst], [[$1]], [$2]))],
+       [$#], 3, [m4_unquote(m4_builtin([patsubst], [[$1]], [$2], [$3]))],
        [_$0(address@hidden(m4_eval($# & 1), 0, [,]))])])
 m4_define([_m4_bpatsubsts],
 [m4_if([$#], 2, [$1],
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index ce119e0..a1c0bd0 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -521,6 +521,30 @@ AT_CHECK_M4RE([m4_re_string], address@hidden)
 
 AT_CLEANUP
 
+## --------------- ##
+## m4_bpatsubsts.  ##
+## --------------- ##
+
+AT_SETUP([m4@&address@hidden)
+
+AT_CHECK_M4SUGAR_TEXT(
+[[m4_bpatsubsts([11], [^..$])
+m4_bpatsubsts([11], [\(.\)1], [\12])
+m4_bpatsubsts([11], [^..$], [], [1], [2])
+m4_bpatsubsts([11], [\(.\)1], [\12], [1], [3])
+m4_define([a], [oops])m4_define([AB], [good])dnl
+m4_bpatsubsts([abc], [a], [A], [b], [B], [c])
+m4_bpatsubsts(address@hidden, [\$\*], [$#])
+]], [[11
+21
+22
+23
+good
+$1$#$@
+]])
+
+AT_CLEANUP
+
 ## ---------- ##
 ## M4 Loops.  ##
 ## ---------- ##
@@ -787,9 +811,9 @@ 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)
+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)
 
 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,
@@ -813,6 +837,7 @@ m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
 m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
+m4_bpatsubsts([a1]m4_for([i], [1], [10000], [], [,i]), [a2], [A])
 m4_divert_pop(0)
 ]])
 
@@ -825,6 +850,7 @@ end
 0
 0
 0
+A
 ]])
 
 AT_DATA_M4SUGAR([script.4s],
@@ -839,6 +865,7 @@ end
 0
 0
 0
+A
 m4_exit([0])])
 m4_init
 m4_divert_push(0)[]dnl
@@ -856,6 +883,7 @@ m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
 m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
 m4_for([i], [1], [10000], [], [m4_define(i)])dnl
 m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
+m4_bpatsubsts([a1]m4_for([i], [1], [10000], [], [,i]), [a2], [A])
 m4_divert_pop(0)
 ]])
 
@@ -868,6 +896,7 @@ end
 0
 0
 0
+A
 ]])
 
 AT_CLEANUP
-- 
1.5.6.4