John Kessenich | 7213324 | 2013-07-08 19:39:16 +0000 | [diff] [blame] | 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-2012 Free Software Foundation, Inc.
|
| 8 |
|
| 9 | # This file is part of Autoconf. This program is free
|
| 10 | # software; you can redistribute it and/or modify it under the
|
| 11 | # terms of the GNU General Public License as published by the
|
| 12 | # Free Software Foundation, either version 3 of the License, or
|
| 13 | # (at your option) any later version.
|
| 14 | #
|
| 15 | # This program is distributed in the hope that it will be useful,
|
| 16 | # but WITHOUT ANY WARRANTY; without even the implied warranty of
|
| 17 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
| 18 | # GNU General Public License for more details.
|
| 19 | #
|
| 20 | # Under Section 7 of GPL version 3, you are granted additional
|
| 21 | # permissions described in the Autoconf Configure Script Exception,
|
| 22 | # version 3.0, as published by the Free Software Foundation.
|
| 23 | #
|
| 24 | # You should have received a copy of the GNU General Public License
|
| 25 | # and a copy of the Autoconf Configure Script Exception along with
|
| 26 | # this program; see the files COPYINGv3 and COPYING.EXCEPTION
|
| 27 | # respectively. If not, see <http://www.gnu.org/licenses/>.
|
| 28 |
|
| 29 | # Written by Eric Blake.
|
| 30 |
|
| 31 | # In M4 1.4.x, every byte of $@ is rescanned. This means that an
|
| 32 | # algorithm on n arguments that recurses with one less argument each
|
| 33 | # iteration will scan n * (n + 1) / 2 arguments, for O(n^2) time. In
|
| 34 | # M4 1.6, this was fixed so that $@ is only scanned once, then
|
| 35 | # back-references are made to information stored about the scan.
|
| 36 | # Thus, n iterations need only scan n arguments, for O(n) time.
|
| 37 | # Additionally, in M4 1.4.x, recursive algorithms did not clean up
|
| 38 | # memory very well, requiring O(n^2) memory rather than O(n) for n
|
| 39 | # iterations.
|
| 40 | #
|
| 41 | # This file is designed to overcome the quadratic nature of $@
|
| 42 | # recursion by writing a variant of m4_foreach that uses m4_for rather
|
| 43 | # than $@ recursion to operate on the list. This involves more macro
|
| 44 | # expansions, but avoids the need to rescan a quadratic number of
|
| 45 | # arguments, making these replacements very attractive for M4 1.4.x.
|
| 46 | # On the other hand, in any version of M4, expanding additional macros
|
| 47 | # costs additional time; therefore, in M4 1.6, where $@ recursion uses
|
| 48 | # fewer macros, these replacements actually pessimize performance.
|
| 49 | # Additionally, the use of $10 to mean the tenth argument violates
|
| 50 | # POSIX; although all versions of m4 1.4.x support this meaning, a
|
| 51 | # future m4 version may switch to take it as the first argument
|
| 52 | # concatenated with a literal 0, so the implementations in this file
|
| 53 | # are not future-proof. Thus, this file is conditionally included as
|
| 54 | # part of m4_init(), only when it is detected that M4 probably has
|
| 55 | # quadratic behavior (ie. it lacks the macro __m4_version__).
|
| 56 | #
|
| 57 | # Please keep this file in sync with m4sugar.m4.
|
| 58 |
|
| 59 | # _m4_foreach(PRE, POST, IGNORED, ARG...)
|
| 60 | # ---------------------------------------
|
| 61 | # Form the common basis of the m4_foreach and m4_map macros. For each
|
| 62 | # ARG, expand PRE[ARG]POST[]. The IGNORED argument makes recursion
|
| 63 | # easier, and must be supplied rather than implicit.
|
| 64 | #
|
| 65 | # This version minimizes the number of times that $@ is evaluated by
|
| 66 | # using m4_for to generate a boilerplate into _m4_f then passing $@ to
|
| 67 | # that temporary macro. Thus, the recursion is done in m4_for without
|
| 68 | # reparsing any user input, and is not quadratic. For an idea of how
|
| 69 | # this works, note that m4_foreach(i,[1,2],[i]) calls
|
| 70 | # _m4_foreach([m4_define([i],],[)i],[],[1],[2])
|
| 71 | # which defines _m4_f:
|
| 72 | # $1[$4]$2[]$1[$5]$2[]_m4_popdef([_m4_f])
|
| 73 | # then calls _m4_f([m4_define([i],],[)i],[],[1],[2]) for a net result:
|
| 74 | # m4_define([i],[1])i[]m4_define([i],[2])i[]_m4_popdef([_m4_f]).
|
| 75 | m4_define([_m4_foreach],
|
| 76 | [m4_if([$#], [3], [],
|
| 77 | [m4_pushdef([_m4_f], _m4_for([4], [$#], [1],
|
| 78 | [$0_([1], [2],], [)])[_m4_popdef([_m4_f])])_m4_f($@)])])
|
| 79 |
|
| 80 | m4_define([_m4_foreach_],
|
| 81 | [[$$1[$$3]$$2[]]])
|
| 82 |
|
| 83 | # m4_case(SWITCH, VAL1, IF-VAL1, VAL2, IF-VAL2, ..., DEFAULT)
|
| 84 | # -----------------------------------------------------------
|
| 85 | # Find the first VAL that SWITCH matches, and expand the corresponding
|
| 86 | # IF-VAL. If there are no matches, expand DEFAULT.
|
| 87 | #
|
| 88 | # Use m4_for to create a temporary macro in terms of a boilerplate
|
| 89 | # m4_if with final cleanup. If $# is even, we have DEFAULT; if it is
|
| 90 | # odd, then rounding the last $# up in the temporary macro is
|
| 91 | # harmless. For example, both m4_case(1,2,3,4,5) and
|
| 92 | # m4_case(1,2,3,4,5,6) result in the intermediate _m4_case being
|
| 93 | # m4_if([$1],[$2],[$3],[$1],[$4],[$5],_m4_popdef([_m4_case])[$6])
|
| 94 | m4_define([m4_case],
|
| 95 | [m4_if(m4_eval([$# <= 2]), [1], [$2],
|
| 96 | [m4_pushdef([_$0], [m4_if(]_m4_for([2], m4_eval([($# - 1) / 2 * 2]), [2],
|
| 97 | [_$0_(], [)])[_m4_popdef(
|
| 98 | [_$0])]m4_dquote($m4_eval([($# + 1) & ~1]))[)])_$0($@)])])
|
| 99 |
|
| 100 | m4_define([_m4_case_],
|
| 101 | [$0_([1], [$1], m4_incr([$1]))])
|
| 102 |
|
| 103 | m4_define([_m4_case__],
|
| 104 | [[[$$1],[$$2],[$$3],]])
|
| 105 |
|
| 106 | # m4_bmatch(SWITCH, RE1, VAL1, RE2, VAL2, ..., DEFAULT)
|
| 107 | # -----------------------------------------------------
|
| 108 | # m4 equivalent of
|
| 109 | #
|
| 110 | # if (SWITCH =~ RE1)
|
| 111 | # VAL1;
|
| 112 | # elif (SWITCH =~ RE2)
|
| 113 | # VAL2;
|
| 114 | # elif ...
|
| 115 | # ...
|
| 116 | # else
|
| 117 | # DEFAULT
|
| 118 | #
|
| 119 | # We build the temporary macro _m4_b:
|
| 120 | # m4_define([_m4_b], _m4_defn([_m4_bmatch]))_m4_b([$1], [$2], [$3])...
|
| 121 | # _m4_b([$1], [$m-1], [$m])_m4_b([], [], [$m+1]_m4_popdef([_m4_b]))
|
| 122 | # then invoke m4_unquote(_m4_b($@)), for concatenation with later text.
|
| 123 | m4_define([m4_bmatch],
|
| 124 | [m4_if([$#], 0, [m4_fatal([$0: too few arguments: $#])],
|
| 125 | [$#], 1, [m4_fatal([$0: too few arguments: $#: $1])],
|
| 126 | [$#], 2, [$2],
|
| 127 | [m4_pushdef([_m4_b], [m4_define([_m4_b],
|
| 128 | _m4_defn([_$0]))]_m4_for([3], m4_eval([($# + 1) / 2 * 2 - 1]),
|
| 129 | [2], [_$0_(], [)])[_m4_b([], [],]m4_dquote([$]m4_eval(
|
| 130 | [($# + 1) / 2 * 2]))[_m4_popdef([_m4_b]))])m4_unquote(_m4_b($@))])])
|
| 131 |
|
| 132 | m4_define([_m4_bmatch],
|
| 133 | [m4_if(m4_bregexp([$1], [$2]), [-1], [], [[$3]m4_define([$0])])])
|
| 134 |
|
| 135 | m4_define([_m4_bmatch_],
|
| 136 | [$0_([1], m4_decr([$1]), [$1])])
|
| 137 |
|
| 138 | m4_define([_m4_bmatch__],
|
| 139 | [[_m4_b([$$1], [$$2], [$$3])]])
|
| 140 |
|
| 141 |
|
| 142 | # m4_cond(TEST1, VAL1, IF-VAL1, TEST2, VAL2, IF-VAL2, ..., [DEFAULT])
|
| 143 | # -------------------------------------------------------------------
|
| 144 | # Similar to m4_if, except that each TEST is expanded when encountered.
|
| 145 | # If the expansion of TESTn matches the string VALn, the result is IF-VALn.
|
| 146 | # The result is DEFAULT if no tests passed. This macro allows
|
| 147 | # short-circuiting of expensive tests, where it pays to arrange quick
|
| 148 | # filter tests to run first.
|
| 149 | #
|
| 150 | # m4_cond already guarantees either 3*n or 3*n + 1 arguments, 1 <= n.
|
| 151 | # We only have to speed up _m4_cond, by building the temporary _m4_c:
|
| 152 | # m4_define([_m4_c], _m4_defn([m4_unquote]))_m4_c([m4_if(($1), [($2)],
|
| 153 | # [[$3]m4_define([_m4_c])])])_m4_c([m4_if(($4), [($5)],
|
| 154 | # [[$6]m4_define([_m4_c])])])..._m4_c([m4_if(($m-2), [($m-1)],
|
| 155 | # [[$m]m4_define([_m4_c])])])_m4_c([[$m+1]]_m4_popdef([_m4_c]))
|
| 156 | # We invoke m4_unquote(_m4_c($@)), for concatenation with later text.
|
| 157 | m4_define([_m4_cond],
|
| 158 | [m4_pushdef([_m4_c], [m4_define([_m4_c],
|
| 159 | _m4_defn([m4_unquote]))]_m4_for([2], m4_eval([$# / 3 * 3 - 1]), [3],
|
| 160 | [$0_(], [)])[_m4_c(]m4_dquote(m4_dquote(
|
| 161 | [$]m4_eval([$# / 3 * 3 + 1])))[_m4_popdef([_m4_c]))])m4_unquote(_m4_c($@))])
|
| 162 |
|
| 163 | m4_define([_m4_cond_],
|
| 164 | [$0_(m4_decr([$1]), [$1], m4_incr([$1]))])
|
| 165 |
|
| 166 | m4_define([_m4_cond__],
|
| 167 | [[_m4_c([m4_if(($$1), [($$2)], [[$$3]m4_define([_m4_c])])])]])
|
| 168 |
|
| 169 | # m4_bpatsubsts(STRING, RE1, SUBST1, RE2, SUBST2, ...)
|
| 170 | # ----------------------------------------------------
|
| 171 | # m4 equivalent of
|
| 172 | #
|
| 173 | # $_ = STRING;
|
| 174 | # s/RE1/SUBST1/g;
|
| 175 | # s/RE2/SUBST2/g;
|
| 176 | # ...
|
| 177 | #
|
| 178 | # m4_bpatsubsts already validated an odd number of arguments; we only
|
| 179 | # need to speed up _m4_bpatsubsts. To avoid nesting, we build the
|
| 180 | # temporary _m4_p:
|
| 181 | # m4_define([_m4_p], [$1])m4_define([_m4_p],
|
| 182 | # m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$2], [$3]))m4_define([_m4_p],
|
| 183 | # m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$4], [$5]))m4_define([_m4_p],...
|
| 184 | # m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$m-1], [$m]))m4_unquote(
|
| 185 | # _m4_defn([_m4_p])_m4_popdef([_m4_p]))
|
| 186 | m4_define([_m4_bpatsubsts],
|
| 187 | [m4_pushdef([_m4_p], [m4_define([_m4_p],
|
| 188 | ]m4_dquote([$]1)[)]_m4_for([3], [$#], [2], [$0_(],
|
| 189 | [)])[m4_unquote(_m4_defn([_m4_p])_m4_popdef([_m4_p]))])_m4_p($@)])
|
| 190 |
|
| 191 | m4_define([_m4_bpatsubsts_],
|
| 192 | [$0_(m4_decr([$1]), [$1])])
|
| 193 |
|
| 194 | m4_define([_m4_bpatsubsts__],
|
| 195 | [[m4_define([_m4_p],
|
| 196 | m4_bpatsubst(m4_dquote(_m4_defn([_m4_p])), [$$1], [$$2]))]])
|
| 197 |
|
| 198 | # m4_shiftn(N, ...)
|
| 199 | # -----------------
|
| 200 | # Returns ... shifted N times. Useful for recursive "varargs" constructs.
|
| 201 | #
|
| 202 | # m4_shiftn already validated arguments; we only need to speed up
|
| 203 | # _m4_shiftn. If N is 3, then we build the temporary _m4_s, defined as
|
| 204 | # ,[$5],[$6],...,[$m]_m4_popdef([_m4_s])
|
| 205 | # before calling m4_shift(_m4_s($@)).
|
| 206 | m4_define([_m4_shiftn],
|
| 207 | [m4_if(m4_incr([$1]), [$#], [], [m4_pushdef([_m4_s],
|
| 208 | _m4_for(m4_eval([$1 + 2]), [$#], [1],
|
| 209 | [[,]m4_dquote($], [)])[_m4_popdef([_m4_s])])m4_shift(_m4_s($@))])])
|
| 210 |
|
| 211 | # m4_do(STRING, ...)
|
| 212 | # ------------------
|
| 213 | # This macro invokes all its arguments (in sequence, of course). It is
|
| 214 | # useful for making your macros more structured and readable by dropping
|
| 215 | # unnecessary dnl's and have the macros indented properly.
|
| 216 | #
|
| 217 | # Here, we use the temporary macro _m4_do, defined as
|
| 218 | # $1[]$2[]...[]$n[]_m4_popdef([_m4_do])
|
| 219 | m4_define([m4_do],
|
| 220 | [m4_if([$#], [0], [],
|
| 221 | [m4_pushdef([_$0], _m4_for([1], [$#], [1],
|
| 222 | [$], [[[]]])[_m4_popdef([_$0])])_$0($@)])])
|
| 223 |
|
| 224 | # m4_dquote_elt(ARGS)
|
| 225 | # -------------------
|
| 226 | # Return ARGS as an unquoted list of double-quoted arguments.
|
| 227 | #
|
| 228 | # _m4_foreach to the rescue.
|
| 229 | m4_define([m4_dquote_elt],
|
| 230 | [m4_if([$#], [0], [], [[[$1]]_m4_foreach([,m4_dquote(], [)], $@)])])
|
| 231 |
|
| 232 | # m4_reverse(ARGS)
|
| 233 | # ----------------
|
| 234 | # Output ARGS in reverse order.
|
| 235 | #
|
| 236 | # Invoke _m4_r($@) with the temporary _m4_r built as
|
| 237 | # [$m], [$m-1], ..., [$2], [$1]_m4_popdef([_m4_r])
|
| 238 | m4_define([m4_reverse],
|
| 239 | [m4_if([$#], [0], [], [$#], [1], [[$1]],
|
| 240 | [m4_pushdef([_m4_r], [[$$#]]_m4_for(m4_decr([$#]), [1], [-1],
|
| 241 | [[, ]m4_dquote($], [)])[_m4_popdef([_m4_r])])_m4_r($@)])])
|
| 242 |
|
| 243 |
|
| 244 | # m4_map_args_pair(EXPRESSION, [END-EXPR = EXPRESSION], ARG...)
|
| 245 | # -------------------------------------------------------------
|
| 246 | # Perform a pairwise grouping of consecutive ARGs, by expanding
|
| 247 | # EXPRESSION([ARG1], [ARG2]). If there are an odd number of ARGs, the
|
| 248 | # final argument is expanded with END-EXPR([ARGn]).
|
| 249 | #
|
| 250 | # Build the temporary macro _m4_map_args_pair, with the $2([$m+1])
|
| 251 | # only output if $# is odd:
|
| 252 | # $1([$3], [$4])[]$1([$5], [$6])[]...$1([$m-1],
|
| 253 | # [$m])[]m4_default([$2], [$1])([$m+1])[]_m4_popdef([_m4_map_args_pair])
|
| 254 | m4_define([m4_map_args_pair],
|
| 255 | [m4_if([$#], [0], [m4_fatal([$0: too few arguments: $#])],
|
| 256 | [$#], [1], [m4_fatal([$0: too few arguments: $#: $1])],
|
| 257 | [$#], [2], [],
|
| 258 | [$#], [3], [m4_default([$2], [$1])([$3])[]],
|
| 259 | [m4_pushdef([_$0], _m4_for([3],
|
| 260 | m4_eval([$# / 2 * 2 - 1]), [2], [_$0_(], [)])_$0_end(
|
| 261 | [1], [2], [$#])[_m4_popdef([_$0])])_$0($@)])])
|
| 262 |
|
| 263 | m4_define([_m4_map_args_pair_],
|
| 264 | [$0_([1], [$1], m4_incr([$1]))])
|
| 265 |
|
| 266 | m4_define([_m4_map_args_pair__],
|
| 267 | [[$$1([$$2], [$$3])[]]])
|
| 268 |
|
| 269 | m4_define([_m4_map_args_pair_end],
|
| 270 | [m4_if(m4_eval([$3 & 1]), [1], [[m4_default([$$2], [$$1])([$$3])[]]])])
|
| 271 |
|
| 272 | # m4_join(SEP, ARG1, ARG2...)
|
| 273 | # ---------------------------
|
| 274 | # Produce ARG1SEPARG2...SEPARGn. Avoid back-to-back SEP when a given ARG
|
| 275 | # is the empty string. No expansion is performed on SEP or ARGs.
|
| 276 | #
|
| 277 | # Use a self-modifying separator, since we don't know how many
|
| 278 | # arguments might be skipped before a separator is first printed, but
|
| 279 | # be careful if the separator contains $. _m4_foreach to the rescue.
|
| 280 | m4_define([m4_join],
|
| 281 | [m4_pushdef([_m4_sep], [m4_define([_m4_sep], _m4_defn([m4_echo]))])]dnl
|
| 282 | [_m4_foreach([_$0([$1],], [)], $@)_m4_popdef([_m4_sep])])
|
| 283 |
|
| 284 | m4_define([_m4_join],
|
| 285 | [m4_if([$2], [], [], [_m4_sep([$1])[$2]])])
|
| 286 |
|
| 287 | # m4_joinall(SEP, ARG1, ARG2...)
|
| 288 | # ------------------------------
|
| 289 | # Produce ARG1SEPARG2...SEPARGn. An empty ARG results in back-to-back SEP.
|
| 290 | # No expansion is performed on SEP or ARGs.
|
| 291 | #
|
| 292 | # A bit easier than m4_join. _m4_foreach to the rescue.
|
| 293 | m4_define([m4_joinall],
|
| 294 | [[$2]m4_if(m4_eval([$# <= 2]), [1], [],
|
| 295 | [_m4_foreach([$1], [], m4_shift($@))])])
|
| 296 |
|
| 297 | # m4_list_cmp(A, B)
|
| 298 | # -----------------
|
| 299 | # Compare the two lists of integer expressions A and B.
|
| 300 | #
|
| 301 | # m4_list_cmp takes care of any side effects; we only override
|
| 302 | # _m4_list_cmp_raw, where we can safely expand lists multiple times.
|
| 303 | # First, insert padding so that both lists are the same length; the
|
| 304 | # trailing +0 is necessary to handle a missing list. Next, create a
|
| 305 | # temporary macro to perform pairwise comparisons until an inequality
|
| 306 | # is found. For example, m4_list_cmp([1], [1,2]) creates _m4_cmp as
|
| 307 | # m4_if(m4_eval([($1) != ($3)]), [1], [m4_cmp([$1], [$3])],
|
| 308 | # m4_eval([($2) != ($4)]), [1], [m4_cmp([$2], [$4])],
|
| 309 | # [0]_m4_popdef([_m4_cmp]))
|
| 310 | # then calls _m4_cmp([1+0], [0*2], [1], [2+0])
|
| 311 | m4_define([_m4_list_cmp_raw],
|
| 312 | [m4_if([$1], [$2], 0,
|
| 313 | [_m4_list_cmp($1+0_m4_list_pad(m4_count($1), m4_count($2)),
|
| 314 | $2+0_m4_list_pad(m4_count($2), m4_count($1)))])])
|
| 315 |
|
| 316 | m4_define([_m4_list_pad],
|
| 317 | [m4_if(m4_eval($1 < $2), [1],
|
| 318 | [_m4_for(m4_incr([$1]), [$2], [1], [,0*])])])
|
| 319 |
|
| 320 | m4_define([_m4_list_cmp],
|
| 321 | [m4_pushdef([_m4_cmp], [m4_if(]_m4_for(
|
| 322 | [1], m4_eval([$# >> 1]), [1], [$0_(], [,]m4_eval([$# >> 1])[)])[
|
| 323 | [0]_m4_popdef([_m4_cmp]))])_m4_cmp($@)])
|
| 324 |
|
| 325 | m4_define([_m4_list_cmp_],
|
| 326 | [$0_([$1], m4_eval([$1 + $2]))])
|
| 327 |
|
| 328 | m4_define([_m4_list_cmp__],
|
| 329 | [[m4_eval([($$1) != ($$2)]), [1], [m4_cmp([$$1], [$$2])],
|
| 330 | ]])
|
| 331 |
|
| 332 | # m4_max(EXPR, ...)
|
| 333 | # m4_min(EXPR, ...)
|
| 334 | # -----------------
|
| 335 | # Return the decimal value of the maximum (or minimum) in a series of
|
| 336 | # integer expressions.
|
| 337 | #
|
| 338 | # _m4_foreach to the rescue; we only need to replace _m4_minmax. Here,
|
| 339 | # we need a temporary macro to track the best answer so far, so that
|
| 340 | # the foreach expression is tractable.
|
| 341 | m4_define([_m4_minmax],
|
| 342 | [m4_pushdef([_m4_best], m4_eval([$2]))_m4_foreach(
|
| 343 | [m4_define([_m4_best], $1(_m4_best,], [))], m4_shift($@))]dnl
|
| 344 | [_m4_best[]_m4_popdef([_m4_best])])
|
| 345 |
|
| 346 | # m4_set_add_all(SET, VALUE...)
|
| 347 | # -----------------------------
|
| 348 | # Add each VALUE into SET. This is O(n) in the number of VALUEs, and
|
| 349 | # can be faster than calling m4_set_add for each VALUE.
|
| 350 | #
|
| 351 | # _m4_foreach to the rescue. If no deletions have occurred, then
|
| 352 | # avoid the speed penalty of m4_set_add.
|
| 353 | m4_define([m4_set_add_all],
|
| 354 | [m4_if([$#], [0], [], [$#], [1], [],
|
| 355 | [m4_define([_m4_set_size($1)], m4_eval(m4_set_size([$1])
|
| 356 | + m4_len(_m4_foreach(m4_ifdef([_m4_set_cleanup($1)],
|
| 357 | [[m4_set_add]], [[_$0]])[([$1],], [)], $@))))])])
|
| 358 |
|
| 359 | m4_define([_m4_set_add_all],
|
| 360 | [m4_ifdef([_m4_set([$1],$2)], [],
|
| 361 | [m4_define([_m4_set([$1],$2)],
|
| 362 | [1])m4_pushdef([_m4_set([$1])], [$2])-])])
|