faster m4_bmatch

[Eric Blake]

With this patch, I've come up with a linear solution for all of the m4sugar 
macros that previously triggered quadratic scaling in m4 1.4.x.  However, there 
are still quadratic functions at other levels (for example, AS_CASE).

From: Eric Blake <address@hidden>
Date: Tue, 12 Aug 2008 15:23:56 -0600
Subject: [PATCH] Optimize m4_bmatch.

* lib/m4sugar/foreach.m4 (m4_bmatch): Provide linear
implementation for m4 1.4.x.
* tests/m4sugar.at (m4@&address@hidden): New test.
(recursion): Test the linear nature.
* NEWS: Document the fix.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    7 +++++++
 NEWS                   |    5 +++--
 lib/m4sugar/foreach.m4 |   33 +++++++++++++++++++++++++++++++++
 tests/m4sugar.at       |   40 +++++++++++++++++++++++++++++++++++++++-
 4 files changed, 82 insertions(+), 3 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index d460078..aa82465 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
 2008-08-12  Eric Blake  <address@hidden>
 
+       Optimize m4_bmatch.
+       * lib/m4sugar/foreach.m4 (m4_bmatch): Provide linear
+       implementation for m4 1.4.x.
+       * tests/m4sugar.at (m4@&address@hidden): New test.
+       (recursion): Test the linear nature.
+       * NEWS: Document the fix.
+
        Fix m4_cond corner case.
        * lib/m4sugar/foreach.m4 (_m4_cond): Ensure alternate
        implementation allows concatenation with subsequent text.
diff --git a/NEWS b/NEWS
index dbff114..2cf6747 100644
--- a/NEWS
+++ b/NEWS
@@ -38,8 +38,9 @@ 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_bpatsubsts  m4_case  m4_cond  m4_do  m4_dquote_elt  m4_foreach
-   m4_join  m4_list_cmp  m4_map  m4_map_sep  m4_max  m4_min  m4_shiftn
+   m4_bmatch  m4_bpatsubsts  m4_case  m4_cond  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/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index b85fce2..816ee60 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -121,6 +121,39 @@ m4_define([m4_case],
 m4_define([_m4_case_],
 [[[$$1],[$$2],[$$3],]])
 
+# m4_bmatch(SWITCH, RE1, VAL1, RE2, VAL2, ..., DEFAULT)
+# -----------------------------------------------------
+# m4 equivalent of
+#
+# if (SWITCH =~ RE1)
+#   VAL1;
+# elif (SWITCH =~ RE2)
+#   VAL2;
+# elif ...
+#   ...
+# else
+#   DEFAULT
+#
+# We build the temporary macro _m4_b:
+#   m4_define([_m4_b], _m4_defn([_m4_bmatch]))_m4_b([$1], [$2], [$3])...
+#   _m4_b([$1], [$m-1], [$m])_m4_b([], [], [$m+1]_m4_popdef([_m4_b]))
+# then invoke m4_unquote(_m4_b($@)), for concatenation with later text.
+m4_define([m4_bmatch],
+[m4_if([$#], 0, [m4_fatal([$0: too few arguments: $#])],
+       [$#], 1, [m4_fatal([$0: too few arguments: $#: $1])],
+       [$#], 2, [$2],
+       [m4_define([_m4_b], m4_pushdef([_m4_b])[m4_define([_m4_b],
+  _m4_defn([_$0]))]_m4_for([_m4_b], [3], m4_eval([($# + 1) / 2 * 2 - 1]),
+  [2], [_$0_([1], m4_decr(_m4_b), _m4_b)])[_m4_b([], [],]m4_dquote(
+  [$]m4_incr(_m4_b))[_m4_popdef([_m4_b]))])m4_unquote(_m4_b($@))])])
+
+m4_define([_m4_bmatch],
+[m4_if(m4_bregexp([$1], [$2]), [-1], [], [[$3]m4_define([$0])])])
+
+m4_define([_m4_bmatch_],
+[[_m4_b([$$1], [$$2], [$$3])]])
+
+
 # m4_cond(TEST1, VAL1, IF-VAL1, TEST2, VAL2, IF-VAL2, ..., [DEFAULT])
 # -------------------------------------------------------------------
 # Similar to m4_if, except that each TEST is expanded when encountered.
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 8e5fd01..8e9885a 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -573,6 +573,38 @@ AT_CHECK_M4RE([m4_re_string], address@hidden)
 
 AT_CLEANUP
 
+## ----------- ##
+## m4_bmatch.  ##
+## ----------- ##
+
+AT_SETUP([m4@&address@hidden)
+
+AT_CHECK_M4SUGAR_TEXT(
+[[m4_bmatch([abc], [default\])
+m4_bmatch([abc], [^a], [yes])
+m4_bmatch([abc], [^a], [yes], [no])
+m4_bmatch([abc], [^.a], [yes])
+m4_bmatch([abc], [^.a], [yes], [no\])
+m4_bmatch([abc], [a], [1], [b], [2])
+m4_bmatch([abc], [A], [1], [b], [2])
+m4_define([ab], [AB])dnl
+m4_bmatch([$*], [a])b
+m4_bmatch([$*], [\*], [a])b
+m4_bmatch([$*], [1], [2], [a])b
+]], [[default\
+yes
+yes
+
+no\
+1
+2
+AB
+AB
+AB
+]])
+
+AT_CLEANUP
+
 ## --------------- ##
 ## m4_bpatsubsts.  ##
 ## --------------- ##
@@ -870,7 +902,8 @@ 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 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,
@@ -895,6 +928,7 @@ 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_bmatch([9997]m4_for([i], [1], [10000], [], [,^i$]))
 m4_define([up], [m4_define([$1], m4_incr($1))$1])m4_define([j], 0)dnl
 m4_cond(m4_for([i], [1], [10000], [], [[up([j])], [9990], i,]) [oops]) j
 m4_divert_pop(0)
@@ -910,6 +944,7 @@ end
 0
 0
 A
+^9998$
 9990 9990
 ]])
 
@@ -926,6 +961,7 @@ end
 0
 0
 A
+^9998$
 9990 9990
 m4_exit([0])])
 m4_init
@@ -945,6 +981,7 @@ 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_bmatch([9997]m4_for([i], [1], [10000], [], [,^i$]))
 m4_define([up], [m4_define([$1], m4_incr($1))$1])m4_define([j], 0)dnl
 m4_cond(m4_for([i], [1], [10000], [], [[up([j])], [9990], i,]) [oops])
 m4_divert_pop(0)
@@ -960,6 +997,7 @@ end
 0
 0
 A
+^9998$
 9990 9990
 ]])
 
-- 
1.5.6.4