data/m4sugar/foreach.m4

   1 #                                                  -*- Autoconf -*-
   2 # This file is part of Autoconf.
   3 # foreach-based replacements for recursive functions.
   4 # Speeds up GNU M4 1.4.x by avoiding quadratic $@ recursion, but penalizes
   5 # GNU M4 1.6 by requiring more memory and macro expansions.
   6 #
   7 # Copyright (C) 2008 Free Software Foundation, Inc.
   8 #
   9 # This program is free software: you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation, either version 3 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # This program is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 # As a special exception, the Free Software Foundation gives unlimited
  23 # permission to copy, distribute and modify the configure scripts that
  24 # are the output of Autoconf.  You need not follow the terms of the GNU
  25 # General Public License when using or distributing such scripts, even
  26 # though portions of the text of Autoconf appear in them.  The GNU
  27 # General Public License (GPL) does govern all other use of the material
  28 # that constitutes the Autoconf program.
  29 #
  30 # Certain portions of the Autoconf source text are designed to be copied
  31 # (in certain cases, depending on the input) into the output of
  32 # Autoconf.  We call these the "data" portions.  The rest of the Autoconf
  33 # source text consists of comments plus executable code that decides which
  34 # of the data portions to output in any given case.  We call these
  35 # comments and executable code the "non-data" portions.  Autoconf never
  36 # copies any of the non-data portions into its output.
  37 #
  38 # This special exception to the GPL applies to versions of Autoconf
  39 # released by the Free Software Foundation.  When you make and
  40 # distribute a modified version of Autoconf, you may extend this special
  41 # exception to the GPL to apply to your modified version as well, *unless*
  42 # your modified version has the potential to copy into its output some
  43 # of the text that was the non-data portion of the version that you started
  44 # with.  (In other words, unless your change moves or copies text from
  45 # the non-data portions to the data portions.)  If your modification has
  46 # such potential, you must delete any notice of this special exception
  47 # to the GPL from your modified version.
  48 #
  49 # Written by Eric Blake.
  50 #
  51
  52 # In M4 1.4.x, every byte of $@ is rescanned.  This means that an
  53 # algorithm on n arguments that recurses with one less argument each
  54 # iteration will scan n * (n + 1) / 2 arguments, for O(n^2) time.  In
  55 # M4 1.6, this was fixed so that $@ is only scanned once, then
  56 # back-references are made to information stored about the scan.
  57 # Thus, n iterations need only scan n arguments, for O(n) time.
  58 # Additionally, in M4 1.4.x, recursive algorithms did not clean up
  59 # memory very well, requiring O(n^2) memory rather than O(n) for n
  60 # iterations.
  61 #
  62 # This file is designed to overcome the quadratic nature of $@
  63 # recursion by writing a variant of m4_foreach that uses m4_for rather
  64 # than $@ recursion to operate on the list.  This involves more macro
  65 # expansions, but avoids the need to rescan a quadratic number of
  66 # arguments, making these replacements very attractive for M4 1.4.x.
  67 # On the other hand, in any version of M4, expanding additional macros
  68 # costs additional time; therefore, in M4 1.6, where $@ recursion uses
  69 # fewer macros, these replacements actually pessimize performance.
  70 # Additionally, the use of $10 to mean the tenth argument violates
  71 # POSIX; although all versions of m4 1.4.x support this meaning, a
  72 # future m4 version may switch to take it as the first argument
  73 # concatenated with a literal 0, so the implementations in this file
  74 # are not future-proof.  Thus, this file is conditionally included as
  75 # part of m4_init(), only when it is detected that M4 probably has
  76 # quadratic behavior (ie. it lacks the macro __m4_version__).
  77
  78 # m4_foreach(VARIABLE, LIST, EXPRESSION)
  79 # --------------------------------------
  80 # Expand EXPRESSION assigning each value of the LIST to VARIABLE.
  81 # LIST should have the form `item_1, item_2, ..., item_n', i.e. the
  82 # whole list must *quoted*.  Quote members too if you don't want them
  83 # to be expanded.
  84 #
  85 # This version minimizes the number of times that $@ is evaluated by
  86 # using m4_for to generate a boilerplate into VARIABLE then passing $@
  87 # to that temporary macro.  Thus, the recursion is done in m4_for
  88 # without reparsing any user input, and is not quadratic.  For an idea
  89 # of how this works, note that m4_foreach(i,[1,2],[i]) defines i to be
  90 #   m4_define([$1],[$3])$2[]m4_define([$1],[$4])$2[]m4_popdef([i])
  91 # then calls i([i],[i],[1],[2]).
  92 m4_define([m4_foreach],
  93 [m4_if([$2], [], [], [_$0([$1], [$3], $2)])])
  94
  95 m4_define([_m4_foreach],
  96 [m4_define([$1], m4_pushdef([$1])_m4_for([$1], [3], [$#], [1],
  97     [$0_([1], [2], _m4_defn([$1]))])[m4_popdef([$1])])m4_indir([$1], $@)])
  98
  99 m4_define([_m4_foreach_],
 100 [[m4_define([$$1], [$$3])$$2[]]])
 101
 102 # m4_case(SWITCH, VAL1, IF-VAL1, VAL2, IF-VAL2, ..., DEFAULT)
 103 # -----------------------------------------------------------
 104 # Find the first VAL that SWITCH matches, and expand the corresponding
 105 # IF-VAL.  If there are no matches, expand DEFAULT.
 106 #
 107 # Use m4_for to create a temporary macro in terms of a boilerplate
 108 # m4_if with final cleanup.  If $# is even, we have DEFAULT; if it is
 109 # odd, then rounding the last $# up in the temporary macro is
 110 # harmless.  For example, both m4_case(1,2,3,4,5) and
 111 # m4_case(1,2,3,4,5,6) result in the intermediate _m4_case being
 112 #   m4_if([$1],[$2],[$3],[$1],[$4],[$5],_m4_popdef([_m4_case])[$6])
 113 m4_define([m4_case],
 114 [m4_if(m4_eval([$# <= 2]), [1], [$2],
 115 [m4_pushdef([_$0], [m4_if(]m4_for([_m4_count], [2], m4_decr([$#]), [2],
 116      [_$0_([1], _m4_count, m4_incr(_m4_count))])[_m4_popdef(
 117          [_$0])]m4_dquote($m4_eval([($# + 1) & ~1]))[)])_$0($@)])])
 118
 119 m4_define([_m4_case_],
 120 [[[$$1],[$$2],[$$3],]])
 121
 122 # m4_bmatch(SWITCH, RE1, VAL1, RE2, VAL2, ..., DEFAULT)
 123 # -----------------------------------------------------
 124 # m4 equivalent of
 125 #
 126 # if (SWITCH =~ RE1)
 127 #   VAL1;
 128 # elif (SWITCH =~ RE2)
 129 #   VAL2;
 130 # elif ...
 131 #   ...
 132 # else
 133 #   DEFAULT
 134 #
 135 # We build the temporary macro _m4_b:
 136 #   m4_define([_m4_b], _m4_defn([_m4_bmatch]))_m4_b([$1], [$2], [$3])...
 137 #   _m4_b([$1], [$m-1], [$m])_m4_b([], [], [$m+1]_m4_popdef([_m4_b]))
 138 # then invoke m4_unquote(_m4_b($@)), for concatenation with later text.
 139 m4_define([m4_bmatch],
 140 [m4_if([$#], 0, [m4_fatal([$0: too few arguments: $#])],
 141        [$#], 1, [m4_fatal([$0: too few arguments: $#: $1])],
 142        [$#], 2, [$2],
 143        [m4_define([_m4_b], m4_pushdef([_m4_b])[m4_define([_m4_b],
 144   _m4_defn([_$0]))]_m4_for([_m4_b], [3], m4_eval([($# + 1) / 2 * 2 - 1]),
 145   [2], [_$0_([1], m4_decr(_m4_b), _m4_b)])[_m4_b([], [],]m4_dquote(
 146   [$]m4_incr(_m4_b))[_m4_popdef([_m4_b]))])m4_unquote(_m4_b($@))])])
 147
 148 m4_define([_m4_bmatch],
 149 [m4_if(m4_bregexp([$1], [$2]), [-1], [], [[$3]m4_define([$0])])])
 150
 151 m4_define([_m4_bmatch_],
 152 [[_m4_b([$$1], [$$2], [$$3])]])
 153
 154
 155 # m4_cond(TEST1, VAL1, IF-VAL1, TEST2, VAL2, IF-VAL2, ..., [DEFAULT])
 156 # -------------------------------------------------------------------
 157 # Similar to m4_if, except that each TEST is expanded when encountered.
 158 # If the expansion of TESTn matches the string VALn, the result is IF-VALn.
 159 # The result is DEFAULT if no tests passed.  This macro allows
 160 # short-circuiting of expensive tests, where it pays to arrange quick
 161 # filter tests to run first.
 162 #
 163 # m4_cond already guarantees either 3*n or 3*n + 1 arguments, 1 <= n.
 164 # We only have to speed up _m4_cond, by building the temporary _m4_c:
 165 #   m4_define([_m4_c], _m4_defn([m4_unquote]))_m4_c([m4_if(($1), [($2)],
 166 #   [[$3]m4_define([_m4_c])])])_m4_c([m4_if(($4), [($5)],
 167 #   [[$6]m4_define([_m4_c])])])..._m4_c([m4_if(($m-2), [($m-1)],
 168 #   [[$m]m4_define([_m4_c])])])_m4_c([[$m+1]]_m4_popdef([_m4_c]))
 169 # We invoke m4_unquote(_m4_c($@)), for concatenation with later text.
 170 m4_define([_m4_cond],
 171 [m4_define([_m4_c], m4_pushdef([_m4_c])[m4_define([_m4_c],
 172   _m4_defn([m4_unquote]))]_m4_for([_m4_c], [2], m4_eval([$# / 3 * 3 - 1]), [3],
 173   [$0_(m4_decr(_m4_c), _m4_c, m4_incr(_m4_c))])[_m4_c(]m4_dquote(m4_dquote(
 174   [$]m4_eval([$# / 3 * 3 + 1])))[_m4_popdef([_m4_c]))])m4_unquote(_m4_c($@))])
 175
 176 m4_define([_m4_cond_],
 177 [[_m4_c([m4_if(($$1), [($$2)], [[$$3]m4_define([_m4_c])])])]])
 178
 179 # m4_bpatsubsts(STRING, RE1, SUBST1, RE2, SUBST2, ...)
 180 # ----------------------------------------------------
 181 # m4 equivalent of
 182 #
 183 #   $_ = STRING;
 184 #   s/RE1/SUBST1/g;
 185 #   s/RE2/SUBST2/g;
 186 #   ...
 187 #
 188 # m4_bpatsubsts already validated an odd number of arguments; we only
 189 # need to speed up _m4_bpatsubsts.  To avoid nesting, we build the
 190 # temporary _m4_p:
 191 #   m4_define([_m4_p], [$1])m4_define([_m4_p],
 192 #   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$2], [$3]))m4_define([_m4_p],
 193 #   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$4], [$5]))m4_define([_m4_p],...
 194 #   m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$m-1], [$m]))m4_unquote(
 195 #   _m4_defn([_m4_p])_m4_popdef([_m4_p]))
 196 m4_define([_m4_bpatsubsts],
 197 [m4_define([_m4_p], m4_pushdef([_m4_p])[m4_define([_m4_p],
 198   ]m4_dquote([$]1)[)]_m4_for([_m4_p], [3], [$#], [2], [$0_(m4_decr(_m4_p),
 199   _m4_p)])[m4_unquote(_m4_defn([_m4_p])_m4_popdef([_m4_p]))])_m4_p($@)])
 200
 201 m4_define([_m4_bpatsubsts_],
 202 [[m4_define([_m4_p],
 203 m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$$1], [$$2]))]])
 204
 205 # m4_shiftn(N, ...)
 206 # -----------------
 207 # Returns ... shifted N times.  Useful for recursive "varargs" constructs.
 208 #
 209 # m4_shiftn already validated arguments; we only need to speed up
 210 # _m4_shiftn.  If N is 3, then we build the temporary _m4_s, defined as
 211 #   ,[$5],[$6],...,[$m]_m4_popdef([_m4_s])
 212 # before calling m4_shift(_m4_s($@)).
 213 m4_define([_m4_shiftn],
 214 [m4_define([_m4_s],
 215            m4_pushdef([_m4_s])_m4_for([_m4_s], m4_eval([$1 + 2]), [$#], [1],
 216   [[,]m4_dquote([$]_m4_s)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])
 217
 218 # m4_do(STRING, ...)
 219 # ------------------
 220 # This macro invokes all its arguments (in sequence, of course).  It is
 221 # useful for making your macros more structured and readable by dropping
 222 # unnecessary dnl's and have the macros indented properly.
 223 #
 224 # Here, we use the temporary macro _m4_do, defined as
 225 #   $1[]$2[]...[]$n[]_m4_popdef([_m4_do])
 226 m4_define([m4_do],
 227 [m4_if([$#], [0], [],
 228        [m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [1], [$#], [1],
 229                   [$_$0[[]]])[_m4_popdef([_$0])])_$0($@)])])
 230
 231 # m4_dquote_elt(ARGS)
 232 # -------------------
 233 # Return ARGS as an unquoted list of double-quoted arguments.
 234 #
 235 # m4_foreach to the rescue.  It's easier to shift off the leading comma.
 236 m4_define([m4_dquote_elt],
 237 [m4_shift(m4_foreach([_m4_elt], [$@], [,m4_dquote(_m4_defn([_m4_elt]))]))])
 238
 239 # m4_reverse(ARGS)
 240 # ----------------
 241 # Output ARGS in reverse order.
 242 #
 243 # Invoke _m4_r($@) with the temporary _m4_r built as
 244 #   [$m], [$m-1], ..., [$2], [$1]_m4_popdef([_m4_r])
 245 m4_define([m4_reverse],
 246 [m4_if([$#], [0], [], [$#], [1], [[$1]],
 247 [m4_define([_m4_r], m4_dquote([$$#])m4_pushdef([_m4_r])_m4_for([_m4_r],
 248       m4_decr([$#]), [1], [-1],
 249     [[, ]m4_dquote([$]_m4_r)])[_m4_popdef([_m4_r])])_m4_r($@)])])
 250
 251
 252 # m4_map(MACRO, LIST)
 253 # -------------------
 254 # Invoke MACRO($1), MACRO($2) etc. where $1, $2... are the elements
 255 # of LIST.  $1, $2... must in turn be lists, appropriate for m4_apply.
 256 #
 257 # m4_map/m4_map_sep only execute once; the speedup comes in fixing
 258 # _m4_map.  The mismatch in () is intentional, since $1 supplies the
 259 # opening `(' (but it sure looks odd!).  Build the temporary _m4_m:
 260 #   $1, [$3])$1, [$4])...$1, [$m])_m4_popdef([_m4_m])
 261 m4_define([_m4_map],
 262 [m4_if([$#], [2], [],
 263        [m4_define([_m4_m], m4_pushdef([_m4_m])_m4_for([_m4_m], [3], [$#], [1],
 264    [$0_([1], _m4_m)])[_m4_popdef([_m4_m])])_m4_m($@)])])
 265
 266 m4_define([_m4_map_],
 267 [[$$1, [$$2])]])
 268
 269 # m4_transform(EXPRESSION, ARG...)
 270 # --------------------------------
 271 # Expand EXPRESSION([ARG]) for each argument.  More efficient than
 272 # m4_foreach([var], [ARG...], [EXPRESSION(m4_defn([var]))])
 273 #
 274 # Invoke the temporary macro _m4_transform, defined as:
 275 #   $1([$2])[]$1([$3])[]...$1([$m])[]_m4_popdef([_m4_transform])
 276 m4_define([m4_transform],
 277 [m4_if([$#], [0], [m4_fatal([$0: too few arguments: $#])],
 278        [$#], [1], [],
 279        [m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [2], [$#], [1],
 280    [_$0_([1], _$0)])[_m4_popdef([_$0])])_$0($@)])])
 281
 282 m4_define([_m4_transform_],
 283 [[$$1([$$2])[]]])
 284
 285 # m4_transform_pair(EXPRESSION, [END-EXPR = EXPRESSION], ARG...)
 286 # --------------------------------------------------------------
 287 # Perform a pairwise grouping of consecutive ARGs, by expanding
 288 # EXPRESSION([ARG1], [ARG2]).  If there are an odd number of ARGs, the
 289 # final argument is expanded with END-EXPR([ARGn]).
 290 #
 291 # Build the temporary macro _m4_transform_pair, with the $2([$m+1])
 292 # only output if $# is odd:
 293 #   $1([$3], [$4])[]$1([$5], [$6])[]...$1([$m-1],
 294 #   [$m])[]m4_default([$2], [$1])([$m+1])[]_m4_popdef([_m4_transform_pair])
 295 m4_define([m4_transform_pair],
 296 [m4_if([$#], [0], [m4_fatal([$0: too few arguments: $#])],
 297        [$#], [1], [m4_fatal([$0: too few arguments: $#: $1])],
 298        [$#], [2], [],
 299        [$#], [3], [m4_default([$2], [$1])([$3])[]],
 300        [m4_define([_$0], m4_pushdef([_$0])_m4_for([_$0], [3],
 301    m4_eval([$# / 2 * 2 - 1]), [2], [_$0_([1], _$0, m4_incr(_$0))])_$0_end(
 302    [1], [2], [$#])[_m4_popdef([_$0])])_$0($@)])])
 303
 304 m4_define([_m4_transform_pair_],
 305 [[$$1([$$2], [$$3])[]]])
 306
 307 m4_define([_m4_transform_pair_end],
 308 [m4_if(m4_eval([$3 & 1]), [1], [[m4_default([$$2], [$$1])([$$3])[]]])])
 309
 310 # m4_join(SEP, ARG1, ARG2...)
 311 # ---------------------------
 312 # Produce ARG1SEPARG2...SEPARGn.  Avoid back-to-back SEP when a given ARG
 313 # is the empty string.  No expansion is performed on SEP or ARGs.
 314 #
 315 # Use a self-modifying separator, since we don't know how many
 316 # arguments might be skipped before a separator is first printed, but
 317 # be careful if the separator contains $.  m4_foreach to the rescue.
 318 m4_define([m4_join],
 319 [m4_pushdef([_m4_sep], [m4_define([_m4_sep], _m4_defn([m4_echo]))])]dnl
 320 [m4_foreach([_m4_arg], [m4_shift($@)],
 321             [m4_ifset([_m4_arg], [_m4_sep([$1])_m4_defn([_m4_arg])])])]dnl
 322 [_m4_popdef([_m4_sep])])
 323
 324 # m4_joinall(SEP, ARG1, ARG2...)
 325 # ------------------------------
 326 # Produce ARG1SEPARG2...SEPARGn.  An empty ARG results in back-to-back SEP.
 327 # No expansion is performed on SEP or ARGs.
 328 #
 329 # A bit easier than m4_join.  m4_foreach to the rescue.
 330 m4_define([m4_joinall],
 331 [[$2]m4_if(m4_eval([$# <= 2]), [1], [],
 332            [m4_foreach([_m4_arg], [m4_shift2($@)],
 333                        [[$1]_m4_defn([_m4_arg])])])])
 334
 335 # m4_list_cmp(A, B)
 336 # -----------------
 337 # Compare the two lists of integer expressions A and B.
 338 #
 339 # First, insert padding so that both lists are the same length; the
 340 # trailing +0 is necessary to handle a missing list.  Next, create a
 341 # temporary macro to perform pairwise comparisons until an inequality
 342 # is found.  For example, m4_list_cmp([1], [1,2]) creates _m4_cmp as
 343 #   m4_if(m4_eval([($1) != ($3)]), [1], [m4_cmp([$1], [$3])],
 344 #         m4_eval([($2) != ($4)]), [1], [m4_cmp([$2], [$4])],
 345 #         [0]_m4_popdef([_m4_cmp], [_m4_size]))
 346 # then calls _m4_cmp([1+0], [0], [1], [2+0])
 347 m4_define([m4_list_cmp],
 348 [m4_if([$1], [$2], 0,
 349   [m4_pushdef([_m4_size])_$0($1+0_m4_list_pad(m4_count($1), m4_count($2)),
 350                              $2+0_m4_list_pad(m4_count($2), m4_count($1)))])])
 351
 352 m4_define([_m4_list_pad],
 353 [m4_if(m4_eval($1 < $2), [1],
 354        [_m4_for([_m4_size], m4_incr([$1]), [$2], [1], [,0])])])
 355
 356 m4_define([_m4_list_cmp],
 357 [m4_define([_m4_size], m4_eval([$# >> 1]))]dnl
 358 [m4_define([_m4_cmp], m4_pushdef([_m4_cmp])[m4_if(]_m4_for([_m4_cmp],
 359    [1], _m4_size, [1], [$0_(_m4_cmp, m4_eval(_m4_cmp + _m4_size))])[
 360       [0]_m4_popdef([_m4_cmp], [_m4_size]))])_m4_cmp($@)])
 361
 362 m4_define([_m4_list_cmp_],
 363 [[m4_eval([($$1) != ($$2)]), [1], [m4_cmp([$$1], [$$2])],
 364 ]])
 365
 366 # m4_max(EXPR, ...)
 367 # m4_min(EXPR, ...)
 368 # -----------------
 369 # Return the decimal value of the maximum (or minimum) in a series of
 370 # integer expressions.
 371 #
 372 # m4_foreach to the rescue; we only need to replace _m4_minmax.  Here,
 373 # we need a temporary macro to track the best answer so far, so that
 374 # the foreach expression is tractable.
 375 m4_define([_m4_minmax],
 376 [m4_pushdef([_m4_best], m4_eval([$2]))m4_foreach([_m4_arg], [m4_shift2($@)],
 377     [m4_define([_m4_best], $1(_m4_best, _m4_defn([_m4_arg])))])]dnl
 378 [_m4_best[]_m4_popdef([_m4_best])])
 379
 380 # m4_set_add_all(SET, VALUE...)
 381 # -----------------------------
 382 # Add each VALUE into SET.  This is O(n) in the number of VALUEs, and
 383 # can be faster than calling m4_set_add for each VALUE.
 384 #
 385 # m4_foreach to the rescue.  If no deletions have occurred, then avoid
 386 # the speed penalty of m4_set_add.
 387 m4_define([m4_set_add_all],
 388 [m4_if([$#], [0], [], [$#], [1], [],
 389        [m4_define([_m4_set_size($1)], m4_eval(m4_set_size([$1])
 390           + m4_len(m4_foreach([_m4_arg], [m4_shift($@)],
 391     m4_ifdef([_m4_set_cleanup($1)],
 392              [[m4_set_add([$1], _m4_defn([_m4_arg]))]],
 393              [[m4_ifdef([_m4_set([$1],]_m4_defn([_m4_arg])[)], [],
 394                         [m4_define([_m4_set([$1],]_m4_defn([_m4_arg])[)],
 395                                    [1])m4_pushdef([_m4_set([$1])],
 396         _m4_defn([_m4_arg]))-])]])))))])])