autoconf-patches
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

faster AS_IF,AS_CASE


From: Eric Blake
Subject: faster AS_IF,AS_CASE
Date: Wed, 13 Aug 2008 16:27:26 +0000 (UTC)
User-agent: Loom/3.14 (http://gmane.org/)

This fixes the remaining two quadratic implementations when using autoconf with 
m4 1.4.x (based on inspection of "git grep 'm4_\(shift\|cdr\)'"; a macro is 
quadratic on older m4 if it processes the first few arguments, then recurses 
with the remaining arguments shifted).  And since m4sh.m4 has a net decrease in 
code size, it seems like a nice factorization, not to mention a cleaner 
separation by providing the linear foundation in m4sugar rather than mixing 
m4sh into foreach.m4.

I'm not applying this patch on savannah yet, in case there are any comments.  
For example, is my new macro m4_foreach_pair worth documenting as a supported 
interface, or should I leave it undocumented?  Also, should it be named 
slightly differently since it behaves more like m4_map than m4_foreach?

But if you want to play with it, use
$ git pull git://repo.or.cz/autoconf/ericb.git as-if
or see
http://repo.or.cz/w/autoconf/ericb.git?a=shortlog;h=refs/heads/as-if

>From 1a324c67f6d9cbc5555e1e70a67f680fe5dca209 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Wed, 13 Aug 2008 09:12:28 -0600
Subject: [PATCH] Implement m4_foreach_pair.

* lib/m4sugar/m4sugar.m4 (m4_foreach_pair): New macro,
undocumented for now.
* lib/m4sugar/foreach.m4 (m4_foreach_pair): Also the m4 1.4.x
counterpart.
* lib/m4sugar/m4sh.m4 (AS_IF, AS_CASE): Use it.
* tests/m4sh.at (AS@&address@hidden and AS@&address@hidden): Test it.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   10 ++++++++++
 lib/m4sugar/foreach.m4 |   26 ++++++++++++++++++++++++++
 lib/m4sugar/m4sh.m4    |   21 +++++++++------------
 lib/m4sugar/m4sugar.m4 |   20 ++++++++++++++++++++
 tests/m4sh.at          |   27 +++++++++++++++++++++++++++
 5 files changed, 92 insertions(+), 12 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index aa82465..ad12452 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2008-08-13  Eric Blake  <address@hidden>
+
+       Implement m4_foreach_pair.
+       * lib/m4sugar/m4sugar.m4 (m4_foreach_pair): New macro,
+       undocumented for now.
+       * lib/m4sugar/foreach.m4 (m4_foreach_pair): Also the m4 1.4.x
+       counterpart.
+       * lib/m4sugar/m4sh.m4 (AS_IF, AS_CASE): Use it.
+       * tests/m4sh.at (AS@&address@hidden and AS@&address@hidden): Test it.
+
 2008-08-12  Eric Blake  <address@hidden>
 
        Optimize m4_bmatch.
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 816ee60..ba37105 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -251,6 +251,32 @@ m4_define([m4_reverse],
     [[, ]m4_dquote([$]_m4_r)])[_m4_popdef([_m4_r])])_m4_r($@)])])
 
 
+# m4_foreach_pair(EXPRESSION, [END-EXPR = EXPRESSION], ARG...)
+# ------------------------------------------------------------
+# Perform a pairwise grouping of consecutive ARGs, by expanding
+# EXPRESSION([ARG1], [ARG2]).  If there are an odd number of ARGs, the
+# final argument is expanded with END-EXPR([ARGn]).
+#
+# Build the temporary macro _m4_foreach_pair, with the $2([$m+1]) only
+# output if $# is odd:
+#   $1([$3], [$4])[]$1([$5], [$6])[]...$1([$m-1],
+#   [$m])[]m4_default([$2], [$1])([$m+1])[]_m4_popdef([_m4_foreach_pair])
+m4_define([m4_foreach_pair],
+[m4_if([$#], [0], [m4_fatal([$0: too few arguments: $#])],
+       [$#], [1], [m4_fatal([$0: too few arguments: $#: $1])],
+       [$#], [2], [],
+       [$#], [3], [m4_default([$2], [$1])([$3])[]],
+       [m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [3],
+   m4_eval([$# / 2 * 2 - 1]), [2], [_$0_([1], _$0, m4_incr(_$0))])_$0_end(
+   [1], [2], [$#])[_m4_popdef([_$0])])_$0($@)])])
+
+m4_define([_m4_foreach_pair_],
+[[$$1([$$2], [$$3])[]]])
+
+m4_define([_m4_foreach_pair_end],
+[m4_if(m4_eval([$3 & 1]), [1], [[m4_default([$$2], [$$1])([$$3])[]]])])
+
+
 # m4_map(MACRO, LIST)
 # -------------------
 # Invoke MACRO($1), MACRO($2) etc. where $1, $2... are the elements
diff --git a/lib/m4sugar/m4sh.m4 b/lib/m4sugar/m4sh.m4
index 74d8377..d1bc241 100644
--- a/lib/m4sugar/m4sh.m4
+++ b/lib/m4sugar/m4sh.m4
@@ -453,16 +453,15 @@ m4_defun([AS_PREPARE],
 # | *) DEFAULT ;;
 # | esac
 m4_define([_AS_CASE],
-[m4_if([$#], 0, [m4_fatal([$0: too few arguments: $#])],
-       [$#], 1, [  *) $1 ;;],
-       [$#], 2, [  $1) m4_default([$2], [:]) ;;],
-       [  $1) m4_default([$2], [:]) ;;
-$0(m4_shift2($@))])dnl
+[  $1[)] m4_default([$2], [:]) ;;
+])
+m4_define([_AS_CASE_DEFAULT],
+[  *[)] $1 ;;
 ])
 m4_defun([AS_CASE],
 [m4_ifval([$2$3],
 [case $1 in
-_AS_CASE(m4_shift($@))
+m4_foreach_pair([_$0], [_$0_DEFAULT], m4_shift($@))dnl
 esac
 ])dnl
 ])# AS_CASE
@@ -496,20 +495,18 @@ m4_define([AS_EXIT],
 # with simplifications if IF-TRUE1 and/or IF-FALSE is empty.
 #
 m4_define([_AS_IF],
-[m4_ifval([$2$3],
 [elif $1; then
   m4_default([$2], [:])
-m4_ifval([$3], [$0(m4_shift2($@))])],
+])
+m4_define([_AS_IF_ELSE],
 [m4_ifvaln([$1],
 [else
-  $1])dnl
-])dnl
-])# _AS_IF
+  $1])])
 m4_defun([AS_IF],
 [m4_ifval([$2$3],
 [if $1; then
   m4_default([$2], [:])
-m4_ifval([$3], [_$0(m4_shift2($@))])[]dnl
+m4_foreach_pair([_$0], [_$0_ELSE], m4_shift2($@))dnl
 fi
 ])dnl
 ])# AS_IF
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 22af6ef..63fadf2 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -1000,6 +1000,26 @@ m4_define([_m4_foreach],
 m4_define([m4_foreach_w],
 [m4_foreach([$1], m4_split(m4_normalize([$2]), [ ]), [$3])])
 
+# m4_foreach_pair(EXPRESSION, [END-EXPR = EXPRESSION], ARG...)
+# ------------------------------------------------------------
+# Perform a pairwise grouping of consecutive ARGs, by expanding
+# EXPRESSION([ARG1], [ARG2]).  If there are an odd number of ARGs, the
+# final argument is expanded with END-EXPR([ARGn]).
+#
+# For example:
+#   m4_define([show], [($*)m4_newline])dnl
+#   m4_foreach_pair([show], [], [a], [b], [c], [d], [e])dnl
+#   => (a,b)
+#   => (c,d)
+#   => (e)
+m4_define([m4_foreach_pair],
+[m4_if([$#], [0], [m4_fatal([$0: too few arguments: $#])],
+       [$#], [1], [m4_fatal([$0: too few arguments: $#: $1])],
+       [$#], [2], [],
+       [$#], [3], [m4_default([$2], [$1])([$3])[]],
+       [$#], [4], [m4_apply([$1], [[$3], [$4]])[]],
+       [$1([$3], [$4])[]$0([$1], [$2], m4_shift(m4_shift3($@)))])])
+
 
 # m4_map(MACRO, LIST)
 # -------------------
diff --git a/tests/m4sh.at b/tests/m4sh.at
index e01f769..ac5f8ba 100644
--- a/tests/m4sh.at
+++ b/tests/m4sh.at
@@ -634,6 +634,8 @@ AT_CLEANUP
 
 AT_SETUP([AS@&address@hidden and AS@&address@hidden)
 
+AT_KEYWORDS([m4@&address@hidden)
+
 AT_DATA_M4SH([script.as], [[dnl
 AS_INIT
 # Syntax checks: cope with empty arguments.
@@ -725,6 +727,31 @@ foo8=8 bar8=8
 foo9=9 bar9=9
 ]])
 
+dnl stress test for large number of conditionals
+AT_DATA_M4SH([script.as], [[dnl
+AS_INIT
+AS_IF(m4_shift(m4_for([i], [1], [1000], [], [, test $[1] = i, echo i])))
+AS_IF(m4_shift(m4_for([i], [1], [1000], [], [, test $[1] = i, echo i])),
+      [echo default])
+AS_CASE([$[1]]m4_for([i], [1], [1000], [], [, i, echo i]))
+AS_CASE([$[1]]m4_for([i], [1], [1000], [], [, i, echo i]), [echo default])
+]])
+
+AT_CHECK_M4SH
+AT_CHECK([./script 1], [0], [[1
+1
+1
+1
+]])
+AT_CHECK([./script 1000], [0], [[1000
+1000
+1000
+1000
+]])
+AT_CHECK([./script default], [0], [[default
+default
+]])
+
 AT_CLEANUP
 
 
-- 
1.5.6.4








reply via email to

[Prev in Thread] Current Thread [Next in Thread]