m4sugar and m4 1.6, bison

[Eric Blake]

I'm committing these two patches.  The first works around warnings caused by 
dereferencing undefined macros (available on m4's master branch for some time 
now, and recently backported to branch-1.6):

$ m4 -I lib m4sugar/m4sugar.m4
m4:lib/m4sugar/m4sugar.m4:124: Warning: m4_undefine: undefined macro 
`changeword'
m4:lib/m4sugar/m4sugar.m4:157: Warning: m4_defn: undefined macro `symbols'
m4:lib/m4sugar/m4sugar.m4:157: Warning: m4_undefine: undefined macro `symbols'

I'm debating about removing support for 'symbols' in the first place, since it 
only ever appeared in m4 1.4o (in the eventual m4 2.0, it has been renamed 
m4symbols).  But there are other builtins added in m4 2.0 that will eventually 
need to be addressed.  Also, once m4sugar can assume m4 1.6 or better, we can 
make m4sugar's m4_defn, m4_undefine, and m4_popdef noticeably faster by relying 
on the native warning produced by m4 rather than having to write our own 
wrappers that use m4_ifdef and m4_warn.

The second patch is for something I discovered when trying to fix bison's usage 
of m4sugar [1].  Bison forked m4sugar somewhere in between autoconf 2.59 and 
2.59c, then added m4_prepend, and skips the m4_PACKAGE_* macros defined in 
autoconf's version.m4.  In the future, we may want to move m4sugar (or even 
autom4te, but probably not m4sh) into the M4 package rather than Autoconf, but 
until that time, autoconf should provide all the m4sugar macros that bison 
wants to use to make it easier to resync bison back to autoconf's m4sugar.  
m4_PACKAGE_* macros remain undocumented (autoconf users should use the 
documented AC_AUTOCONF_VERSION instead of m4_PACKAGE_VERSION), so making their 
existence optional for bison's sake is acceptable.

In the process of adding m4_prepend, I noticed a missed optimization in m4 - it 
should be possible for m4_append (but not m4_prepend nor m4_append_uniq) to be 
implemented as O(n log n) rather than O(n^2), but only if m4 is taught that the 
idiom define([$1],defn([$1])[$2]) should behave like the += operator added in 
bash 3.1 (ie. recognizing the special case of appending as an opportunity to 
stick the new suffix into the over-allocated storage already associated with 
the existing definition, and growing the storage geometrically when the suffix 
doesn't fit; rather than the current practice of doing a linear storage growth 
to the exact new size and always copying the entire prefix from the old 
definition into the new storage).  I'll see what I can whip up on the m4 side 
of things, and hopefully get that optimization into 1.6.  In the patch below, I 
used the term 'linearithmic' rather than 'loglinear' for the notion of O(n log 
n); I found both terms in wikipedia [2], and while I am personally more 
familiar with 'loglinear', the wikipedia search for 'n log n' turned up the 
former [3].  See also Bruno's analysis of the speed ramifications of m4_append 
vs. m4_append_uniq [4] (Bruno claimed that appending can be O(n), but because 
of amortized realloc'ing, it is really O(n log n)).

[1] http://thread.gmane.org/gmane.comp.parsers.bison.bugs/2984
[2] http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
[3] http://en.wikipedia.org/wiki/N_log_n
[4] http://lists.gnu.org/archive/html/bug-gnulib/2008-05/msg00064.html

>From 5fb9f9c1a2a310caf37d45d2bc7640723e40c311 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 11 Jul 2008 08:55:15 -0600
Subject: [PATCH] Work around M4 1.6 warning on undefined macros.

* lib/m4sugar/m4sugar.m4 (changeword, symbols): Don't rename if
not already available as builtins.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    6 ++++++
 lib/m4sugar/m4sugar.m4 |   14 +++++++++-----
 2 files changed, 15 insertions(+), 5 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 822e2ca..4df6dc3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2008-07-11  Eric Blake  <address@hidden>
+
+       Work around M4 1.6 warning on undefined macros.
+       * lib/m4sugar/m4sugar.m4 (changeword, symbols): Don't rename if
+       not already available as builtins.
+
 2008-07-06  Ralf Wildenhues  <address@hidden>
 
        * doc/autoconf.texi (@dvar): Remove trailing newline.
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 4f86546..faa86ee 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -117,11 +117,16 @@ m4_define([m4_copy_unm4],
 
 
 # Some m4 internals have names colliding with tokens we might use.
-# Rename them a` la `m4 --prefix-builtins'.
+# Rename them a` la `m4 --prefix-builtins'.  Conditionals first, since
+# some subsequent renames are conditional.
+m4_rename_m4([ifdef])
+m4_rename([ifelse], [m4_if])
+
 m4_rename_m4([builtin])
 m4_rename_m4([changecom])
 m4_rename_m4([changequote])
-m4_undefine([changeword])
+m4_ifdef([changeword],dnl conditionally available in 1.4.x
+[m4_undefine([changeword])])
 m4_rename_m4([debugfile])
 m4_rename_m4([debugmode])
 m4_rename_m4([decr])
@@ -132,8 +137,6 @@ m4_rename_m4([errprint])
 m4_rename_m4([esyscmd])
 m4_rename_m4([eval])
 m4_rename_m4([format])
-m4_rename_m4([ifdef])
-m4_rename([ifelse], [m4_if])
 m4_undefine([include])
 m4_rename_m4([incr])
 m4_rename_m4([index])
@@ -154,7 +157,8 @@ m4_rename([regexp], [m4_bregexp])
 m4_rename_m4([shift])
 m4_undefine([sinclude])
 m4_rename_m4([substr])
-m4_rename_m4([symbols])
+m4_ifdef([symbols],dnl present only in alpha-quality 1.4o
+[m4_rename_m4([symbols])])
 m4_rename_m4([syscmd])
 m4_rename_m4([sysval])
 m4_rename_m4([traceoff])
-- 
1.5.6


>From 8d6a8686929e52e9bd1c4a0298132b172dfe96e1 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 11 Jul 2008 11:14:46 -0600
Subject: [PATCH] Inherit improvements from bison's fork of m4sugar.

* lib/m4sugar/m4sugar.m4 (m4_PACKAGE_VERSION): Ignore failure to
find version.texi, since bison does not provide it.
(m4_prepend): Add new macro, from bison.
(m4_prepend_uniq, m4_prepend_uniq_w): Add new macros, for
completeness.
(_m4_append_uniq): Rename...
(_m4_grow_uniq_1): ...to this to share implementation, and
optimize initial assignment.
(m4_append_uniq_w): Adjust caller.
* NEWS: Document new macros.
* doc/autoconf.texi (Text processing Macros) <m4_append>: Mention
speed consideration.
<m4_prepend>: Document the new prepend variants.
* tests/m4sugar.at (m4@&address@hidden): New test.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   16 +++++++++
 NEWS                   |    3 ++
 doc/autoconf.texi      |   23 +++++++++++++
 lib/m4sugar/m4sugar.m4 |   68 ++++++++++++++++++++++++++++++----------
 tests/m4sugar.at       |   82 ++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 175 insertions(+), 17 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 4df6dc3..9218ddc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,21 @@
 2008-07-11  Eric Blake  <address@hidden>
 
+       Inherit improvements from bison's fork of m4sugar.
+       * lib/m4sugar/m4sugar.m4 (m4_PACKAGE_VERSION): Ignore failure to
+       find version.texi, since bison does not provide it.
+       (m4_prepend): Add new macro, from bison.
+       (m4_prepend_uniq, m4_prepend_uniq_w): Add new macros, for
+       completeness.
+       (_m4_append_uniq): Rename...
+       (_m4_grow_uniq_1): ...to this to share implementation, and
+       optimize initial assignment.
+       (m4_append_uniq_w): Adjust caller.
+       * NEWS: Document new macros.
+       * doc/autoconf.texi (Text processing Macros) <m4_append>: Mention
+       speed consideration.
+       <m4_prepend>: Document the new prepend variants.
+       * tests/m4sugar.at (m4@&address@hidden): New test.
+
        Work around M4 1.6 warning on undefined macros.
        * lib/m4sugar/m4sugar.m4 (changeword, symbols): Don't rename if
        not already available as builtins.
diff --git a/NEWS b/NEWS
index 06b705f..86203db 100644
--- a/NEWS
+++ b/NEWS
@@ -26,6 +26,9 @@ GNU Autoconf NEWS - User visible changes.
 ** Config header templates `#undef UNDEFINED /* comment */' do not lead to
    nested comments any more; regression introduced in 2.62.
 
+** The following m4sugar macros are new:
+   m4_prepend  m4_prepend_uniq  m4_prepend_uniq_w
+
 
 * Major changes in Autoconf 2.62 (2008-04-05) [stable]
   Released by Eric Blake, based on git versions 2.61a.*.
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index f312378..672e76b 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -11055,6 +11055,12 @@ to grow strings without duplicating substrings.  
Additionally,
 Also, @code{m4_append_uniq} warns if @var{separator} is not empty, but
 occurs within @var{string}, since that can lead to duplicates.
 
+Note that @code{m4_append} can scale @dfn{linearithmically} (ie., O(n
+log n) in complexity notation), 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.
+
 @example
 m4_define([active], [ACTIVE])dnl
 m4_append([sentence], [This is an])dnl
@@ -11165,6 +11171,23 @@ with a single space.  This is a combination of @code
{m4_flatten} and
 @code{m4_strip}.
 @end defmac
 
address@hidden m4_prepend (@var{macro-name}, @var{string}, @ovar{separator})
address@hidden m4_prepend_uniq (@var{macro-name}, @var{string}, 
@ovar{separator} @
+  @ovar{if-uniq}, @ovar{if-duplicate})
address@hidden m4_append_uniq_w (@var{macro-name}, @var{strings})
address@hidden
address@hidden
address@hidden
+These macros were introduced in Autoconf 2.63; they are like
address@hidden, @code{m4_append_uniq}, and @code{m4_append_uniq_w}
+respectively, except that the @var{string} argument is added at the
+beginning instead of the end of the definition of @code{macro-name}.
+
+Also note that unlike @code{m4_append}, @code{m4_prepend} has quadratic
+rather than linearithmic scaling behavior.  Thus, if the order of list
+elements does not matter, it is better to append.
address@hidden defmac
+
 @defmac m4_re_escape (@var{string})
 @msindex{re_escape}
 Backslash-escape all characters in @var{string} that are active in
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index faa86ee..0a708f6 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -1876,9 +1876,11 @@ m4_define([m4_combine],
 
 
 # m4_append(MACRO-NAME, STRING, [SEPARATOR])
-# ------------------------------------------
+# m4_prepend(MACRO-NAME, STRING, [SEPARATOR])
+# -------------------------------------------
 # Redefine MACRO-NAME to hold its former content plus `SEPARATOR`'STRING'
-# at the end.  It is valid to use this macro with MACRO-NAME undefined,
+# at the end for m4_append, or `STRING`'SEPARATOR' at the beginning for
+# m4_prepend.  It is valid to use this macro with MACRO-NAME undefined,
 # in which case no SEPARATOR is added.  Be aware that the criterion is
 # `not being defined', and not `not being empty'.
 #
@@ -1921,37 +1923,67 @@ m4_define([m4_combine],
 #    => one, two, three
 #    => [one],[two],[three]
 #
+# Note that m4_append can benefit from amortized O(n log n) m4 behavior, if
+# the underlying m4 implementation is smart enough to avoid copying existing
+# contents when enlarging a macro's definition into any pre-allocated storage
+# (m4 1.4.x unfortunately does not implement this optimization).  m4_prepend
+# is inherently O(n^2), since pre-allocated storage only occurs at the end
+# of a macro, so the existing contents must always be moved.
+#
 # Use m4_builtin to avoid overhead of m4_defn.
 m4_define([m4_append],
 [m4_define([$1],
           m4_ifdef([$1], [m4_builtin([defn], [$1])[$3]])[$2])])
+m4_define([m4_prepend],
+[m4_define([$1],
+          [$2]m4_ifdef([$1], [[$3]m4_builtin([defn], [$1])]))])
 
 
 # m4_append_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
-# --------------------------------------------------------------------
-# Like `m4_append', but append only if not yet present.  Additionally,
-# expand IF-UNIQ if STRING was appended, or IF-DUP if STRING was already
-# present.  Also, warn if SEPARATOR is not empty and occurs within STRING,
-# as the algorithm no longer guarantees uniqueness.
+# m4_prepend_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
+# ---------------------------------------------------------------------
+# Like `m4_append'/`m4_prepend', but add STRING only if not yet present.
+# Additionally, expand IF-UNIQ if STRING was appended, or IF-DUP if STRING
+# was already present.  Also, warn if SEPARATOR is not empty and occurs
+# within STRING, as the algorithm no longer guarantees uniqueness.
+#
+# Note that while m4_append can be O(n log n) (depending on whether the
+# underlying M4 implementation), m4_append_uniq is inherently O(n^2)
+# because each append operation searches the entire string.
 m4_define([m4_append_uniq],
-[m4_ifval([$3], [m4_if(m4_index([$2], [$3]), [-1], [],
+[_m4_grow_uniq([m4_append], $@)])
+m4_define([m4_prepend_uniq],
+[_m4_grow_uniq([m4_prepend], $@)])
+
+# _m4_grow_uniq(HOW, MACRO-NAME, STRING, [SEP], [IF-UNIQ], [IF-DUP])
+# ------------------------------------------------------------------
+# Shared implementation of m4_append_uniq and m4_prepend_uniq.  HOW is
+# used to distinguish where the STRING will be added.
+m4_define([_m4_grow_uniq],
+[m4_ifval([$4], [m4_if(m4_index([$3], [$4]), [-1], [],
                       [m4_warn([syntax],
-                               [$0: `$2' contains `$3'])])])_$0($@)])
-m4_define([_m4_append_uniq],
-[m4_ifdef([$1],
-         [m4_if(m4_index([$3]m4_builtin([defn], [$1])[$3], [$3$2$3]), [-1],
-                [m4_append([$1], [$2], [$3])$4], [$5])],
-         [m4_append([$1], [$2], [$3])$4])])
+                               [$1_uniq: `$3' contains `$4'])])])]$0_1($@))
+m4_define([_m4_grow_uniq_1],
+[m4_ifdef([$2],
+         [m4_if(m4_index([$4]m4_builtin([defn], [$2])[$4], [$4$3$4]), [-1],
+                [$1([$2], [$3], [$4])$5], [$6])],
+         [m4_define([$2], [$3])$5])])
 
 # m4_append_uniq_w(MACRO-NAME, STRINGS)
-# -------------------------------------
+# m4_prepend_uniq_w(MACRO-NAME, STRINGS)
+# --------------------------------------
 # For each of the words in the whitespace separated list STRINGS, append
 # only the unique strings to the definition of MACRO-NAME.
 #
 # Avoid overhead of m4_defn by using m4_builtin.
 m4_define([m4_append_uniq_w],
 [m4_foreach_w([m4_Word], [$2],
-             [_m4_append_uniq([$1], m4_builtin([defn], [m4_Word]), [ ])])])
+             [_m4_grow_uniq_1([m4_append], [$1],
+                              m4_builtin([defn], [m4_Word]), [ ])])])
+m4_define([m4_prepend_uniq_w],
+[m4_foreach_w([m4_Word], [$2],
+             [_m4_grow_uniq_1([m4_prepend], [$1],
+                              m4_builtin([defn], [m4_Word]), [ ])])])
 
 
 # m4_text_wrap(STRING, [PREFIX], [FIRST-PREFIX], [WIDTH])
@@ -2202,7 +2234,9 @@ m4_define([m4_version_compare],
 # m4_PACKAGE_STRING
 # m4_PACKAGE_BUGREPORT
 # --------------------
-m4_include([m4sugar/version.m4])
+# If m4sugar/version.m4 is present, then define version strings.  This
+# file is optional, provided by Autoconf but absent in Bison.
+m4_sinclude([m4sugar/version.m4])
 
 
 # m4_version_prereq(VERSION, [IF-OK], [IF-NOT = FAIL])
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 69cb74b..6cbf4f6 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -278,6 +278,88 @@ AT_CHECK_M4SUGAR([-o-], 0, [[a a b
 AT_CLEANUP
 
 
+## ------------ ##
+## m4_prepend.  ##
+## ------------ ##
+
+AT_SETUP([m4@&address@hidden)
+
+AT_CHECK_M4SUGAR_TEXT(
+[[m4_define([active], [ACTIVE])dnl
+m4_prepend([sentence], [This is an])dnl
+m4_prepend([sentence], [ active ])dnl
+m4_prepend([sentence], [symbol.])dnl
+sentence
+m4_undefine([active])dnl
+sentence
+m4_define([active], [ACTIVE])dnl
+m4_prepend([hooks], [m4_define([act1], [act2])])dnl
+m4_prepend([hooks], [m4_define([act2], [active])])dnl
+m4_undefine([active])dnl
+act1
+hooks
+act1
+dnl Test for bug fixed in 2.62 when separator is active.
+m4_define([a], [A])dnl
+m4_prepend_uniq([foo], [-], [a])dnl
+m4_prepend_uniq([foo], [-], [a])dnl
+m4_prepend_uniq([bar], [-], [a])dnl
+m4_prepend_uniq([bar], [~], [a])dnl
+m4_prepend_uniq([bar], [-], [a])dnl
+m4_defn([foo])
+m4_defn([bar])
+foo
+bar
+m4_prepend_uniq([blah], [one], [, ], [new], [existing])
+m4_prepend_uniq([blah], [two], [, ], [new], [existing])
+m4_prepend_uniq([blah], [two], [, ], [new], [existing])
+m4_prepend_uniq([blah], [three], [, ], [new], [existing])
+m4_prepend([blah], [two], [, ])dnl
+blah
+m4_dquote(blah)
+m4_prepend([list], [one], [[, ]])dnl
+m4_prepend([list], [two], [[, ]])dnl
+m4_prepend([list], [three], [[, ]])dnl
+list
+m4_dquote(list)
+m4_prepend_uniq_w([numbers], [1 1 2])dnl
+m4_prepend_uniq_w([numbers], [ 2 3 ])dnl
+numbers
+]],
+[[symbol. ACTIVE This is an
+symbol. active This is an
+act1
+
+active
+-
+~a-
+-
+~A-
+new
+new
+existing
+new
+two, three, two, one
+[two],[three],[two],[one]
+three, two, one
+[three, two, one]
+3 2 1
+]])
+
+AT_DATA_M4SUGAR([script.4s],
+[[m4_prepend_uniq([str], [a], [ ])
+m4_prepend_uniq([str], [a b], [ ])
+m4_divert([0])dnl
+str
+]])
+
+AT_CHECK_M4SUGAR([-o-], 0, [[a b a
+]], [[script.4s:2: warning: m4@&address@hidden: `a b' contains ` '
+]])
+
+AT_CLEANUP
+
+
 ## --------- ##
 ## m4_join.  ##
 ## --------- ##
-- 
1.5.6