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])-])]) 363
